Jumlah tertimbang dari angka N terakhir

Misalkan kita menerima angka dalam aliran. Setelah setiap angka diterima, jumlah tertimbang dari angka terakhir $N$perlu dihitung, di mana bobot selalu sama, tetapi sewenang-wenang.

Seberapa efisien hal ini dapat dilakukan jika kita diizinkan menyimpan struktur data untuk membantu perhitungan? Bisakah kita melakukan yang lebih baik daripada $\Theta(N)$ , yaitu menghitung ulang jumlah setiap kali nomor diterima?

Sebagai contoh: Misalkan bobot yang $W= \langle w_1, w_2, w_3, w_4\rangle$ . Pada satu titik kita memiliki daftar terakhir $N$ nomor $L_1= \langle a, b, c, d \rangle>$ , dan jumlah tertimbang $S_1=w_1*a+w_2*b+w_3*c+w_4*d$ .

Ketika nomor lain, $e$ , diterima, kami memperbarui daftar untuk mendapatkan $L_2= \langle b,c,d,e\rangle$ dan kita perlu menghitung $S_2=w_1*b+w_2*c+w_3*d+w_4*e$ .

Pertimbangan menggunakan FFT Kasus khusus masalah ini tampaknya dapat dipecahkan secara efisien dengan menggunakan Fast Fourier Transform. Di sini, kita menghitung jumlah ditimbang $S$ dalam kelipatan $N$ . Dengan kata lain, kita menerima angka $N$ dan baru kemudian kita dapat menghitung jumlah ditimbang sesuai $N$. Untuk melakukan ini, kita membutuhkan $N-1$ angka yang lalu (yang jumlahnya telah dihitung), dan $N$ angka baru, total $2N-1$ angka N - 1 .

Jika vektor bilangan masukan dan vektor berat $W$ menentukan koefisien polinomial $P(x)$ dan $Q(x)$ , dengan koefisien dalam $Q$ terbalik, kita melihat bahwa produk $P(x)\times Q(x)$ adalah polinomial yang koefisiennya di depan $x^{N-1}$ hingga $x^{2N-2}$ adalah jumlah tertimbang yang kami cari. Ini dapat dihitung menggunakan FFT di $\Theta(N*\log (N))$ waktu, yang memberi kami rata-rata waktuper nomor input.$Θ(\log (N))$

Namun ini bukan solusi masalah seperti yang disebutkan, karena diperlukan bahwa jumlah tertimbang dihitung secara efisien setiap kali nomor baru diterima - kami tidak dapat menunda perhitungan.

Berikut ini adalah penjabaran dari pendekatan Anda. Setiap iterasi, kita menggunakan algoritma FFT untuk menghitung nilai-nilai konvolusi dalam waktu , dengan asumsi bahwa selanjutnya nilai-nilai nol. Dengan kata lain, kami menghitung mana adalah bobot (atau timbangan terbalik), adalah urutan input, adalah waktu saat ini, dan untuk .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$

Untuk setiap iterasi berikut , kami dapat menghitung konvolusi yang diperlukan dalam waktu ( iterasi ke- membutuhkan waktu ). Jadi waktu yang diamortisasi adalah . Ini diminimalkan dengan memilih , yang memberikan waktu berjalan diamortisasi .$m$$O(m)$$i$$O(i)$$O(m) + O(n\log n/m)$$m = \sqrt{n\log n}$$O(\sqrt{n\log n})$

Kami dapat meningkatkan ini ke waktu berjalan terburuk dengan memecah komputasi menjadi beberapa bagian. Perbaiki , dan tentukan Setiap hanya bergantung pada input , sehingga dapat dihitung dalam waktu . Juga, mengingat untuk , kita dapat menghitung konvolusi dalam waktu . Karena itu, rencananya adalah mempertahankan daftar Untuk setiap periode$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}$$2m$$O(m\log m)$$C_{\lfloor t/m \rfloor-p,p}$$0 \leq p \leq n/m-1$$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$input, kita perlu memperbarui ini. Setiap pembaruan membutuhkan waktu , jadi jika kami menyebarkan pembaruan ini secara merata, setiap input akan membutuhkan kerja . Bersama dengan menghitung konvolusi itu sendiri, kompleksitas waktu per input adalah . Memilih seperti sebelumnya, ini menghasilkan .$n/m$$O(m\log m)$$O((n/m^2) m\log m) = O((n/m) \log m)$$O((n/m)\log m + m)$$m = \sqrt{n\log n}$$O(\sqrt{n\log n})$