本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：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壁纸宝贝上线了，欢迎大家下载。
