以下是代码片段:
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),对吗?
以下是代码片段:
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^5),对吗?
初步说明
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)
次操作。参考资料
1 + 2^4 + 3^4 + 4^4 + ... + n^4
Wolframalpha 表示为:
" 请注意,对于n>0
,有扩展版本:
编辑:
我刚意识到,我的回答中存在一个漏洞,因为大多数内部循环将被执行的次数比我预计的要多。查看这个三重循环的结果并绘制它,似乎它比O(n^6)
更高。会回头解决。
编辑2: 正如我提到的,我错了。无法比@fjardon在他的answer中更好地解释。
让我们打开每个循环将运行多少次。
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
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..........
1 + 16 + 81 ... + (N*N) * (N*N)
的总和,你觉得呢? - CodeYogi1 + 2 + 3 ~ O(N^2)
,1 + 4 + 9 ~ O(N^3)
,因此上述解决方案应该是O(N^5),对吗? - CodeYogi