问题描述
有人能帮助我,让我这个伪code的时间复杂度分析?我在寻找最坏情况的复杂性在这里,我想不通,如果是为O(n ^ 4),为O(n ^ 5),或别的东西完全。如果你能进入细节研究如何你到底解决了它,这将是更AP preciated。
和= 0
对于i = 1到n做
对于j = 1到i *我做的
如果在j mod我== 0,那么
对于k = 1到j做
总和=总和+ 1
第一个循环: O(N)
第二循环:我
是平均 N / 2
,你可以有一个确切的公式,但它的 O(N²)
三环路发生我
倍的第二循环中,使平均的N / 2
次。而且它的 O(N²)
为好,估计它。
因此,它是 O(N *N²*(1 + 1 / N *N²))
,我会说为O(n ^ 4 )
。该 1 / N
来自该第三循环发生大约 1 / N
时间内的第二个。事实
这都是一个大概的估计,没有严格的证明,但它应该是正确的。你可以通过运行code自己确认。
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
First loop: O(n)
Second loop: i
is in average n/2
, you could have an exact formula but it's 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.
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.
这篇关于最坏情况下的时间复杂度分析伪code的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!