作为N的函数的最坏情况运行时间的增长顺序

Question

给出以下代码片段:

int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i*i; j++)
        for (int k = 1; k <= j*j; k++)
            sum++;

我的假设:

• 外环:O(N)
• 中环:O(N*N)
• 最内圈:O(N*N)

因此,总运行时间应为O(N ^ 5),对吧？

Answer 1

初步评论

sum(k=1,p,k^2) = p(p+1)(2p+1)/6 = O(p^3)
sum(k=1,p,k^6) = O(p^7)

复杂度计算

1. 最内层循环从k=1到运行j^2，因此它执行精确的j^2操作。
2. 中间的循环从j=1到运行i^2，并且在每一步我们都进行j^2操作。根据我的初步观察，通过代入p=i^2第一个方程，我们可以将总操作计算为：i^2(i^2+1)(2*i^2+1)/6对于 的每个值i。这是O((i^2)^3) = O(i^6)一些操作。
3. 外循环从i=1到运行n，并O(i^6)在每一步执行操作。所以我们有O(n^7)行动。

参考

• http://www.math.com/tables/expansion/power.htm