2.6 对于下列六个程序片段中的每一个

分析

前面几题通过观察可以很简单的得出结论。

（5）

对于（5）的理解可以参见下图。

（6）

（6）的理解见下图


对于第二句“实际上因为 i*i 个 j 的取值中只有 i 个使 if 语句为真”，我们可以这样理解：

• 不严格的说，在 1-100 中，是二的倍数的数有 100/2 个
• 是3的倍数的数有 100/3 个
• 所以对于 1~ii 范围中，是 i 的倍数的数有 ii/i 也就是 i 个， 只有 i 个使得 if 语句为真。

参考：数据结构与算法习题讲解(全)解析（第八页）
第1-6章中文版答案.pdf

估计的复杂度的正确性检查

根据 第二章 检验复杂度分析的正确性 中介绍的第二种方法，我们编写代码来进行估计的复杂度的正确性检查。

import time
import math
sum=0
n=1
while(n):
    start_time=time.time()
    n=input("请输入n的值:")
    n=int(n)
    for i in range(1,n):
        for j in range(1,n**2):
            if j%i==0:
                for k in range(j):
                    sum=sum+1
    print("sum=",sum)
    end_time=time.time()
    tn=end_time-start_time
    tn*=10000 # 为了方便观察商的变化趋势，扩大被除数。
    print("T(n)=",tn)
    print("n=",n)
    print("T(n)/n^2=",tn/(n**2))
    print("T(n)/n^3=",tn/(n**3))
    print("T(n)/n^4=",tn/(n**4))
    print("T(n)/n^5=",tn/(n**5))
    print("T(n)/n^2logn",tn/((n**2)*math.log(n)))

受限于机器的运算速度，n只能输入10,20,30,…（太大很长时间出不来结果）。
我们可以发现 print("T(n)/n^4=",tn/(n**4)) 的结果呈现收敛态势，符合预期。