Order of growth as worst case running time as a function of N
Given the following code fragment:
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++;
My assumption:
Hence, total running time should be O(N^5), right?
A preliminary remark
sum(k=1,p,k^2) = p(p+1)(2p+1)/6 = O(p^3)
sum(k=1,p,k^6) = O(p^7)
Computation of complexity
k=1
to j^2
so it does exactly j^2
operations. j=1
to i^2
and at each step we do j^2
operations. According to my preliminary observation, by substituting p=i^2
in the first equation, we can compute the total operations as: i^2(i^2+1)(2*i^2+1)/6
for each value of i
. This is an O((i^2)^3) = O(i^6)
number of operations. i=1
to n
and does O(i^6)
operations at each step. So we have O(n^7)
operations. References
Lets open up how many times every loop will run.
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
So, i think the complexity should be N^4
EDIT 1
Based on a comment, i think the complexity will be sum of the series
1, 16, 81, 256, 625, ...., ( (N*N)*(N*N) )
EDIT 2
I think we made a mistake in opening the loops (Thanks to CodeYogi). Lets try one more time.
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..........
I think that the final O is definitely higher then O(n^4)
and slightly higher then O(n^5)
, but since this is Big O notation, we can say that it is O(n^5) . Last loop will execute this amount of times:
1 + 2^4 + 3^4 + 4^4 + ... + n^4
Wolframalpha represents it as:
Please note expanded version for n>0
:
Edit:
I just realized, that there is a gap in my answer, cause most inner loop will be executed more times than I assumed. Looking at results of this triple loop and plotting it, it seems it is higher than O(n^6)
. Will get back to it.
Edit 2: As I mentioned, I was wrong. Cannot explain it better than @fjardon in his answer.
链接地址: http://www.djcxy.com/p/87634.html上一篇: 流中的地图元素对应于帖子
下一篇: 作为最坏情况运行时间的增长顺序是N的函数