complexity-theory - 歩数を使用して時間の複雑さを見つける方法

Question

sum(array,n)
{
  tsum=0;
  for(i=0;i<n;i++)
    tsum=tsum+array[i];
  return tsum;
}

Answer 1

big-Oに関しては、処理される配列要素の数に比例して線形であるため、 O(n)

(注: あなたのコードは i パラメーターを上書きします。合計する配列要素の数を示すために、パラメーターが n であることが意図されていたと仮定しますか?)

Answer 2

                                Cost         Times
tsum=0;                         c1             1
for(i=0;i<n;i++)                c2             n+1
    tsum=tsum+array[i];         c3             n
return tsum;                    c4             1

アルゴリズムの総コストは 1*c1 + (n+1) c2 + n c3 + 1*c4

したがって、このアルゴリズムに必要な時間は n に比例します。

Answer 3

1ステップでtsum=0を宣言してから、nステップのループを実行します。1回の繰り返しで1ステップの合計をして、1ステップでツムを返します。あなたの歩数はおおよそ次のとおりです。

1 + 3n + 1、これは big-oh 表記法で言えば O(n) であり、定数とすべての低次項 (それらの定数が存在する場合) を無視します。各反復のように 3n ステップがあり、変数 i をインクリメントし、それが n より小さいかどうかを確認してから、ループに入って計算を行います。