滑动平均

Moving Average

给定长度为 $m$ 的数组 $A$ ，构造长度为 $m$ 的数组 $B$ ：

B_i=\frac{A_{i-n+1}+\cdots+A_i}{n}.

要求高效实现。

Large array $A$ with length $m$ , build array of $n$ -element moving avg. $B_i = \frac{A_{i-n+1} +\dots+ A_i}{n}.$

解析

维护滚动和：

S = A[1]+...+A[n];
B[n] = S/n;
for(i=n+1; i<=m; i++){
  S = S - A[i-n] + A[i];
  B[i] = S/n;
}

时间复杂度 $O(m)$ 。

Use the previous sum:

S = A[1]+...+A[n];
B[n] = S/n;
for(i=n+1; i<=m; i++){
    S = S - A[i-n] + A[i];
    B[i] = S/n;
}

Time $O(m)$ .