【算法随笔】【斐波那契数列】

> 作为程序员想必大家都非常熟悉斐波那契数列。在算法课上经常被用来引入递归算法与迭代算法。CS170中,同样也对斐波那契额数列中的解法进行了一系列分析。
> 【注】斐波那契数列,在本文中不再赘述。

### algorithm1
- 最朴素的想法就是根据斐波那契数列的递推公式,并利用递归算法进行求解
$$F_n = F_{n-1} + F_{n-2}$$
```
def fib(n):
if n <= 2:
return 1;
return fib(n-1) + fib(n-2)
```
- 那么这种算法的复杂度是多少呢?
- 我们很容易就可以推算出这种算法的flops下界
- 原递推式
- $T(n) = T(n-1) + T(n-2) + 1$
- 显然有
- $T(n) >= 2T(n-2) + 1 => 4T(n-4) + (1 + 2) => ... => Ω(2^{n})$
- ok, 这个算法的复杂度至少为$2^n$ 级别, 熟悉算法的朋友们都知道,这种复杂度的算法,当n稍微大一点点时,计算开销就会变成天文数字,那么有没有优化的办法呢?

### algorithm2
- 既然计算第n项时,只依赖n-1与n-2项,那我从n=1一路自底向上,用迭代的算法直接求解不就行了?这种算法很简单,只需要计算n次就可以得到最终的结果,显然渐进复杂度为$O(n)$

### algorithm3
- 那么还有更快的算法么? 可以试试构造递推矩阵
$$
A = \left[
\begin{matrix}
1 & 1 \\
1 & 0 \\
\end{matrix}
\right],
v = \left[
\begin{matrix}
F_1 \\
F_0 \\
\end{matrix}
\right]
$$
$$
v_n = \left[
\begin{matrix}
F_n \\
F_{n-1} \\
\end{matrix}
\right] = A^nv
$$
- 对于$x^n$次方,我们知道存在快速幂算法,使得其运算复杂度为$O(logn)$,对于矩阵来说,同样可以应用快速幂算法,最终达到$O(logn)$的复杂度。
- 这里再补充一下,矩阵递推公式实际上可以进行分解,其中Q与Q^T是单位正交矩阵, B为对角矩阵
$$
v_n = A^nv = (QBQ^T)^nv = QB^nQ^Tv
$$
$B^n$实际上就是对角线上的数的n次方运算,是一个确定的公式。因此这种方式实际上已经可以推导出斐波那契数列的精确公式,其代价就是计算该公式的代价。

### 后记
我们简单的分析了三种不同方法的flops复杂度,但实际上的运算复杂度与我们推算的复杂度是略有不同的,在算法2中仅涉及加法,而算法3中涉及加法与乘法,乘法指令的运算代价要大于加法指令(参见上一节中的大数乘法),因此实际的运行时间上,算法二可能会优于算法三。

热门相关:仙城纪   仗剑高歌   网游之逆天飞扬   寂静王冠   霸皇纪