嵌套依赖型for循环的Big O表示法一定是O(n²)吗？

哈哈，这绝对是个容易踩的误区！答案显然是否定的——嵌套且依赖外层变量的for循环，时间复杂度并不总是O(n²)，关键得看内层循环的迭代次数和外层循环变量的具体依赖关系。下面举几个典型例子帮你理解：

1. 确实是O(n²)的情况 #

当内层循环的迭代次数和外层变量成线性正相关时，总次数的增长是平方级的。比如最经典的“三角遍历”：

n = 100
for i in range(n):
    # 内层循环次数随i线性增加
    for j in range(i):
        do_something(i, j)

总迭代次数是 1 + 2 + 3 + ... + (n-1) = n(n-1)/2，渐近上界就是O(n²)，这也是大家最常见的嵌套循环场景。

2. 复杂度为O(n)的嵌套循环 #

如果内层循环的迭代次数增长速度远慢于外层，甚至总次数累加后是线性的，那复杂度就不是平方级了。比如外层循环变量按指数增长，内层循环次数等于当前外层变量：

import math
n = 100
i = 1
while i <= n:
    # 内层循环次数等于当前i值
    for j in range(i):
        do_something(j)
    # 外层变量指数级增长
    i *= 2

总迭代次数是 1 + 2 + 4 + 8 + ... + 2^k（其中2^k ≤n），这个等比数列的和是 2^(k+1)-1 ≈ 2n，所以时间复杂度是O(n)，完全和平方级不沾边。

3. 复杂度为O(n^(3/2))的嵌套循环 #

再比如内层循环次数是外层变量的平方根：

import math
n = 100
for i in range(n):
    # 内层循环次数是sqrt(i)
    for j in range(int(math.sqrt(i))):
        do_something(j)

总迭代次数是 sum(sqrt(i)) 从i=0到n-1，用积分近似的话，这个和大概是 (2/3)n^(3/2)，所以渐近复杂度是O(n^(3/2))，也不是O(n²)。

核心判断逻辑 #

其实不管循环怎么嵌套，判断时间复杂度的核心都是计算所有循环迭代的总次数，然后看这个总次数随n增长的渐近趋势。不能看到“嵌套依赖”就直接默认是O(n²)，得具体分析内层和外层变量的依赖关系，把总次数的表达式推导出来，再取上界。

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