如何分析含嵌套for循环函数的时间复杂度？附代码及疑问

待分析函数代码 #

Code(n){
    val = n;
    int i = 1;
    for(i < n²; i++){
        for(j=1301; j<1922; j++){
            val = val * val * val;
            for(int k=i; k<i²; k++){
                val = val * k;
            }
        }
    }
}

（注：原代码中n^2、i^2应为平方运算，此处修正为n²、i²以增强可读性）

此前的复杂度分析内容 #

i 1 to n^2 is O(n^2)
j 1301 to 1922 is O((n-1)^2*621)
val*val*val is O((n-1)*620)
k i to i^2 is O((n-1)*620*i^2)
val*k is O((n-1)*620*(i-1)^2)

技术疑问 #

该函数的时间复杂度是否为O(n²)？此结论是否正确？是否可以忽略所有量级低于n²的项？

解答 #

首先明确：结论“时间复杂度为O(n²)”完全错误，下面逐层拆解分析：

1. 最外层循环：i从1到n²-1，循环次数确实是O(n²)，这是此前分析唯一正确的点。
2. 中间层循环：j的范围是1301到1921，总次数是1922-1301=621次——这是个固定常数，和n无关，所以是O(1)量级，此前分析把它和n关联完全错误。
3. 最内层循环：k从i到i²-1，循环次数约为i²（忽略低阶项i），也就是O(i²)。这里i的最大值是n²，需要计算所有外层循环中内层的总执行次数：
   对i从1到n²求和i²，根据平方和公式，结果约为(n²)³/3 = n⁶/3，也就是O(n⁶)量级。
4. 常数时间操作：val=val*val*val是单次运算，属于O(1)，总执行次数是n²*621，即O(n²)，和O(n⁶)相比完全可以忽略。

综上，整个函数的时间复杂度由最内层循环主导，为O(n⁶)。

关于是否可以忽略低量级项：时间复杂度分析中，我们只保留最高阶的项，低阶项可以忽略，但前提是存在更高阶的项。这里的问题不是忽略低量级项，而是此前分析完全错误地计算了各层循环的量级，把常数当成了和n相关的项，还漏算了内层循环的求和量级。

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