您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

算法设计策略之分治(补充)

编程 332℃ 1 3年前 (2014-12-21)

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

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

1

评论1条

  1. win 回复

    错觉

评论前:需填写以下信息,或 登录

用户登录

忘记密码?