Взвешенная сумма последних N чисел

Предположим, мы получаем цифры в потоке. После получения каждого числа необходимо вычислить взвешенную сумму последних $N$ чисел, где веса всегда одинаковы, но произвольны.

Насколько эффективно это можно сделать, если нам разрешено сохранять структуру данных, чтобы помочь с вычислениями? Можем ли мы сделать что-то лучше, чем $\Theta(N)$ , то есть пересчитывать сумму при каждом получении числа?

Например: Предположим , что веса $W= \langle w_1, w_2, w_3, w_4\rangle$ . В какой -то момент мы имеем список последних $N$ чисел $L_1= \langle a, b, c, d \rangle>$ , а взвешенная сумма $S_1=w_1*a+w_2*b+w_3*c+w_4*d$ .

Когда другой номер, $e$ , получена, мы обновить список , чтобы получить $L_2= \langle b,c,d,e\rangle$ и нам нужно вычислить $S_2=w_1*b+w_2*c+w_3*d+w_4*e$ .

Рассмотрение использования БПФ . Особый случай этой проблемы, по-видимому, эффективно решается с помощью быстрого преобразования Фурье. Здесь мы вычислим взвешенные суммы в упаковке N . Другими словами, мы получаем N чисел, и только тогда мы можем вычислить соответствующие N взвешенных сумм. Для этого нам нужно N - 1 прошлых чисел (для которых суммы уже были вычислены) и N новых чисел, всего 2 N - 1 чисел.$S$$N$$N$$N$$N-1$$N$$2N-1$

Если этот вектор входных чисел и весовой вектор определяют коэффициенты многочленов P ( x ) и Q ( x ) с обратными коэффициентами в Q , мы видим, что произведение P ( x ) × Q ( x ) является полиномом чьи коэффициенты перед x N - 1 до x 2 N - 2 - это именно те взвешенные суммы, которые мы ищем. Они могут быть вычислены с использованием БПФ в Θ ( N ∗ $W$$P(x)$$Q(x)$$Q$$P(x)\times Q(x)$$x^{N-1}$$x^{2N-2}$ времени, что дает нам в среднем thetas ; ( журнала ( N ) ) раз в номер входа.$\Theta(N*\log (N))$$Θ(\log (N))$

Это, однако, не является решением проблемы, как указано, потому что требуется, чтобы взвешенная сумма вычислялась эффективно каждый раз, когда принимается новое число - мы не можем задержать вычисление.

Вот разработка вашего подхода. Каждые итераций мы используем алгоритм FFT для вычисления m значений свертки за время O ( n log n ) , предполагая, что последующие m значений равны нулю. Другими словами, мы вычисляем n - 1 ∑ i = 0 w i a t - i + k$m$$m$$O(n\log n)$$m$ где w i - это n весов (или обратных весов), a i - входная последовательность, t - текущее время и a t ′ = 0 для t ′ > t .

$$\sum_{i=0}^{n-1} w_i a_{t-i+k}, \quad 0 \leq k \leq m-1,$$ $w_i$$n$$a_i$$t$$a_{t'} = 0$$t' > t$

Для каждой из следующих итераций мы можем рассчитать требуемую свертку за время O ( m ) (для i- й итерации требуется время O ( i ) ). Таким образом, амортизированное время составляет O ( m ) + O ( n log n / m ) . Это минимизируется путем выбора m = $m$$O(m)$$i$$O(i)$$O(m) + O(n\log n/m)$ , который дает амортизированное время работыO($m = \sqrt{n\log n}$.$O(\sqrt{n\log n})$

Мы можем улучшить это до наихудшего времени работы , разбив вычисление на части. Зафиксируемmи определим b T , p , o = m - 1 ∑ i = 0 w p m + i a T m - i + o$O(\sqrt{n\log n})$$m$ Каждый C T , p зависит только от 2 м входов, поэтому его можно вычислить за время O ( m log m ) . Кроме того, учитывая C ⌊ t / m ⌋ - p , p для 0 ≤ p ≤

$$b_{T,p,o} = \sum_{i=0}^{m-1} w_{pm+i} a_{Tm-i+o}, \quad C_{T,p} = b_{T,p,0}, \ldots, b_{T,p,m-1}.$$ $C_{T,p}$$2m$$O(m\log m)$$C_{\lfloor t/m \rfloor-p,p}$ , мы можем вычислить свертку за время O ( n / m + m ) . Поэтому план состоит в том, чтобы сохранить список C ⌊ t / m ⌋ - p , p$0 \leq p \leq n/m-1$$O(n/m + m)$ Для каждого периода из m входов нам необходимо обновить n / m из них. Каждое обновление занимает время O ( m log m ) , поэтому, если мы распространим эти обновления равномерно, каждый вход займет работу O ( ( n / m 2 ) m log m ) = O ( ( n / m ) log m $$C_{\lfloor t/m \rfloor-p,p}, \quad 0 \leq p \leq n/m-1.$$ $m$$n/m$$O(m\log m)$$O((n/m^2) m\log m) = O((n/m) \log m)$, Вместе с вычислением самой свертки временная сложность на вход составляет . Выбор м = $O((n/m)\log m + m)$ как и раньше, это даетO($m = \sqrt{n\log n}$.$O(\sqrt{n\log n})$