外层线性内层对数循环的时间复杂度分析：O(logn)还是O(nlogn)？

先看这段代码：

int i=1; 
while (i<= n) { 
   int j = i; 
   while (j > 0) { 
      j = j/2;
   } 
   i++;  
}

结论：时间复杂度为O(nlogn) #

详细分析： #

1. 外层循环执行次数：i从1递增到n，共执行n次。
2. 内层循环执行次数：对于每个i，内层循环中j从i开始不断除以2，直到j ≤ 0。内层循环的执行次数等于i的二进制位数，也就是⌊log₂i⌋ + 1，这个量级是O(logi)。
3. 总执行次数：把每个i对应的内层循环次数累加，得到总次数为Σ（i=1到n）O(logi)，也就是log1 + log2 + log3 + ... + logn = log(n!)。

根据斯特林公式，log(n!) ≈ nlogn - n + O(logn)，显然这个结果的主导项是nlogn，因此总时间复杂度是O(nlogn)。

对O(logn)论点的澄清： #

认为复杂度是O(logn)的错误在于混淆了“单次循环的最大复杂度”和“总复杂度”。内层循环单次的最大次数是O(logn)（当i=n时），但外层循环执行了n次，总次数是n个对数项的累加，而非取单次的最大值，因此不能简化为O(logn)。

内容的提问来源于stack exchange，提问作者Silidrone