最坏情况下的时间复杂度分析伪code [英] Worst case time complexity analysis pseudocode

问题描述

有人能帮助我，让我这个伪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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！