摄影：产品经理吃：kingname & 产品经理
在小说《三体》里面，我们知道一个词叫做降维打击，通过把对手所在空间的维度降低从而实现团灭整个星系。
但是如果对方所在的维度已经是一维了，降不动了，那么要实现维度打击的办法就是把自己的维度提升。
今天我们将会从二维的层面来解决一维的问题，把时间复杂度从O(n)降低到 O(logn)。
想必大家对斐波拉契数列已经很熟悉了：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55……
从第三位开始，每一位都是前面两位之和。
在一维层面，我们能实现的最快的解法时间复杂度为O(n)：
def fib(n): if n < 1: return0 if n in [1, 2]: return1 a = fib(1) b = fib(2) for i in range(3, n + 1): a, b = b, a + b return b
运行效果如下图所示：
知道了第1个数和第2个数，才能计算第3个数。知道了第2个数和第3个数，才能计算第4个数。时间复杂度为 O(n)。前面的数必需都计算出来，才能计算后面的数。要知道第n位数字，就需要知道第 n - 1 位数字，要知道第 n-1 位数字，就需要知道 n-2 位数字。这不是显而易见的吗？
难道还有办法在不计算第3个数的情况下，就把第4个数算出来？
斐波拉契数列是一个一维的数列，看起来就像是一条线一样。你要走到第4个数，必需先走到第3个数。
但如果你从二维的视角来看待，你就会发现实际上你可以从旁边绕过去。
现在我们假设斐波拉契数列第 n 位的值为。第 n-1位的值为。那么我们可以把它表示为一个2行1列的矩阵：
由于，所以上面的矩阵可以转换为：
再进一步转换为：
我们来复习一下矩阵的乘法：
所以
所以
同理，
所以一路推下来：
虽然斐波那契数列没有第0个数，但是我们通过它的生成规则，可以人工设定。
于是，求斐波拉契数列第 n 位的值转换为矩阵运算
运算结果是一个2行1列的矩阵，第1行第1列这个数就是我们需要的结果。
到目前为止，矩阵运算：
看起来还是要乘n 次，时间复杂度还是 O(n)。那么优化在哪里呢？此时我们就要说到快速幂运算了。
以计算为例，看起来要进行15次乘法：
2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * * 2 * 2 * 2 * 2 * 2 * 2
但实际上，我们真正运算的时候是这样的：
所以，要计算我们可以这样写代码:
a = 2 * 2 b = a * a c = b * b result = c * c
所以对于，我们最多只需要计算次乘法即可解决问题（n 为偶数不加1，为奇数加1）。
这种计算方法对矩阵同样适用。并且，对于矩阵计算，Python 的 numpy 库有直接可用的函数，所以要计算一个矩阵的 n 次幂，代码非常简单：
from numpy.linalg import matrix_power matrix_power(矩阵, n)
所以，我们使用矩阵运算来写一个求斐波那契数列的函数：
import numpy as np from numpy.linalg import matrix_power def fib_matrix(n): if n == 1: return1 matrix = np.matrix('1 1; 1 0', dtype='uint64') power = matrix_power(matrix, n - 1) base_matrix = np.matrix('1; 0') result_matrix = np.matmul(power, base_matrix) return result_matrix.item(0)
运行效果如下图所示：
但是，由于 numpy 中对整型数字的精度有限定，超出精度以后就会出现数值溢出，变成负数的情况。对于这个问题，我们将会在下一篇文章中介绍解决办法。
