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）、正しく読むと。

2 つの内部ループが必要な理由は、私にはわかりません。同じループで B と C を合計しないのはなぜですか?

Answer 2

最悪の場合は O(n²) です。

実際には 3 つのループがありますが、すべてが互いに内側にあるわけではないため、O(n²) になります。

また、(外側のループのように) 内側のループが 1 から n にならないことがはっきりとわかります。しかし、これは時間計算量を一定の定数だけ変えるだけなので、これを無視して O(n^2) であると言うことができます。

これは、時間の複雑さが指標であることを示しています。アルゴリズムはこの順序でスケーリングされ、それ以上かかることはありません。(しかし、より速いことは常に可能です)

アルゴリズムの最悪の場合の複雑さを「計算」する方法の詳細については、以前に尋ねた関連する質問を参照してください。