algorithm - 如何证明嵌套 forloop 的操作次数的下限

Question

下面我尝试显示算法执行的加法次数的下限。请告诉我我的分析是否正确。

这是一个低效算法，用于计算具有 n 个元素的数组 A 的所有 i,j i < j 的连续和

for i=1 to n
  for j = i+1 to n
    B[i,j] = 0
    for i < j: 
      B[i,j] += A[i,j]
return B

我认为该算法至少需要 n^3 次操作。这是我的论点:

1. 从外部 forloop 进行 n 次迭代
2. 如果 i = n\2 则内部 forloop 将迭代至少 n/2 次
3. 如果 i=n/2 且 j=n 则至少需要 n/2 次加法才能对 i 到 j 的元素求和

因此该算法执行 n * n/2 * n/2 = (n^3)/4 次操作。

Answer 1

很接近，但您的证明并不能完全证明您想要的。你说:

1. n iterations from outer forloop

好的，所以至少 Ω(n)

2. If i = n\2 then the inner forloop will iterate at least n/2 times

当然，但 i = n/2 仅一次迭代，因此这证明总共只有 n/2 次迭代...再次至少 Ω(n)

3. if i=n/2 and j=n then it will take at least n/2 additions to sum up the elements from i to j

是的，但同样这些条件只会发生一次，所以这只会再次证明 Ω(n)。

你想要的证明是这样的:

1. 外循环至少有 n/2-1 次迭代，其中 i < n/2
2. 在每一次迭代中，n-i >= n/2，并且内部循环运行了那么多次迭代，因此至少有 (n/2)(n/2 - 1) 内部循环的迭代。
3. 至少一半的内部循环迭代——特别是至少 (n/4)(n/2 - 1) - 1 迭代——总和至少 n/4 个元素，因此需要添加 n/4 - 1 个元素。

所以至少有 ( (n/4)(n/2-1) - 1 )(n/4 - 1) 次加法，也就是 Ω(n ^3)