Hizli Fourier Donusumu algoritmasi Ayrik Fourier Donusumunu $O(n^2)$ den hizli hesaplamak icin kullanilan tum algoritmalarin genel adiymis. Bilgisiyar biliminde acik sorulardan bir tanesi bu donusumu $O(n\log{n})$ den hizli yapabilirmiyiz imis.
Ben Cooley-Tukey algoritmasindan bahsedecegim. Ilginc bir anektod olarak bu algoritmayi Cooley ve Tukeyden 160 sene kadar once Gauss astreoidlerin yorungesini hesaplamak icin bulmus/kullanmis.
$N$ uzunlugundaki $x_n$ dizisinin Ayrik Fourier Transformasyonu su sekilde veriliyor:
$k \in [0, N-1] \quad X_k = \sum_{n=0}^{N-1}x_n e^{-\frac{2\pi i}{N}nk} $
$X_k$ yi baska bir sekilde ifade edelim.
$X_k = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N}2mk} + \sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N}(2m+1)k}$
$X_k = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N/2}mk} + e^{-\frac{2\pi i}{N}k}\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N/2}mk}$
Dikkatli bakarsaniz toplamanin sagi $x_{2k}$ dizisinin , toplamanin sol tarafi $x_{2k+1}$ dizisinin Ayrik Fourier Donusumu.
$e^{i\cdot} $ nin periyodikliginden yararlanip gosterebiliriz ki
$X_k = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N/2}mk} + e^{-\frac{2\pi i}{N}k}\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N/2}mk}$
$X_{k+\frac{N}{2}} = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N/2}mk} - e^{-\frac{2\pi i}{N}k}\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N/2}mk}$
Bu sekilde ozyinelemeli olarak yazarsak yapacagimiz islem sayisi $O(n^2)$ den $O(n\log{n})$ duser.
Python da yazarsak
def hizli_fourier(x):
N = len(x)
if(N <=1):
return x
cift = hizli_fourier(x[0::2])
tek = hizli_fourier(x[1::2])
T= [ exp(-2j*pi*k/N)*tek[k] for k in range(N//2) ]
sol = [ cift[k] + T[k] for k in range(N//2)]
sag = [cift[k] - T[k] for k in range(N//2)]
return sol+sag
Duzenleme :
Su soruyu da inceleyebilirsiniz. Verilen cevap matematiksel olarak daha temiz.