作为最坏情况运行时间的增长顺序是N的函数
给定以下代码片段：
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^2(i^2+1)(2*i^2+1)/6 i 。 这是一个O((i^2)^3) = O(i^6)个操作。 i=1运行到n ，并在每个步骤执行O(i^6)操作。 所以我们有O(n^7)操作。 参考
让我们打开每个循环运行多少次。
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 ^ 4
编辑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..........
我认为最后的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更好地解释它。
链接地址: http://www.djcxy.com/p/87633.html上一篇: Order of growth as worst case running time as a function of N
下一篇: Changing the row background color of a QTreeView does not work