昨天关于分治算法中有一点没有提到，就是算法的时间复杂度到底意味着什么呢？在fiboccina数列的例程中，算出来时间复杂度是2^n,也就是说随着输入规模n的增长，运行耗费的时间越多。一个算法的时间复杂度是非常重要的。对于这样的算法我们必须要对其进行优化。观察一下它的式子f(n) = f(n – 1) + f(n -2) 得出 f(n – 1) = f(n – 2) + f(n – 3)，于是我们发现我们对同一个问题进行了多次求解,也就是堆f(n – 2)求解了两次。事实上我们求解f(n)的时候，所有比n小的元素都会被重复计算遍，这个画出递归树就会发现，在递归树的叶子上，第n-m个节点出现了m次。也就是它被重新处理了m次，而我们知道这个算法的复杂度是O（2^n），假设常数因子c是1的话，处理m节点1次带开的开销是2^(n – m)，这是不可忍受的！
现在从数学上来看看：
2^n = 2^(n – 1) + 2^(n – 2) + 2^(n – 3) + ……+ 2^0 + 1
2^(n – 1) = 2^(n – 2) + 2^(n – 3) + 2(^n – 4) + …. + 2^0 +1
2^(n – 2) = 2^(n – 3) + 2(n – 4) + 2^(n – 5)…. + 2^0 +1
2^(n – 3) = 2^(n – 4) + 2^(n – 5) + 2^(n – 6)…. + 2^0 +1
…..
代换回去
2^n = 2^(n – 2) + 2^(n – 3) + 2^(n – 4) + 2^(n – 5) …. + 2^0 +1 +
2^(n – 3) + 2(n – 4) + 2^(n – 5) + 2^(n – 6)…. + 2^0 +1 +
2^(n – 4) + 2^(n – 5) + 2^(n – 6 +) +2^(n – 7)…. + 2^0 +1 +
2^(n – 5) + 2^(n – 6) + 2^(n – 7) + 2^(n – 8)…. + 2^0 +1 +
…..
(注意观察左下角到右上角的对角线)
整理得：
2^n = 2^(n – 2) + 2*2^(n – 3) + 3*2^(n – 4) + 4*2^(n – 5) + …. + (m – 1)*2^(n – m) + ….
现在我们可以看到2^(n – m)在式子中出现m – 1次，也就是它被计算机计算了m次。如果我们将一个节点计算一次，然后把结果记录下来，以后需要再次计算的时候就拿出来用。那么每个节点只计算一次整个程序只需要很少次就可以计算完了，这叫做备忘录方法，以后会经常用到。这时候在递归树上的轨迹是一条从根到达某个叶子节点的直线，O（n）。
现在通过程序验证一下，宏MEMO用来控制是否使用备忘录，定义了MEMO就使用备忘录，否则不使用。
当输入规模为1 – 30的时候，不使用备忘录的运行结果：
input : 1 fiboccina : 1 count : 1
input : 2 fiboccina : 1 count : 2
input : 3 fiboccina : 2 count : 5
input : 4 fiboccina : 3 count : 10
input : 5 fiboccina : 5 count : 19
input : 6 fiboccina : 8 count : 34
input : 7 fiboccina : 13 count : 59
input : 8 fiboccina : 21 count : 100
input : 9 fiboccina : 34 count : 167
input : 10 fiboccina : 55 count : 276
input : 11 fiboccina : 89 count : 453
input : 12 fiboccina : 144 count : 740
input : 13 fiboccina : 233 count : 1205
input : 14 fiboccina : 377 count : 1958
input : 15 fiboccina : 610 count : 3177
input : 16 fiboccina : 987 count : 5150
input : 17 fiboccina : 1597 count : 8343
input : 18 fiboccina : 2584 count : 13510
input : 19 fiboccina : 4181 count : 21871
input : 20 fiboccina : 6765 count : 35400
input : 21 fiboccina : 10946 count : 57291
input : 22 fiboccina : 17711 count : 92712
input : 23 fiboccina : 28657 count : 150025
input : 24 fiboccina : 46368 count : 242760
input : 25 fiboccina : 75025 count : 392809
input : 26 fiboccina : 121393 count : 635594
input : 27 fiboccina : 196418 count : 1028429
input : 28 fiboccina : 317811 count : 1664050
input : 29 fiboccina : 514229 count : 2692507
input : 30 fiboccina : 832040 count : 4356586
看到计数count呈指数关系增长。
输入规模为1- 30，使用备忘录：
input : 1 fibociina : 1 count : 1
input : 2 fibociina : 1 count : 2
input : 3 fibociina : 2 count : 5
input : 4 fibociina : 3 count : 7
input : 5 fibociina : 5 count : 8
input : 6 fibociina : 8 count : 9
input : 7 fibociina : 13 count : 10
input : 8 fibociina : 21 count : 11
input : 9 fibociina : 34 count : 12
input : 10 fibociina : 55 count : 13
input : 11 fibociina : 89 count : 14
input : 12 fibociina : 144 count : 15
input : 13 fibociina : 233 count : 16
input : 14 fibociina : 377 count : 17
input : 15 fibociina : 610 count : 18
input : 16 fibociina : 987 count : 19
input : 17 fibociina : 1597 count : 20
input : 18 fibociina : 2584 count : 21
input : 19 fibociina : 4181 count : 22
input : 20 fibociina : 6765 count : 23
input : 21 fibociina : 10946 count : 24
input : 22 fibociina : 17711 count : 25
input : 23 fibociina : 28657 count : 26
input : 24 fibociina : 46368 count : 27
input : 25 fibociina : 75025 count : 28
input : 26 fibociina : 121393 count : 29
input : 27 fibociina : 196418 count : 30
input : 28 fibociina : 317811 count : 31
input : 29 fibociina : 514229 count : 32
input : 30 fibociina : 832040 count : 33
可以看到cout呈线性关系在增长。从4356586优化成了33，是不是觉得自己很流弊啊？有种你们是大学霸的错觉。
最后，欢迎扫码关注微信公众号，也可以加我微信 jzj2015 交流（注明来自博客）。
本文由tofulee原创，转载请注明来源：https://www.paincker.com/algorithm-2
（标注了原文链接的文章除外）
错觉