嵌套循环时间复杂度疑问：内层循环从i开始减半执行

首先给出待分析的嵌套循环代码：

for ( i = 1; i <= n; i++) {
   for ( j = i; j >= 1; j = j / 2) {
     // 常数时间操作
   }
}

你的推导问题出在哪？ #

你对内层循环执行次数的计算是对的：内层循环次数确实是⌊log₂i⌋ + 1（比如i=1时执行1次，i=2时执行2次，i=4时执行3次），求和公式(log1+1)+(log2+1)+...+(logn+1)也没问题，但你错误地把这个和的复杂度推导成了O(n²)。

正确的复杂度推导 #

把求和公式拆成两部分：

• 第一部分：log1 + log2 + ... + logn，这等价于log(1×2×3×...×n) = log(n!)
• 第二部分：1+1+...+1（共n个1），和为n

根据斯特林公式，log(n!)的渐近增长速度是O(nlogn)，而第二部分的n是O(n)，远慢于O(nlogn)。所以整体求和的主导项是O(nlogn)，整个嵌套循环的时间复杂度就是O(nlogn)。

为什么另一种解法（内层次数算logi）结果也对？ #

渐近复杂度分析里，常数项可以忽略。⌊log₂i⌋ +1和⌊log₂i⌋的渐近增长速度是一样的，都是O(logi)，所以不管用哪个来求和，最终的复杂度都是O(nlogn)，只是具体的常数项不同，但渐近复杂度只看主导项。

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