算法复杂度分析：求解程序的上界和下界

算法复杂度分析：求解程序的上界和下界

程序代码：

k=0
for i= 1 to n do
m =[n/i]
for j =1 to m do
k=k+1
return k

上界分析：

外层循环执行n次，内层循环执行m次，其中m=[n/i]，即每次内层循环执行的次数是不同的。

• 当i=1时，m=n，内层循环执行n次；
• 当i=2时，m=[n/2]，内层循环执行[n/2]次；
• 当i=3时，m=[n/3]，内层循环执行[n/3]次； ...
• 当i=n时，m=[n/n]=1，内层循环执行1次。

因此，程序总共执行的次数为n+[n/2]+[n/3]+...+1，其中[]表示向下取整符号。

根据调和级数的性质，该式的上界为O(nlogn)。

下界分析：

程序中的每个语句都只执行一次，因此下界也是Ω(nlogn)。