Fast Fourier transform
Rychlá Fourierova transformace (FFT) je algoritmus pro efektivní výpočet diskretní Fourierovy transformace (DFT) a její inverze. DFT je klíčová technika v oblastech jako je zpracování signálů, analýza systémů a vědy o datech, protože umožňuje převést signál z časové domény do frekvenční domény. FFT dramaticky zrychluje tento výpočet, což je zvlášť užitečné při zpracování velkých datových souborů. První efektivní FFT algoritmus navrhl Cooley a Tukey v roce 1965, a od té doby se objevily různé varianty a optimalizace. FFT se široce používá v mnoha aplikacích, včetně audio a obrazového zpracování, komprese dat, a numerických simulací. Úspěch FFT leží v jeho schopnosti snižovat časovou složitost výpočtů a usnadňovat analýzu a zpracování signálů.