代码时间复杂度疑问：自算O(nlogn)为何与答案O(n)不符？

先看你给出的代码：

count = 0

for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;

你的错误核心在于错误假设内层循环每次都执行n次，但实际上外层循环的变量i是每次除以2递减的，内层循环的执行次数随i的变化而变化，需要把每次内层循环的执行次数相加来计算总操作数。

具体计算过程 #

外层循环中，i的取值依次是n, n/2, n/4, ..., 1（直到i变为0时停止），对应的内层循环执行次数分别是n, n/2, n/4, ..., 1。这是一个首项为n、公比为1/2的等比数列，求和公式为：
$$
S = n + \frac{n}{2} + \frac{n}{4} + ... + 1
$$

根据等比数列求和公式，当项数足够多（n趋近于无穷大）时，这个和的极限是2n——因为：
$$
S = n \times \frac{1 - (1/2)^k}{1 - 1/2}
$$
其中k是项数（约为$\log_2 n$），当n趋向无穷大时，$(1/2)^k$趋近于0，所以$S \approx 2n$。

时间复杂度关注的是渐近增长趋势，常数系数2可以忽略，因此总时间复杂度是$O(n)$。

再澄清你的误解 #

外层循环确实执行$\log_2 n$次，但内层循环的执行次数不是固定的n，而是每次减半。如果直接用外层次数乘内层最大次数（$\log_2 n \times n$），就会错误得到$O(n\log n)$，但这不符合实际的总操作数计算逻辑——时间复杂度的计算需要统计实际执行的总操作次数，而非循环层数的简单乘积。

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