Ważona suma ostatnich N liczb

Załóżmy, że otrzymujemy liczby w strumieniu. Po otrzymaniu każdej liczby należy obliczyć ważoną sumę ostatnich liczb, przy czym wagi są zawsze takie same, ale dowolne.$N$

Jak skutecznie można to zrobić, jeśli pozwolimy zachować strukturę danych, która pomoże w obliczeniach? Czy możemy zrobić coś lepszego niż , tj. Przeliczać sumę za każdym razem, gdy liczba jest odbierana?$\Theta(N)$

Na przykład: Załóżmy, że wagi to . W pewnym momencie mamy listę ostatnich liczb i ważoną sumę .$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$

Po otrzymaniu innej liczby, , aktualizujemy listę, aby uzyskać i musimy obliczyć .$e$$L_2= \langle b,c,d,e\rangle$$S_2=w_1*b+w_2*c+w_3*d+w_4*e$

Rozważanie przy użyciu FFT Szczególny przypadek tego problemu wydaje się być do rozwiązania w wyniku skutecznego zastosowania szybkiej transformacji Fouriera. Tutaj obliczania sumy ważonych wielokrotność . Innymi słowy, otrzymujemy liczb i tylko wtedy możemy obliczyć odpowiednie ważonych sum. Aby to zrobić, potrzebujemy przeszłych liczb (dla których sumy zostały już obliczone) i nowych liczb, łącznie liczb.$S$$N$$N$$N$$N-1$$N$$2N-1$

Jeśli ten wektor liczb wejściowych i wektor ciężaru określają współczynniki wielomianów i , przy współczynnikach w odwróconym , widzimy, że iloczyn jest a wielomian, którego współczynniki przed do są dokładnie ważonymi sumami, których szukamy. Można je obliczyć za pomocą FFT w czasie , co daje nam średni czas Θ (\ log (N)) na liczbę wejściową.P ( x ) Q ( x ) Q P ( x ) × Q ( x ) x N - 1 x 2 N - 2 Θ ( N ∗ log ( N ) ) Θ ( log ( N ) $W$$P(x)$$Q(x)$$Q$$P(x)\times Q(x)$$x^{N-1}$$x^{2N-2}$$\Theta(N*\log (N))$$Θ(\log (N))$

Nie jest to jednak rozwiązanie problemu, jak stwierdzono, ponieważ wymagane jest, aby suma ważona była obliczana wydajnie za każdym razem, gdy otrzymywana jest nowa liczba - nie możemy opóźniać obliczeń.

Oto opracowanie twojego podejścia. Każdy iteracji używamy algorytm do obliczania FFT wartości zwoju w czasie , przy założeniu, że kolejne wartości zero. Innymi słowy, gdzie są wagami (lub wagi odwrotne), jest sekwencją wprowadzania, jest bieżącym czasem, a dla .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 ′ >

$$\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$

Dla każdego z poniższych iteracji, że są w stanie wyliczyć wymagane splot w czasie (The tą iterację potrzebuje czasu, ). Tak więc zamortyzowany czas wynosi . Można to zminimalizować, wybierając , co daje zamortyzowany czas działania .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})$

Możemy to poprawić do najgorszego czasu działania , dzieląc obliczenia na części. Napraw i zdefiniuj Każde zależy tylko od wejść, więc można je obliczyć w czasie . Ponadto, biorąc pod uwagę dla , możemy obliczyć splot w czasie . Dlatego planuje się utrzymanie listy Dla każdego okresumb T , p , o = m - 1 ∑ i = 0 w p m + i a T m - i + o$O(\sqrt{n\log n})$$m$C T ,

$$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}$O ( m log m ) C ⌊ t / m ⌋ - p , p 0 ≤ p ≤ n / m - 1 O ( n / m + $2m$$O(m\log m)$$C_{\lfloor t/m \rfloor-p,p}$$0 \leq p \leq n/m-1$C ⌊ t / m ⌋ - p , p$O(n/m + m)$m n / m O ( m log m ) O $$C_{\lfloor t/m \rfloor-p,p}, \quad 0 \leq p \leq n/m-1.$$ $m$dane wejściowe, musimy zaktualizować z nich. Każda aktualizacja zajmuje czas , więc jeśli rozłożymy te aktualizacje równomiernie, każde wejście zajmie pracę . Wraz z obliczeniem samego splotu złożoność czasowa na wejście wynosi . Wybranie jak poprzednio, daje .$n/m$$O(m\log m)$O ( ( n / m ) log m + m ) 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})$