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

Question

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

7

以下是代码片段：

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)，对吗？

- CodeYogi

大多数内部循环不是O(N^2 * N^2)吗？ - Michał Szkudlarek

2

该死，答案是：N^7。对于给定的i值，最内层循环的主体被执行1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~ 1/3 i^6次。对所有i值求和得到 ~ 1/21 N^7。 - CodeYogi

你是对的。复杂度将会是O(n^5)。 - vish4071

3个回答

1

我认为最终的O肯定高于O(n^4)，略高于O(n^5)，但由于这是大O符号，我们可以说它是O(n^5)。最后一个循环将执行这么多次：

1 + 2^4 + 3^4 + 4^4 + ... + n^4

"

Wolframalpha 表示为：

"

请注意，对于 n>0，有扩展版本：

编辑：

我刚意识到，我的回答中存在一个漏洞，因为大多数内部循环将被执行的次数比我预计的要多。查看这个三重循环的结果并绘制它，似乎它比O(n^6)更高。会回头解决。

编辑2： 正如我提到的，我错了。无法比@fjardon在他的answer中更好地解释。

- Michał Szkudlarek

1

让我们打开每个循环将运行多少次。

First loop    1, 2,   3,   4,   5,  ...., N
Second loop   1, 4,   9,  16,  25, ...., (N*N)             // N^2
Third loop    1, 16, 81, 256, 625, ...., ( (N*N)*(N*N) )   // N^4

所以，我认为复杂度应该是N的四次方。

编辑1：

根据评论，我认为复杂度将是一系列的总和。

1, 16, 81, 256, 625, ...., ( (N*N)*(N*N) )

编辑2

我认为我们在打开循环时犯了一个错误（感谢CodeYogi）。让我们再试一次。

First loop    1, 2,   3,   4,   5,  ...., N
Second loop   1,  4(1,2,3, 4), 9  (1,2,....9),  16,  25, ...., (N*N)  
Third loop    1, 30(1+4+9+16), 285(1+4+...81), and so on..........

- Haris

2

我认为运行时间应该是序列 1 + 16 + 81 ... + (N*N) * (N*N) 的总和，你觉得呢？ - CodeYogi

按照类比，1 + 2 + 3 ~ O(N^2)，1 + 4 + 9 ~ O(N^3)，因此上述解决方案应该是O(N^5)，对吗？ - CodeYogi

复杂度为O(n^5)。我不知道你错误的答案是如何获得3个赞的（因为你说复杂度是O(n^4)）。 - vish4071

@haris，我认为我们错了，我们的思维方式存在严重问题。应该是~O(N^7)。 - CodeYogi

请参考上面fjardon的答案。我已经确认这是解决类似嵌套积分问题的最准确方法。 - CodeYogi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fjardon · Accepted Answer

初步说明

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

复杂度计算

最内层循环从k=1到j^2运行，因此恰好执行j^2次操作。
中间循环从j=1到i^2运行，在每个步骤中我们执行j^2次操作。根据我的初步观察，通过在第一个方程式中替换p=i^2，我们可以计算出每个i值的总操作数为：i^2(i^2+1)(2*i^2+1)/6。这是一个O((i^2)^3) = O(i^6)次操作。
外部循环从i=1到n运行，并在每个步骤中执行O(i^6)次操作。因此我们有O(n^7)次操作。

参考资料

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