Zaawansowane algorytmy i struktury danych/Wykład 6

 $n$

Algorytm Algorytm Szybkiej Transformaty Fouriera

---

 STF($a=(a_0,\dots ,a_{n-1})$)
 if $n$ nieparzyste then
   dodaj wyraz $a_n$ do $a$
   zwiększ $n$
 if $\frac{n}{2}=1$ then return a
 ${\omega }_n=e^{\frac{2\pi i}{n}}$
 $\omega =1$
 $a^{[0]}=(a_0,a_2,\dots ,a_{n-2})$
 $a^{[1]}=(a_1,a_3,\dots ,a_{n-1})$
 $y^{[0]}=SFT(a^{[0]})$
 $y^{[1]}=SFT(a^{[1]})$
 for k=0 to $\frac{n}{2}-1$ do
   $y_k=y_k^{[0]}+\omega y_k^{[1]}$
   $y_{k+\frac{n}{2}}=y_k^{[0]}-\omega y_k^{[1]}$
   \omega = \omega \omega_n
 return y