有人能帮我分析这个伪代码的时间复杂度吗?我在这里寻找最坏情况的复杂性，我不知道它是 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.