algorithm - 最坏情况时间复杂度分析伪代码

Question

谁能帮我分析这个伪代码的时间复杂度？我在这里寻找最坏情况下的复杂性，但我无法弄清楚它是 O(n^4)、O(n^5) 还是完全不同的东西。如果您能详细说明您是如何解决它的，我们将不胜感激。

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

Answer 1

第一个循环:O(n)

第二个循环:i 平均为 n/2，你可以有一个精确的公式，但它是 O(n²)

第三个循环在第二个循环中发生了 i 次，所以平均 n/2 次。它也是 O(n²)，估计它。

所以它是 O(n*n²*(1 + 1/n*n²))，我会说 O(n^4)。 1/n 是因为第三个循环在第二个循环中大约发生了 1/n 次。

这都是一个大概的估计，没有严格的证据，但应该是正确的。您可以通过自己运行代码来确认。