algorithm - 该算法的最坏情况时间复杂度是多少？

Question

procedure matrixvector(n:integer);
var i,j:integer;
begin
  for i<-1 to n do begin
    B[i] = 0;
    C[i] = 0;
    for j<-1 to i do 
      B[i]<- B[i]+ A[i,j];
    for j<-n down to i+1 do
      C[i]<-C[i] + A[i,j]
  end
end;

Answer 1

O(n^2)，如果我没看错的话。

为什么你需要两个内部循环超出了我的范围。为什么不在同一个循环中求和 B 和 C？

Answer 2

只是为初学者详细解释：

最外层的 for 循环将运行 n 次（0 到 n） 然后在最外层的 for 循环中有两个 for 循环。第一个 for 循环将从 1 转到 n (1+2+3+4+.....+n) 第二个 for 循环将从 n 转到 1 (n+n-1+n-2+.. ..+1)

(1+2+3+4+5+....+n ) 的求和公式为 n(n+1)/2

所以总运行时间可以计算为 n + n(n+1)/2 + n(n+1)/2

观察这个方程中的最高多项式，它是n^2。

我们可以进一步简化这个方程，去掉常数并忽略线性部分，这将使我们的运行时间为 n^2。

Answer 3

最坏的情况是 O(n²)。

确实有三个循环，但不是都在彼此内部，因此给出了 O(n²)。

此外，您可以清楚地看到内部循环不会从 1 变为 n（就像外部循环一样）。但是因为这只会将时间复杂度改变一些常数，所以我们可以忽略它并说它只是 O(n^2)。

这表明时间复杂度是一种衡量标准：您的算法将按此顺序扩展，并且不会再花费更多时间。（但总是可以更快）

有关“计算”任何算法的最坏情况复杂度的更多信息，我可以向您指出我之前提出的一个相关问题