算法练习(59): 增长数量级(1.4.6)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 增长的数量级
• 等比数列

题目

1.4.6 给出以下代码段的运行时间的增长数量级(作为N的函数)

---

1.4.6 Give the order of growth (as a function of N)of the running times of each of the following code fragments:

a. int sum=0;
    for(int n=N;n>0;n/=2)
        for(int i=0;i<n;i++)
            sum++;
        
 b. int sum=0;
    for(int i=1;i<N;i*=2)
        for(int j=0;j<i;j++)
            sum++;
    
 c. int sum=0;
    for(int i=1;i<N;i*=2)
        for(int j=0;j<N;j++)
            sum++;

分析

增长的数量级我们已经在上一篇文章算法练习(58): 计算量的近似(1.4.5)
中提到过了。

要分析数量级，我们首先要知道程序运行的总时间，主要和这两点有关：
1.执行每条语句的耗时
2.执行每条语句的频率
接下来我们看代码：

a. int sum=0;
    for(int n=N;n>0;n/=2)
        for(int i=0;i<n;i++)
            sum++;

从内循环往外看，是一个等比数列， 1 + 2 + 4 + 8 + ... 外循环总共迭代 floor(logn) + 1 次，因此根据等比数列求和公式，得到 2N - 1 ~ 2N

 b. int sum=0;
    for(int i=1;i<N;i*=2)
        for(int j=0;j<i;j++)
            sum++;

这个跟上一个也一样

c. int sum=0;
    for(int i=1;i<N;i*=2)
        for(int j=0;j<N;j++)
            sum++;

外循环和内循环互不影响，所以数量级是NlgN

关于这道题，国外有个人做了详细的分析，如果读者有兴趣可以看一下：https://softwareengineering.stackexchange.com/questions/253421/running-time-of-simple-for-loops

答案

a. N
b. N
c. NlgN

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。