斐波那契数列算法时间复杂度

序言

这篇文章在 notion 那边放了很久了，现在拉过来这边重新复刻一遍，其实只是为了试试博客的 mathjax 没有正常工作（）

记得那个时候写这篇文章的时候，大家在出面试题，这里就提到了青蛙跳格子的经典问题（就是 斐波那契数列 求 n 项的变种），所以顺手就整理了一篇文章出来。

解法

朴素递归求解方式

快速脑补法算时间复杂度 (大雾)

易得该求解方式可以构造为二叉树，但不是一个满二叉树，其运算次数约等于树上的节点，而满二叉树的节点总数为： $2^n$。

所以 时间复杂度至少为 $O(2^n)$ 但此解应当不是一个足够小的逼近上界，毕竟我可以胡扯他的 时间复杂度 是 $O(2^{n^2})$，你也不能说我是错的，毕竟结果在这个区间里面。

废话文学

话是这么说没错，但是按这个理论岂不是所有 算法 复杂度都可以表示 $O(\infty )$

当然我们易证此解大小应当小于 $2^n$ 且数量级大致相差不大，那么我们讨巧的可以构造如下方程式求解（因为时间复杂度 的求解上，我们可以近似认为下述式子是相等的）：

$x^n=x^{(n-1)}+x^{(n-2)}$

$x^2-x-1=0$

$x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2}$

$x_2$ 显然为单调递减,不符合结果，所以 时间复杂度可以估算为 $O({\frac{1+\sqrt{5}}{2}}^n)$

数学证明方式

那么如果需要精确求解时间复杂度，可不能 “大概”、“脑补”、“易得”了，我们得通过数学方法分析（如果只用高中知识的话可以凑出一个等比数列求解——类似于上面的快速脑补法）。

首先朴素递归方式可以这样计算 时间复杂度：

设 $f(n)$ 调用的时间为 $T(n)$ 那么必有：

$T(n)=O(1)(T(n-1)+T(n-2))$

因为 $O(1)$ 可以忽略，那么只需要求出 $T(n)=T(n-1)+T(n-2)$ 即可

那么这个式子本身就是一个斐波那契数列，而斐波那契数列是一个二阶常系数齐次线性递推数列:

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}$

故该齐次递推数列有如下特征方程：

$x^2-c_{1}x-c_2=0$ $x^2-x-1=0$

$\lambda =\frac{-a_1\pm \sqrt{a_1^2-4a_2}}{2}$

代入 $a1=-1,a2=-1$ 可求解出上述方程式的解为 ：

$\lambda =\frac{1\pm \sqrt{5}}{2}$

$p=\frac{1+\sqrt{5}}{2},q=\frac{1-\sqrt{5}}{2}$

代入通项公式：

$a_n=\frac{a_2-q{a}_1}{p(p-q)}{p}^n+\frac{p{a}_1-a_2}{q(p-q)}{q}^n$

$a_n=\frac{1-q}{p(p-q)}{p}^n+\frac{p-1}{q(p-q)}{q}^n$

$a_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^n+(\frac{1-\sqrt{5}}{2}{)}^n)$

代入后转换为大O（其实直接求级数后去掉常数项就可以了）:

$T(n)=O(1)(O({\frac{1+\sqrt{5}}{2}}^n)+O({\frac{1-\sqrt{5}}{2}}^n))$

$T(n)=O({\frac{1+\sqrt{5}}{2}}^n)$

尾递归/迭代法

我们可以清楚的发现上面那个求解方法有很多重复项，而且编程中常见的有尾递归（就是 goto）的优化策略。而任何尾递归写法基本都可以转化为迭代法求解方法。比如可以这么写：

if (n < 1) { 
	return 0 
} 
if (n < 2) { 
	return 1
} 
let a1 = 1;
let a2 = 1; 
let sum = 1; 
for(let i = 3; i < n; i++) {
	sum = a1 + a2; 
	a1 = a2; 
	a2 = sum 
} 
return sum

所以不用算：$T(n)=O(n)$

通项公式解法

上文我们已经求解出了通项公式，那么易得:

$a_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^n+(\frac{1-\sqrt{5}}{2}{)}^n)$

很多材料上都会说这玩意儿是 $O(1)$ 复杂度，用屁股想想都知道不可能，你看上面有两个大大 n 次方。而且通项公式还容易出现精度丢失，出现 浮点数 的问题（当然你可以强行转换为整数 ，但是迭代情况下精度累计丢失可能使得结果不正确）

首先求指数最简单的方法是迭代求解，都不用写代码，易得 时间复杂度 是：$T(n)=O(n)$

当然求指数最快的方法是矩阵求解方法，俗称快速幂。

比如求解 $a^b$， 假定求 $b=11$，我们可以转化为二进制求法 $(11{=}^{\prime }1011^{\prime })$，直接拼成：

$a_{11}=a^{2^0+2^1+2^3}$

那么我们往上代换以下马上可以得到通项公式：

$a_n=a^{n_0{2}^0}\times a^{n_1{2}^1}\times ......\times a^{n_t{2}^t}$

显然 n 有 $lo{g}_{2}n+1$ 个二进制位，所以假定我们知道 $n_0,n_1......，n_{lo{g}_{2}n}$,那么只需要做 $lo{g}_{2}n$ 次乘法以后就可以快速获得结果。

大家是不是发现问题了,显然所在位很好求，所以其实只需要求出 $a_1...a_n$ 的关系就可以，那么关系好求么？那可太好求了，直接拿上一项平方一下就可以拿到了，注意一下是不是和之前的迭代法就比较像了？

那么这个算法的总体复杂度会是多少呢？

我们首先花了$\Theta (1)$的时间求了第一项，随后花了 $\Theta (lo{g}_{2}n)$的时间相乘，那么总体 时间复杂度就是:

$O(logn)$

本文标题：斐波那契数列算法时间复杂度

永久链接：https://iceprosurface.com/2022/fibonacci/

作者授权：本文由 icepro 原创编译并授权刊载发布。

版权声明：本文使用「署名-非商业性使用-相同方式共享 4.0 国际」创作共享协议，转载或使用请遵守署名协议。

查看源码：