请教函数及代码的时间复杂度：是O(n^3)、O(n^4)还是其他？

安全阿岳

2026-7-1

时间复杂度问题解答

问题1：某函数的时间复杂度是O(n³)还是其他？

由于未提供该函数的具体实现逻辑、核心操作与输入规模n的关联规则，无法直接判定其时间复杂度。需要明确函数内部的循环嵌套、递归逻辑或关键操作的执行规律，才能准确推导时间复杂度的阶。

问题2：以下代码的时间复杂度是O(n³)还是O(n⁴)？

for(int i = 1; i <= n;i++)
{
    for(int j = 1; j <= i*i;j++)
    {
        if( j % i == 0)
        {
            for(int k = 0; k < j;k++){sum++;}
        } 
    }
}

复杂度推导：

外层循环：i从1到n，共执行n次。
中层循环：j从1到i²，但仅当j是i的倍数时（即j = i, 2i, 3i, ..., i²），才会进入内层循环。对于每个i，满足条件的j共有i个（对应k=1到k=i，j=i*k）。
内层循环：每次触发时执行j次，也就是i*k次。对每个i，内层循环的总执行次数为：
```
sum(k=1到i) i*k = i * sum(k=1到i)k = i * [i(i+1)/2] = i²(i+1)/2
```
对所有i从1到n求和，总执行次数的主导项来自i³的求和：
```
sum(i=1到n) i³ = [n(n+1)/2]^2
```
这一项的阶为O(n⁴)，远高于sum(i²)的O(n³)，因此整个代码的时间复杂度为O(n⁴)。