这种算法的最坏情况时间复杂度是多少？

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

让我们跟踪每次迭代中每个循环执行的次数。

\n

procedure matrixvector(n : integer);\nvar i, j : integer;\nbegin\n    for i<-1 to n do begin   // OuterLoop\n        B[i] = 0;\n        C[i] = 0;\n\n        for j <- 1 to i do   // InnerLoop_1\n            B[i] <- B[i] + A[i, j];\n\n        for j <- n down to (i + 1) do   // InnerLoop_2\n            C[i] <- C[i] + A[i, j]\n    end\nend;\n

\n

InnerLoop_1

\n

在 OuterLoop (i = 1) 的第一次迭代中，InnerLoop_1 执行once.

\n

在 OuterLoop (i = 2) 的第二次迭代中，InnerLoop_1 执行twice.

\n

在 OuterLoop (i = 3) 的第三次迭代中，InnerLoop_1 执行thrice.

\n

.\n.\n.

\n

在 OuterLoop (i = n) 的最后一次迭代中，InnerLoop_1 执行n times。

\n

因此，该代码执行的总次数为

\n

1+ 2+ 3+ \xe2\x80\xa6 +n

\n

= (n(n + 1) / 2) （自然数之和公式）

\n

=(((n^2) + n) / 2)

\n

=O(n^2)

\n

InnerLoop_2

\n

在 OuterLoop (i = 1) 的第一次迭代中，InnerLoop_2 执行了n - 1次。

\n

在 OuterLoop (i = 2) 的第二次迭代中，InnerLoop_2 执行了n - 2次。

\n

在 OuterLoop 的第三次迭代 (i = 3) 中，InnerLoop_2 执行了n - 3次。

\n

.\n.\n.

\n

在n - 2OuterLoop 的第 1 次迭代中 (i = n - 2)，InnerLoop_2 执行了2次。

\n

在n - 1OuterLoop 的第 1 次迭代中 (i = n - 1)，InnerLoop_2 执行了1一次。

\n

在 OuterLoop (i = n) 的最后 ( nth) 次迭代中，InnerLoop_2 执行了0次。

\n

因此，该代码执行的总次数为

\n

n - 1+ n - 2+ n - 3+ \xe2\x80\xa6 + 2+ 1+0

\n

= 0+ 1+ 2+ \xe2\x80\xa6 + n - 3+ n - 2+n - 1

\n

= (n - 1)((n - 1) + 1) / 2（自然数之和公式）

\n

=(n - 1)(n) / 2

\n

=(((n^2) - n) / 2)

\n

=O(n^2)

\n

Time Complexity

\n

执行次数InnerLoop_1：(((n^2) + n) / 2)

\n

执行次数InnerLoop_2：(((n^2) - n) / 2)

\n

相加，我们得到

\n

(((n^2) + n) / 2)+(((n^2) - n) / 2)

\n

=((((n^2) + n) + ((n^2) - n)) / 2)

\n

=(((n^2) + n + (n^2) - n) / 2)

\n

=(((n^2) + (n^2)) / 2)

\n

=((2(n^2)) / 2)

\n

=(n^2)

\n

=O(n^2)

\n

\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94

\n

另外，请看看这些

\n

\n
1. /sf/answers/5007620201/
\n
2. /sf/answers/4980256571/
\n
3. /sf/answers/4887531491/
\n
4. /sf/answers/5043277781/
\n
5. /sf/answers/5043285341/
\n

\n