最坏情况时间复杂度分析伪代码
Worst case time complexity analysis pseudocode
谁能帮我分析一下这个伪代码的时间复杂度？
我在这里寻找最坏情况下的复杂性，但我无法弄清楚它是 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
第一个循环：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 次。
这都是大概的估计，没有严格的证据，但应该是正确的。您可以通过 运行 代码自己确认。
谁能帮我分析一下这个伪代码的时间复杂度？ 我在这里寻找最坏情况下的复杂性，但我无法弄清楚它是 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
第一个循环：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 次。
这都是大概的估计，没有严格的证据，但应该是正确的。您可以通过 运行 代码自己确认。