第一段伪代码分析 #

先把你的伪代码贴出来：

j = 1 
while j < n: 
    k = 2 
    while k < n: 
        k = k*k 
    j++

你原来的思路是外层循环执行n次，内层循环增量步长本质每次减半，得出复杂度O(n log n)，这个思路偏差确实有点大哦。咱们拆解来看：

• 外层循环：j从1开始每次加1，直到j >=n，所以外层循环次数是**O(n)**没错。
• 内层循环：k初始是2，每次执行k = k*k，也就是平方增长。比如n=1000的话，k的变化是2→4→16→256→65536（这时候已经大于1000了），总共只执行了4次。这个次数的计算是找最小的m，使得2^(2^m) ≥n，解出来m是O(log log n)，而不是你以为的O(log n)——这是因为平方增长比线性减半的增速快得多，循环次数是双重对数级别的。

所以第一段伪代码的总时间复杂度是O(n log log n)，不是O(n log n)。

第二段伪代码分析 #

你的伪代码如下：

for i = 1 to n: 
    for j = 1 to n: 
        k = j*j 
        while k < n: 
            k++

你认为复杂度是O(n² log n)，这个理解是不正确的，咱们仔细算一遍：

• 外层和中间层循环：i从1到n，j从1到n，看起来是n²次迭代，但大部分迭代里内层循环根本不会执行。
• 内层循环的执行条件是j*j <n，也就是j < √n。当j >=√n时，k =j*j已经大于等于n，while循环直接跳过。
• 对于j <√n的情况，内层循环的次数是n - j*j，咱们把这些次数加起来：
  sum_{j=1到√n-1} (n - j²) ≈ n*√n - sum(j²)
  其中sum(j²)从1到√n的量级是(√n)^3 =n^(3/2)，所以整个和的量级是O(n^(3/2))，远小于你说的O(n² log n)。

所以第二段伪代码的时间复杂度是O(n^(3/2))，不是O(n² log n)。

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