5

配列の合計値を計算するためのアルゴリズムを見つける方法は??

こんな感じですか？

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-Notationを使用して、アルゴリズムの実行時間とどのように関連付けることができますか

これは昨年の試験であり、試験の改訂を行う必要があります。

質問
n個の整数値を保持する配列A[]が与えられ
ます1.配列内のすべての値の合計を計算するためのアルゴリズムを与えます2.アルゴリズム
の実行時間の最も単純で最良のO表記を見つけます。

4

4 に答える 4

14

問題は、すべての値の合計を見つけて、配列内の各要素を反復処理し、各要素を一時的な合計値に追加することです。

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

配列内のすべての要素を調べる必要があるため、このプログラムは要素の数に直線的に依存します。10個の要素がある場合は、10個の要素を繰り返し処理します。百万個ある場合は、100万個の要素すべてを調べて、それぞれを追加する以外に選択肢はありません。したがって、時間計算量はΘ（n）です。

すべての要素の合計を見つけていて、データについて何も知らない場合は、少なくとも1回はすべての要素を調べる必要があります。したがって、nは下限です。また、要素を複数回見る必要はありません。nは上限でもあります。したがって、複雑さはΘ（n）です。

ただし、要素について何か知っている場合は、n個の自然数のシーケンスを取得するとします。たとえば、n（n + 1）/2を使用して一定時間でそれを行うことができます。取得するデータがランダムである場合は、上記の線形時間アルゴリズムを実行する以外に選択肢はありません。

于 2009-05-24T16:53:11.703 に答える
4

nは配列のサイズであり、最初から最後まで繰り返すだけなので、BigO表記はO[n]です。

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while
于 2009-05-24T16:46:22.523 に答える
0

「j<=Nの間」という意味だと思いますが、これを指定する必要があります。

ループが1つしかないので、実行時間はO（n）になると思います。

于 2009-05-24T16:48:03.517 に答える
0

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

では、j：= 1行は何回実行されますか？合計：= 0は何回実行されますか？whileループの条件は何回実行されますか？whileループ内のステートメント？

これらをすべて合計します。取得する値は、1 + 1 + n + n + n = 2+3nのようになります。したがって、これはnの線形関数であると結論付けることができます。

于 2009-05-24T16:57:38.467 に答える