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]

所以这是我到目前为止所知道的：

第一个算法使用第二个嵌套的 for 循环。第二种效率更高。首先，S 等于数组的第一个元素。在第二个中，S 等于 0。

我还缺少什么？任何帮助将不胜感激，谢谢！

4

1 回答 1

0

在这两种算法中，在每次迭代结束时，S 等于从 0 到 的所有元素的总和i。

在第二个算法中，直到第一次迭代，还没有看到任何元素，因此总和为 0。

首先，计算的循环S从 1 开始计数。由于它从不查看X[0]，因此必须将其添加到其他地方才能使总和正确。所以S一开始就已经包括X[0]. （即使对于空列表也是安全的，因为在空列表中我们永远不会计算总和。）

如果您更改了第一个算法的求和循环，使其从 0 开始计数，那么将从 0S开始。我认为它不是那样做的，因为作者是微优化的，并且没有看到初始化的意义到 0，然后X[0]当他已经知道它在那里时立即添加它。

于 2013-02-14T17:16:45.927 回答