斐波那契数列，想必读者们已经很熟悉了，指的就是这样一个数列：0,1,1,2,3,5,8,13,21,34...这个序列从第三项开始，每一项等于前两项的和。如何用计算机来解决这个问题，一开始似乎是最简单的递归实现方式。不知道各位读者有没有考虑过下面这些小问题呢？递归的方法能找到所有的解吗？当n=80、800甚至8000以上时能解吗？想出几种不同的解法等等实现deffib(n):ifn==0:return0elifn==1:return1else:returnfib(n-1)+fib(n-2)求解上面的递归公式：$$T(n)=T(n-1)+T(n-2)+1≈2^n=O(2^n)$$上面的实现效率很低，重复动作太多都是在递归过程中进行的，时间复杂度是指数级的，而且受限于递归的深度，求解的范围非常有限。递归优化deffib(n):deffib_iter(n,x,y):ifn==0:returnxelse:returnfib_iter(n-1,y,x+y)returnfib_iter(n,0,1)以上是尾递归优化方法。虽然减少了很多不必要的计算，但还是受到递归深度的限制。让我们看看一些更好的解决方案。动态规划自下而上deffib(n):memo=[0,1]foriinrange(2,n+1):memo.append(memo[i-1]+memo[i-2])returnmemo[n]自上而下的memo={0:0,1:1}deffib(n):如果memo中有n:returnmemo[n]ifn==0:return0elifn==1:return1memo[n]=fib(n-1)+fib(n-2)returnmemo[n]以上两种方案都将问题的复杂度降低到O(n)级别，缺点是空间复杂度也在）。改进方案，高效缓存通过递归可知，当前值只与前两个值相关，所以我们只需要保留后两个值即可deffib(n):a,b=0,1foriinrange(n):a,b=b,a+breturna时间复杂度为O(n)，空间复杂度降低为O(1)。同样，我们给出C++版本命名空间的实现{structfib_cache{fib_cache():previous_{0},last_{1},size_{2}{}size_tsize()const{returnsize_;}unsignedintoperator[](unsignedintn)const{returnn==size_-1?last_:n==size_-2?previous_:throwstd::out_of_range("该值不再在缓存中");}voidpush_back(unsignedintvalue){size_++;前一个_=最后一个_；last_=值；}private:unsignedintprevious_;unsignedintlast_；size_tsize_;};}//namespaceunsignedintfib(unsignedintn){fib_cache缓存;if(cache.size()>n){返回缓存[n];}else{constautoresult=fib(n-1)+fib(n-2);缓存.push_back（结果）；返回结果；}}上面的程序受无符号整数最大值的约束，计算范围有限。读者可以使用C+11引入的大整数longlong即可解决，大整数的存储和计算也可以自己实现。上述算法在O(n)级别是最快的。我们来看一个O(logn)级别的算法矩阵算法。先来看一个斐波那契数列的矩阵关系推导$$\left[\begin{matrix}F_n\\F_{n-1}\\\end{matrix}\right]=\left[\begin{matrix}F_{n-1}+F_{n-2}\\F_{n-1}\\\end{矩阵}\right]=\left[\begin{matrix}1&1\\1&0\\\end{matrix}\right]*\left[\begin{matrix}F_{n-1}\\F_{n-2}\\\end{matrix}\right]$$从上面的推导，我们可以很容易得到如下结果$$\left[\begin{matrix}F_n\\F_{n-1}\\\end{matrix}\right]=\left[\begin{matrix}1&1\\1&0\\\end{matrix}\right]^{n-1}*\left[\begin{matrix}F_{1}\\F_{0}\\\end{matrix}\right]=\left[\begin{matrix}1&1\\1&0\\\end{matrix}\right]^{n-1}*\left[\begin{matrix}1\\0\\\end{matrix}\对]$$上式就变成了矩阵的幂，矩阵的幂可以用二元算法快速求幂（本质上是分治思想）$$x^n=\begin{cases}x^{n/2}*x^{n/2},&even\\x^{(n-1)/2}*x^{(n-1)/2}*x,&odd\结束{cases}$$求解上面的递归公式：$$T(n)=T(n/2)+1=O(logn)$$这里不给出具体实现，读者可以自行尝试，或者使用python的第三方numpy库来计算矩阵幂End事实上，斐波那契问题有很多高效的解法，等待你的探索。这段时间的结束，只是下一段旅程的起点……
