請用「Mou」打開😅
豆瓣上看到有人推荐 S. Dasgupta, C. H. Papadimitriou 和 U. V. Vazirani 写的Algorithms，随手翻了下⋯⋯
学计算机的没有不知道 Hanoi塔和 Fibonacci 数列的。但 Hanoi 塔问题是死的，而求解 Fibonacci 数列却精彩不断。
Fibonacci 数列$$$F_0, F_1, F_2, ...$$$是这样定义的：
$$ F_0 = 0, F_1= 1, F_n = F_{n-1} + F_{n-2} $$
如果用定义来求解，计算$$$F_n$$$至少需要$$$F_{n-1} + F_{n-2} + 1$$$次加法（还不算对递归终点的判断），也就是说用这种策略计算$$$F_n$$$所需的加操作不少于其自身。那$$$F_n$$$是个什么数量级呢？$$$F_n ≥ 2^{0.5n} (n ≥ 6)$$$
不信？
$$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, ...$$
$$2^{0/2} = 1, 2^{1/2} = \sqrt{2}, 2^{2/2} = 2, 2^{3/2} = 2\sqrt{2}, 2^{4/2} = 4, 2^{5/2} = 4\sqrt{2}, 2^{6/2} = 8, ...$$
现在开始绑定自然数（数学归纳啦）：
设$$$F_k ≥ 2^{k/2} (6 ≤ k < n)$$$，则
$$F_n = F_{n-1} + F_{n-2} ≥ 2·F_{n-2} ≥ 2·2^{(n-2)/2} = 2^{n/2}$$
0.5 应该是个比较糙的估计，上限是多少呢？
设$$$F_k ≥ 2^{ck} (6 ≤ k < n)$$$，则
$$F_n = F_{n-1} + F_{n-2} ≥ 2^{c(n-1)} + 2^{c(n-2)} = 2^{c(n-2)} (2^c + 1) ≥ 2^{cn}$$
即$$$2^c + 1 ≥ 2^{2c}$$$
简单吧，一元二次方程。令$$$t = 2c$$$，则$$$t2 - t -1 ≤ 0$$$。还因为{$$$F_n$$$}递减，所以
\[2^c > 1 = 20, \
0 < t ≤ {{1+\sqrt{5}} \over 2}, \
c ≤ log_2(1+\sqrt{5}) - 1 ≈ 0.694\]
把不等号方向颠倒还可以得到$$$F_n ≤ 2^{0.694n}$$$，故$$$F_n = Θ(2^{0.694n})$$$。
故事并没有结束，注意到算$$$F_n$$$需要知道$$$F_{n-1}$$$和$$$F_{n-2}$$$，而$$$F_{n-2}$$$在算$$$F_{n-1}$$$时已经算过一次。如果我们把计算结果都存上(memorization)，完全可以在线性时间内求解。更进一步，存储整个数列是否必要，我们需要的只不过是最后两项啊。由此可以得到自底向上版本（动态规划？）：
def fib(n)
fn_1, fn_2 = 0, 1
(1..n).each {
fn_1, fn_2 = (fn_1 + fn_2), fn_1
}
fn_1
end
p fib 7 # >> 13
都$$$O(n)$$$了，但故事还没有结束。你可能知道 Fibonacci 数列有个解析解（就是一个直接计算，不用递归的公式）：
$$$\sqrt{5}$$$是个无理数，但结果确是整数😱。用浮点肯定会有误差，而且还不知道会不会发散⋯⋯再说就算用符号计算还不是得乘n次，复杂度没降啊。此路不通！
但是，故事还是没有结束。
虽然只是换了种写法，但世界因此不同o。谁说幂运算是线性的！看好了，$$$2^4 = (22)2 = 4^2 = 16$$$可只用了两次（准确的说是⌈log2 4 ⌉次）乘法！
def matrix2_2_times(a, b)
[[a[0][0]*b[1][0] + a[0][1]*b[1][0],
a[0][0]*b[0][1] + a[0][1]*b[1][1]],
[a[1][0]*b[0][0] + a[1][1]*b[1][0],
a[1][0]*b[0][1] + a[1][1]*b[1][1]]]
end
def matrix_power(a, n)
return a if n == 1
m = matrix_power(a, n/2)
if n % 2 == 0
pow = matrix2_2_times(m, m)
else
pow = matrix2_2_times(a,
matrix2_2_times(m, m))
end
pow
end
u = [[0, 1], [1, 1]]
matrix_power(u, 6) # => [[6, 8], [8, 13]]
复杂度是$$$O(log n)$$$！
故事该结束了吧⋯⋯还没有。
是，我们只用了$$$O(log n)$$$次加法和乘法，但当数项不断增大，加法和乘法都不能在在常数时间内完成。时间复杂度的下限到底是多少？这个正在看😓
P.S. 学算法最痛快就是看着别人一点点改进（比如《编程珠玑》里提到的对N体问题的改进），就像看 Harry Potter 一点点长大；
P.P.S 学算法最痛苦就是学了却不知道别人怎么想出来的⋯⋯
P.P.P.S 故意把小 Ron 弄掉的，邪恶吧o
