昨天关于分治算法中有一点没有提到，就是算法的时间复杂度到底意味着什么呢？在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，是不是觉得自己很流弊啊？有种你们是大学霸的错觉。

最后，欢迎扫码关注微信公众号。程序员同行学习交流，聊天交友，国内外名企求职内推（微软 / 小冰 / Amazon / Shopee / Coupang / ATM / 头条 / 拼多多等），可加我微信 jzj2015 进技术群（备注进技术群，并简单自我介绍）。

本文由tofulee原创，转载请注明来源：https://www.paincker.com/algorithm-2
（标注了原文链接的文章除外）