chap 0-1 算法基础-Start with Fibonacci

1. Fibonacci数列

Fibonacci是15世纪意大利著名的数学家，虽然大多数人不太清楚他的具体贡献，却都对Fibonacci数列耳熟能详：

$$
0,1,1,2,3,5,8,13,21,34
$$

我们设Fibonacci数列的第$n$项的值为$F_n$，则数列的每一项可以由以下递推式生成：

$$
\begin{equation}
F_n=
\begin{cases}
F_{n-1}+F_{n-2}, & n>1 \\ 1, & n=1 \\ 0, & n=0
\end{cases}
\end{equation}
$$

假设$F_n\geq 2^{cn}$成立，通过数学归纳法可以推出，$2^c\leq \frac{1+\sqrt{5}}{2}$，即$F_n\geq 2^{0.694n}$。通过数学方法也可以推出：

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

使用计算机求解时，如何设计出一个计算$F_n$的算法？

2. fib1-指数时间(exponential)

最容易想到的算法就是直接利用上述的递推式定义，写成递归形式：

// 假设所有数值范围均在int最大范围内
int fib1(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib1(n - 1) + fib1(n - 2);
}

每当设计完一个算法时，都需要问自己三个问题：

1. 算法是否正确？
2. 给定输入大小$n$，算法需要花费多少时间完成？
3. 是否存在更好的其他算法？

对于fib1，很容易验证算法是正确的，但如何确定该算法的运行时间？最简单的方法是，利用各编程语言自带的计时指令，可以输出每次程序运行的时间：

// 本地PC运行结果，不同电脑的运行结果可能不同
fib1_test
Input n: 10
Output: 55
time = 1ms
======================================
fib1_test
Input n: 20
Output: 6765
time = 1ms
======================================
fib1_test
Input n: 30
Output: 832040
time = 61ms
======================================
fib1_test
Input n: 35
Output: 9227465
time = 564ms
======================================
fib1_test
Input n: 40
Output: 102334155
time = 6241ms
======================================

但是我们不可能每次都通过实验的方法去预估时间，而是应该提前进行算法分析。算法就是一个程序，那么如何分析一个程序执行花费的时间呢？

先粗略分析，定义$T(n)$表示执行算法$fib1(n)$所需要的computer steps的数量。这里的computer steps可以理解为计算机执行的宏观操作，比如在$fib1(n)$中，$n$足够大时，除了递归，还存在2次分支判断操作和1次加法操作。我们可以由此计算出$T(n)$：

$$
\begin{equation}
T(n)=
\begin{cases}
& 1 & n=0 \\ & 2 & n=1 \\ & T(n-1)+T(n-2)+3 & n>1
\end{cases}
\end{equation}
$$

对比$F_n$的表达式，易得：$T(n)\geq F_n$，可知$T(n)$将关于$n$以指数级(exponential)递增。

有了执行算法需要的computer steps的数量，和执行每个step所花费的平均时间，就可以预估出算法的执行时间。以计算$F_{200}$为例，需要$T(200)\geq F_{200}\geq 2^{138}$个steps。若某台超级计算机每秒平均执行$4\times 10^{14}$个steps，则运行完该算法需要至少$2^{94}$秒。

3. fib2-多项式时间(polynomial)

解决了前两个问题，下面考虑第三个问题，是否存在更好的算法？显然，在上述例子中，在有生之年计算机将无法计算出$F_{200}$。通过分析，不难发现，fib1中存在大量的重复计算：

                           F(n)
                _____________|_____________
               |                           |
              F(n-1)                     F(n-2)
        _______|_______            ________|________
       |               |          |                 |
     F(n-2)          F(n-3)     F(n-3)            F(n-4)
   ____|____      _____|____    ____|____        _____|____
  |         |    |          |  |         |      |          |
F(n-3)  F(n-4)  F(n-4) F(n-5)  F(n-4) F(n-5)   F(n-5)   F(n-6)                  

我们可以将每个计算好的$F$的值存储起来，便于下一次直接使用：

int fib2(int n) {
	if (n == 0) return 0;
	int f0 = 0;
	int f1 = 1;
	int tmp;
	for (int i = 1; i < n; ++i) {
		tmp = f1;
		f1 = f1 + f0;
		f0 = tmp;
	}
	return f1;
}

不难看出，$T(n)$将关于$n$线性递增。通过这一优化，step的数量从指数级降低为多项式级(polynomial)。

即使现在的结果还不错，我们仍然要问：是否存在更好的算法？确实存在，此处先打住。

4. 深入分析

上述粗略分析忽略的一个重要问题是每个computer step的执行时间并不是相同的。每个处理器的指令集里含有多种类型的指令，如访存、算术运算、分支跳转等，每个step均可以分解为若干指令。每个指令的执行时间也并不是完全相同的。

举个简单的例子，对于加法这个操作，由于加法器本身的性质，加数的bit数越大，加法耗费的时间也越长。可以证明，两个$n-bit$的数相加的时间与$n$成正比，$F_n$大约为 $0.694n$ bits，因此在算法$fib2$中，也可以说$T(n)$关于$n^2$线性递增。

是不是感觉越来越复杂？我们从一开始非常粗略地分析，又落入到了现在过于细致地分析的陷阱里。是否有一种合适的方法来分析算法执行的时间？下面将详细介绍Big-$O$ notation。

Quick Link: 算法笔记整理