総括配列ときO記法

Question

どのようにアルゴリズムのための計値の配列??

あのようなものか。

Algorithm Array Sum
Input: nonnegative integer N, and array A[1],A[2],...,A[N]
Output: sum of the N integers in array A
Algorith Body:
j:=1
sum:=0
while j<N
      sum := sum + a[J]
      j:=j+1
  end while
end Algorithm Array Sum

あまりに関の運転時間のアルゴリズムを用O-表記

これは過去の入試制度とし必要な改訂のための私の試験を受けました。

質問
配列A[]保有nを整数値
1.何アルゴリズムの計算に合には、値の配列
2.のもとO-表記の時間のアルゴリズムです。

Answer 1

に質問することにより 和のすべての値を で繰り返し処理を実行して各要素の配列に追加各要素の一時的な和の値です。

temp_sum = 0
for i in 1 ...array.length
    temp_sum = temp_sum + array[i]

めに必要なすべての配列の要素のこ プログラムにより直線の要素数.い10の要素に対して繰り返し処理を実行を通じての10の要素とした場合、百万円で他のすべては、万要素の追加をおすすめします。このように 時間の複雑さはΘ(n).

の場合の和のすべての要素としょかん本体に保存した打刻データを見ていく必要があるすべての要素に行くことになったのです。このnはlowerbound.る必要もないの要素がります。nも上りました。そのための複雑さはΘ(n)

しかしまっている場合について何かの要素..うまく連続性はnは自然数の取得ができないことがあり一定時間とn(n+1)/2になります。データが得られない場合にはいランダムなければならない以上の線形時間アルゴリズムです。

Answer 2

以来の N の配列のサイズがあり、あなたがしなければならないすべてはランダウの記号があるOを最初から最後まで反復処理である[N]

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while

Answer 3

私は、あなたが "しばらくJ <= N" を意味することを考えて、あなたがこれを指定する必要があります。

あなたが唯一のループを持っているとして

実行している時間はO（n）としなければならない、私は、考えてます。

Answer 4

あなたはコードの各行の実行回数をカウントする必要があり、このアルゴリズムのためのOを計算します。後で上だけの基本的な操作を数えるが、すべてをカウントすることによって開始されます。

それでは、どのように何回Jます：= 1行が実行しますか？ = 0ラン：合計は何回だろうか？ whileループの条件がどのように何回も実行されますか？ whileループ内のステートメント？

これらすべてをまとめます。あなたは、あなたが得る価値が何かのような1 + 1 + N + N + N = 2 + 3Nになることに気づくでしょう。したがって、あなたはそれがn個の一次関数であると結論付けることができます。