Rychlá Fourierova transformace: Porovnání verzí
Smazaný obsah Přidaný obsah
těch komplexních čísel je více => plurál; je ti TA DFT (transformace) značka: editace z Vizuálního editoru |
m Robot: přidáno {{Autoritní data}}; kosmetické úpravy |
||
Řádek 7:
k = 0,\dots,N-1. </math>
Přímé vyhodnocení těchto sum by zabralo [[asymptotická složitost|O(''N'' <sup>2</sup>)]] aritmetických operací. FFT naproti tomu poskytuje složitost pouze O(''N'' log ''N'') operací. Obecně jsou FFT algoritmy založeny na [[faktorizace|faktorizaci]] ''N'', nicméně existují i FFT algoritmy se složitostí O(''N'' log ''N'') pro všechna ''N'', tedy i pro [[prvočíslo|prvočísla]].
Jelikož je inverzní DFT stejná jako DFT jen s rozdílem opačného znaménka v exponentu a koeficientu 1/''N'', kterýkoli algoritmus je možné snadno modifikovat i pro počítání inverzní DFT.
Řádek 30:
{{Pahýl}}
{{Autoritní data}}
[[Kategorie:Algoritmy]]
|