最坏情况时间复杂度分析伪代码 [英] Worst case time complexity analysis pseudocode
问题描述
有人能帮我分析这个伪代码的时间复杂度吗?我在这里寻找最坏情况的复杂性,我不知道它是 O(n^4)、O(n^5) 还是其他完全不同的东西.如果您能详细说明您是如何解决它的,我们将不胜感激.
Could someone help me out with the time complexity analysis on this pseudocode? I'm looking for the worst-case complexity here, and I can't figure out if it's O(n^4), O(n^5) or something else entirely. If you could go into detail into how you solved it exactly, it would be much appreciated.
sum = 0
for i = 1 to n do
for j = 1 to i*i do
if j mod i == 0 then
for k = 1 to j do
sum = sum + 1
推荐答案
第一次循环:O(n)
第二个循环:i
平均为 n/2
,你可以有一个精确的公式,但它是 O(n²)
Second loop: i
is in average n/2
, you could have an exact formula but it's O(n²)
第三个循环在第二个循环内发生 i
次,所以平均 n/2
次.它也是 O(n²)
,估计它.
Third loop happens i
times inside the second loop, so an average of n/2
times. And it's O(n²)
as well, estimating it.
所以它是O(n*n²*(1 + 1/n*n²))
,我会说O(n^4)
.1/n
来自这样一个事实,即第三个循环在第二个循环内发生了大约 1/n
次.
So it's O(n*n²*(1 + 1/n*n²))
, I'd say O(n^4)
. The 1/n
comes from the fact that the third loop happens roughly 1/n
times inside the second one.
这只是一个大概的估计,没有严格的证据,但应该是正确的.您可以通过自己运行代码来确认.
It's all a ballpark estimation, with no rigorous proof, but it should be right. You could confirm it by running code yourself.
这篇关于最坏情况时间复杂度分析伪代码的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!