此代码的时间复杂度为 O(n^5) 或 O(n^3) 还是其他？

Question

我在识别这个嵌套循环代码的时间复杂度时遇到了问题。我的一些朋友说 O(n^3) 和 O(n^5)。

sum = 0;

for(int i=0; i<n; i++)

        for(int j=0; j<i*i; j++)

                for(int k=0; k<j; k++)

                       sum++;

Answer 1

我会说时间复杂度约为 N * (N*N)/2 * N/2。结合起来就是 O(N^4).

编辑：它是O(N^5)因为内部循环被中间循环平方！

但是不要相信我的话。对于这类问题，你为什么不运行几个不同 N 的代码示例并比较 sums，你很快就会弄清楚时间复杂度是多少够了。

Answer 2

WolframAlpha 给出 sum 的增量总数，如

sum_(i=0)^(n-1)( sum_(j=0)^(i^2 - 1)( sum_(k=0)^(j-1) 1))
= 1/20 (n - 2) (n - 1) n (n + 1) (2 n - 1)
= n^5/10 - n^4/4 + n^2/4 - n/10

在θ(n^5)中。

Will this code have Time Complexity O(n^5) or O(n^3) or anything else?