为什么这个算法的运行时间是(n^2)*(n^2 + 1)/2(即O(n/4))？

Question

所以，我的导师给我们的一个问题让我们找到了这个算法的运行时间：

{n > 0}
    i := 1;
    while i ≤ n^2
    j := 1;
    while j ≤ i
        j := j + 1;
    endwhile
    i := i + 1;
endwhile

在解决方案中，这里的运行时间是 n^2(n^2 + 1)/2, 即 Θ(n^4).

所以，我知道第一个 while 循环的运行时间是 n^2，但为什么第二个循环的运行时间是 (n^2 + 1)/2。

在此先感谢您的帮助。

Answer 1

第二个循环执行了 i 次。

因此，如果 i 从 1 变化到 n^2，则运行时间为

1 + 2 + 3 + ... + n^2

请注意

1 + 2 + ... + k = k*(k+1)/2

因此，如果您将 k 替换为 n^2，您将获得 n^2*(n^2+1) 中的运行时。我想正确的身份是：

{n > 0}
    i := 1;
    while i ≤ n*n
      j := 1;
      while j ≤ i
        j := j + 1;
      endwhile
      i := i + 1;
endwhile

Why is the runtime of this algorithm (n^2)*(n^2 + 1)/2(i.e. O(n/4))?