寻找伪代码的大O

Question

代码如下：

y = 0
for j=0 to n:
  for k=0 to (j*n):
     y+=2

我的逻辑是，给定从 0 到 n 的 i 和的已知解，内部 for 循环将有这个求和，其中 n(n+1)/2:

(j*n)(j*n + 1)/2 #in this case, j*n is what we're summing to

然后，这个内部循环将从 j=0 循环到 n，根据该逻辑，我可以对从 0 到 n 求和：

( (n(n+1)/2) * n)((n(n+1)/2) * n + 1) / 2

我将 j 替换为 (n(n+1)/2)。完成乘法后，我得到

O(n^6)

我不知道我的逻辑是否合理，或者我是否遗漏了什么，因为这个数字似乎很大。谢谢

Answer 1

我们可以进行信封背面计算。

j 的范围从 0 到 n。因此，j 的最高数字是 n。那是内循环的绝对最坏情况。

因此，内循环的绝对最坏情况是 j == n，在这种情况下，循环有 j * n == n * n == n² 次迭代。

意思是，在绝对最坏的情况下，内部循环将有 n² 次迭代。反过来，外循环有 n 次迭代，这意味着我们的 over-estimated，绝对 worst-case 上限是 O(n³)。没有比这更糟的了。事实上，我们通过假设 j * n == n² 得到 over-estimated，所以我们知道它肯定小于 n³.

现在，我们可以尝试找到更精确的界限。事实上，我们可以 actually 找到确切的迭代次数，我们甚至不需要 Bachmann-Landau 符号。

在循环边界互斥的假设下，内层循环中的语句将被执行(n³ - n²) / 2次，y将是n³ - n²。（Wolfram Alpha 说。）

寻找伪代码的大O

Finding the Big O of psuedocode

big-o