双层循环调整循环上限后的时间复杂度是O(n³)还是O(n⁴)

你给出的代码如下：

for(long i = 1; i < n*n; i++)
{
    for(long j = 1; j < i * i; j++)
    {
        //some code  
    }
}

计算过程 #

• 外层循环变量i的取值范围是1到n²-1，总共有接近n²次外层循环
• 每次外层循环中，内层循环的执行次数等于i²（j从1到i²-1）
• 总操作次数是所有外层循环对应内层次数的和，即求和公式：
  总次数 = Σ（i=1到i=n²）i²
• 自然数平方和的求和公式为Σ（i=1到k）i² = k(k+1)(2k+1)/6，该式的最高阶项为k³/3，因此求和结果的量级为O(k³)
• 此处k等于n²，代入后最高阶项为(n²)³/3 = n⁶/3，因此这段代码的时间复杂度为*O(n⁶)*，既不是你猜测的O(n⁴)也不是O(n³)。

你猜测的两个量级对应的场景 #

你提到的两个量级分别对应另外两种常见的循环修改方案：

• 若外层循环上限为n，内层循环上限为i²：求和式为Σ（i=1到n）i² = O(n³)，就是你说的三次方量级
• 若外层循环上限为n²，内层循环上限为i：求和式为Σ（i=1到n²）i = O((n²)²) = O(n⁴)，就是你说的四次方量级

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