Versio 24. huhtikuuta 2020 kello 14.25 muokkaa Jawacz (keskustelu \| muokkaukset) seulojat 3 578 muokkausta FFT: w ynnä pieniä tekstimuokkauksia ← Vanhempi muutos		Versio 24. huhtikuuta 2020 kello 14.31 muokkaa kumoa Jmk (keskustelu \| muokkaukset) seulojat, ylläpitäjät 90 999 muokkausta Aikavaativuudesta on omakin artikkelinsa, vaikkei kaksinen olekaan. Uudempi muutos →
Rivi 64: '''FFT''' ({{k-en\|[[:En:Fast_Fourier_Transform\|Fast Fourier Transform]]}}) eli nopea Fourier'n muunnos tarkoittaa tehokasta [[algoritmi]]a diskreetin Fourier'n muunnoksen ja sen käänteismuunnoksen laskemiseksi. Yleisin FFT on [[Cooleyn–Tukeyn algoritmi]], jonka tunsi jo [[Carl Friedrich Gauss\|C.F Gauss]] vuonna 1805 ja käytti sitä [[2 Pallas\|Pallas]] ja [[3 Juno\|Juno]] -asteroidien ratojen laskentaan.{{Lähde}} Työ ei ollut kovin tunnettu. Erilaisia rajoitettuja versioita kehitettiin 1800-luvulla ja 1900-luvun alkupuolella. Nykyisen maineensa FFT saavutti vuonna 1965, jolloin [[James Cooley\|Cooley]] [[IBM\|IBM:stä]] ja [[John Tukey\|Tukey]] [[Princetonin yliopisto\|Princetonista]] osoittivat työssään algoritmin soveltuvuuden tietokoneohjelmointiin. Jos diskreetti Fourier'n muunnos lasketaan suoraan DFT:n määritelmästä, tarvittavien laskentaoperaatioiden määrä on verrannollinen näytepisteiden määrän [[neliö_(algebra)\|neliöön]] <math>N^2\,</math>. Sen sijaan FFT-algoritmien [[~~kompleksisuus#Kompleksisuuden lajeja\|laskennallinen kompleksisuus~~aikavaativuusluokka]] on ~~luokkaa~~ <math>O(N \, \operatorname{log} \, N\,)</math>. FFT:n nopeusero verrattuna suoraan diskreetin muunnoksen määritelmästä laskemiseen muuttuu hyvin merkittäväksi, kun näytepisteiden määrä on suuri. Käytännön sovelluksissa Diskreetti Fourier'n muunnos lasketaankin lähes aina [[numeerinen laskenta\|numeerisesti]] FFT:n avulla. == Käytännön sovelluksia ==

Ero sivun ”Fourier-muunnos” versioiden välillä