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

2022-05-23

序言

这篇文章在 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+\sqrt5}{2}, x_2 = \frac{1-\sqrt5}{2}$$

$x_2$ 显然为单调递减,不符合结果，所以时间复杂度可以估算为 $O(\frac{1+\sqrt5}{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_1a_{n-1} + c_2a_{n-2}$$

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

$$x^2-c_1x-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\sqrt5}{2}$$

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

代入通项公式：

$$a_n=\frac{a_2-qa_1}{p(p-q)}p^n+\frac{pa_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}{\sqrt5}((\frac{1+\sqrt5}{2})^n+(\frac{1-\sqrt5}{2})^n)$$

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

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

$$T(n)=O(\frac{1+\sqrt5}{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}{\sqrt5}((\frac{1+\sqrt5}{2})^n+(\frac{1-\sqrt5}{2})^n)$$

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

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

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

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

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

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

$$a_n=a^{n_02^0} \times a^{n_12^1} \times…\times a^{n_t2^t}$$

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

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

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

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

$$O(logn)$$

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

本文链接：https://iceprosurface.com/2022/fibonacci/index.html

作者授权：除特别说明外，本文由 icepro 原创编译并授权刊载发布。