algorithm - 作为 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