为何该嵌套循环的时间复杂度为O(n)而非O(n log n)？

首先先把代码贴出来方便分析：

for (int i = 1; i <= n; i *= 2) { 
    for (int j = 0; j < i; j++) { 
        // 常数时间的语句
    } 
}

你的疑惑特别常见——很多人刚接触时间复杂度分析时，都会下意识觉得“外层循环O(logn)次，每次内层O(n)，所以总复杂度是O(n logn)”，但这里的核心误区是：内层循环的执行次数不是固定的O(n)，而是随着外层的i值动态变化的。我们需要把每次内层循环的执行次数累加起来，而不是直接用外层次数乘以内层的“最大次数”。

让我们一步步拆解总执行次数：

• 第一次外层循环：i=1，内层执行1次
• 第二次外层循环：i=2，内层执行2次
• 第三次外层循环：i=4，内层执行4次
• ...
• 最后一次外层循环：i是小于等于n的最大2的幂，假设为2^k，满足2^k ≤ n < 2^(k+1)

把这些次数加起来，就是一个首项为1、公比为2的等比数列求和：
1 + 2 + 4 + ... + 2^k

根据等比数列求和公式，这个总和等于2^(k+1) - 1。而因为2^k ≤ n，所以2^(k+1) ≤ 2n，总和也就≤2n - 1。也就是说，总执行次数始终是**O(n)**级别的，远小于n logn的量级。

举个实际例子验证：

• 当n=8时，总和是1+2+4+8=15，刚好等于2*8-1
• 当n=10时，总和是1+2+4+8=15，远小于2*10=20

所以不管n多大，总执行次数都不会超过2n，时间复杂度自然是O(n)，而非O(n logn)。

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