为何给定代码时间复杂度为O(n)而非O(n*log(n))？

首先要明确：如果外层循环真的每次都完整执行n次内层循环，那时间复杂度必然是O(nlogn)。你遇到的O(n)情况，一定是内层循环的执行次数和外层循环的迭代变量强相关，累加后的总操作量是线性的。

最典型的场景是外层循环以倍数递增（比如每次乘2），内层循环的执行次数随外层变量的增大而反比例减少，比如下面这段代码：

n = 1024
i = 1
while i <= n:
    # 内层循环执行次数为 n//i 次
    for j in range(n // i):
        print("操作")
    i *= 2

我们来计算总操作次数：

• 第一次外层循环（i=1）：内层执行n次
• 第二次（i=2）：内层执行n/2次
• 第三次（i=4）：内层执行n/4次
• ...
• 最后一次（i=n）：内层执行1次

总次数就是：n + n/2 + n/4 + ... + 1

这是一个首项为n、公比为1/2的等比数列求和，根据等比数列求和公式，总和为 n*(1 - (1/2)^k)/(1 - 1/2)，其中k是外层循环次数（k=log₂n）。当n趋近于无穷大时，(1/2)^k趋近于0，总和趋近于2n，属于O(n)的量级。

简单来说，虽然外层循环跑了logn次，但内层循环的执行次数是递减的，总工作量并没有达到n*logn，而是被压缩到了线性级别。

如果你的代码不是这种情况，那大概率是对循环次数的统计有误——比如内层循环里有提前break的逻辑，导致实际执行次数远小于n，或者外层循环的迭代次数并不是严格的logn。

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