0 
PrefixAverages1(X)
Input: X, a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n
2) For i = 0 to n-1
3)    Let s = X[0]
4)    For j = 1 to i
5)       Let s = s + X[j]
6)    End For
7)   Let A[i] = s /(i+1)
8) End For
Output: An n-element array A of numbers such that A[i]
    is the average of elements X[0],X[1], … ,X[i]


PrefixAverages2(X)
Input: X, a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n
2) Let s = 0
3) For i = 0 to n-1
4)    Let s = s + X[i]
5)    Let A[i] = s / (i+1)
6) End For
Output: An n-element array A of numbers such that A[i]
    is the average of elements X[0],X[1], … ,X[i]

So here is what I know so far:

The first algorithm makes use of a second nested for loop. The second one is more efficient. In the first, S is equal to the first element of the array. In the second, S is equal to 0.

What else am I missing? Any help will really be appreciated, thanks!

4

1 に答える 1

0

どちらのアルゴリズムでも、各反復の最後で、S は 0 から までのすべての要素の合計に等しくなりiます。

2 番目のアルゴリズムでは、最初の繰り返しまで、要素がまだ表示されていないため、合計が 0 になります。

最初に、計算するループはS1 からカウントを開始します。これは を見ないX[0]ため、合計が正しくなるように他の場所に追加する必要があります。だからS、すでに含めて始めX[0]ます。(これは空のリストでも安全です。なぜなら、空のリストでは合計を計算することはないからです。)

最初のアルゴリズムの合計ループを 0 からカウントを開始するように変更した場合、0 からS開始されます。作成者がマイクロ最適化を行っていて、初期化のポイントを認識していなかったため、そのようには行われなかったと思います。 0 に変更し、X[0]それが存在することがわかったらすぐに追加します。

于 2013-02-14T17:16:45.927 に答える