这段Python嵌套while循环的时间复杂度为何是O(n)而非O(n²)？

参考答案正确，你的分析思路存在误区，这段代码的时间复杂度为O(n)。

你误判为O(n²)的原因，大概率是直接套用了「多层嵌套循环时间复杂度为各层复杂度乘积」的经验，但这个规则成立的核心前提是：各层循环的控制变量相互独立，外层循环每执行一次，内层循环会完整跑完自己的全部迭代周期。
而你给出的代码中，两层while循环共用同一个全局变量i作为控制变量，根本不会触发外层循环的多轮执行，实际执行流程如下：

1. 初始化i = 0，外层循环判断i < n成立，进入循环体
2. 进入内层循环，判断i < n成立，执行打印、i += 1操作
3. 内层循环会持续运行直到i自增到等于n才退出，这一阶段内层循环总共执行了n次迭代
4. 内层循环退出后回到外层循环的判断逻辑，此时i已经等于n，i < n不成立，外层循环直接终止，不会再进入第二轮

统计全流程的基本操作次数：print执行n次，i自增操作执行n次，循环条件判断的次数为常数级，总操作数和输入规模n呈线性关系，因此时间复杂度为O(n)。

只有当两层循环的控制变量相互独立时，嵌套循环才会产生O(n²)的时间复杂度，例如下方代码才是典型的O(n²)实现：

i = 0
while i < n:
    j = 0  # 内层循环使用独立计数器j，每次进入内层都会重置为0
    while j < n:
        print(i, j)
        j += 1
    i += 1

这段代码中外层循环每跑1次，内层循环都会完整执行n次，总迭代次数为n*n = n²，才符合O(n²)的复杂度特征。

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