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

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;

3 个解决方案

#1

O(n^2), if I read it right.

O(n ^ 2),如果我读得对。

Why you need two inner loops is beyond me. Why not sum B and C in the same loop?

为什么你需要两个内循环超出我。为什么不在同一个循环中求和B和C?

#2

worst case is O(n²).

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

there are indeed three loops, but not all inside each other, thus giving O(n²).

确实有三个循环,但并非所有循环都在彼此内部,因此给出O(n²)。

also, you can clearly see that the inner loops won't go from 1 to n (like the outer loop does). But because this would only change the time complexity by some constant, we can ignore this and say that it is just O(n^2).

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

This shows that time complexity is a measure saying: your algorithm will scale with this order, and it won't ever take any longer. (faster is however always possible)

这表明时间复杂度是一种衡量标准:您的算法将按此顺序进行扩展,并且不会再花费更长时间。 (但总是可以更快)

for more information about "calculating" the worst case complexity of any algorithm, I can point you to a related question I asked earlier

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

#3

Just explaining in detail for beginners:

只是为初学者详细解释:

Outermost for loop will run n times (0 to n) Then there are two for loops within the out ermost for loop. First for loop will go from 1 to n (1+2+3+4+.....+n) And the second for loop will go from n to 1 (n+n-1+n-2+....+1)

最外面的循环将运行n次(0到n)然后在最外面的for循环中有两个for循环。第一个for循环将从1变为n(1 + 2 + 3 + 4 + ..... + n)并且第二个for循环将从n变为1(n + n-1 + n-2 + .. .. + 1)

The summation formula for (1+2+3+4+5+....+n ) is n(n+1)/2

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

so the total running time can be computed as n + n(n+1)/2 + n(n+1)/2

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

Observe the highest polynomial in this equation, it is n^2.

观察该等式中的最高多项式,它是n ^ 2。

We can further simplify this equation and drop the constants and ignore the linear part, which will give us a run time of n^2.

我们可以进一步简化这个等式并删除常数并忽略线性部分,这将给出n ^ 2的运行时间。

#1