sum=0;
for(i=0;i<n;i++)
for(j=0;j<i*i;j++)
for(k=0;k<j;k++)
sum++;
上述程序的时间复杂度是多少？我觉得应该是O(n^4)。有人可以推导出来吗？
最佳答案
假设输入n
for(i=0;i<n;i++) is O(n)
for(j=0;j<i*i;j++) is O(n^2 /2) since depends on i whose value goes from 1 to n (average of 1..2 is n/2).
for(k=0;k<j;k++) is O((n^2 /2) / 2) since depends j goes from 0 to i*i
然后因为它们是嵌套的，所以复杂度是循环复杂度 O(n * (n^2/2) * ((n^2/2)/2)) = O(n^5/8 )
n^5 或 O(n^5) 的顺序
关于algorithm - 这段代码的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40228196/