渐近分析疑问：为何嵌套循环时间复杂度是O(n)而非O(nlogn)？

你之前的错误在于默认外层循环次数和内层单次循环次数直接相乘，但实际上循环的总执行次数是每一轮内层循环的次数之和，而非乘积，这是关键区别。

举个对应你问题的典型代码示例：

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

我们来逐轮计算内层循环的执行次数：

• 第一轮i=1，内层循环执行n-1次，约等于n；
• 第二轮i=2，内层循环执行n-2次，约等于n/2；
• 第三轮i=4，内层循环执行n-4次，约等于n/4；
• ...
• 最后一轮i接近n时，内层循环仅执行1次。

把这些次数加起来，总和是：
n + n/2 + n/4 + ... + 1 = 2n - 1

根据渐近复杂度的规则，我们只保留最高阶项，忽略常数系数和低阶项，所以总复杂度是O(n)。

而你之前误以为每次内层都执行n次，所以用外层的logn次乘以n得到O(nlogn)，但这里内层循环的次数是随着外层循环变量递增而递减的，总次数是线性求和，而非乘积，因此logn对应的项属于低阶项，会被舍弃。

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