最坏情况时间复杂度分析伪代码 [英] 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屋！