【算法随笔】【斐波那契数列】
> 作为程序员想必大家都非常熟悉斐波那契数列。在算法课上经常被用来引入递归算法与迭代算法。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中涉及加法与乘法，乘法指令的运算代价要大于加法指令（参见上一节中的大数乘法），因此实际的运行时间上，算法二可能会优于算法三。