这个程序上界和下界怎么求？时间复杂度问题

考虑外层循环循环了n次，第i次内层循环循环了⌊n/i⌋次，因此时间复杂度为

O(n+n/2+n/3+n/4+...+n/n)=O(n(1+1/2+1/3+1/4+...+1/n))

根据调和级数的知识，由欧拉得到的结论：1+1/2+1/3+1/4+...+1/n=ln(n)+γ，其中γ为欧拉常数，近似值为γ≈0.57721。

因此我们逗猜可以得出御指御程序的时间复镇岩杂度为

O(n ln n+nγ)

考虑到γ十分小，ln n=log_e n，其中e≈2.7≈2，因而程序的渐进时间复杂度约为O(nlogn)。

简单一点，忽略诸如程序在循环变量上的开销，只考虑循环体

复杂度是通过数运算次数直接数出来的，要知道循环多少次，以及每次循环的工作量

(1)循环n次，每次两步加法两步赋值，简单一点讲就是每次循环工作量都是常数，所以复杂度就是Θ(n)（既是上界也是下界）

对于(2)而言，n=n-1下降比较慢，n=n/2下降比较快，芹蚂同样每次循环的工作量都是常数，只要看循环次数，所以从前者去统计上界，从后者统计下界

最少的情况来自n=2^k的形式，要循环k步肆首磨，复杂度下界是Ω(log n)

循环次数比较多的情况是反复出现n=n-1运算的情况，但注意一旦执行该运算之裂斗后n一定变成偶数，所以最坏情况是n=n-1和n=n/2交替出现，此时循环次数不超过2log_2 n，复杂度上界是O(log n)

合并起来总体的复杂度还是Θ(n)

汗～～楼上的．．．．．．

不说了．．．一看就知道没学过数据结构

程序的算法效伍耐率 看原 *** 作重复执行的次数．．．．

你写的这个算法时间复杂度是常量级的．．．

当n<=1时，循环0次．

n>1时，分两种情况．1．旁橘磨n是奇数．循环循运斗环两次．2．n是偶数，循环1次

所以时间的上界是2,下界是0

---