Fourier' kiirteisendus
Fourier' kiirteisendus (lühend FFT inglise keele sõnadest Fast Fourier Transform) on algoritmide kogum diskreetse Fourier' teisenduse (DFT) või selle pöördtehte (IDFT) kiireks sooritamiseks. Fourier' teisendus on vajalik mitmetel aladel, et käsitleda signaali sagedusruumis. Selle arvutamine on definitsiooni järgi aga tingituna suurest keerukusest O(N²), kus N on signaali punktide arv, aeganõudev ning tihtipeale ebapraktiline. Fourier’ kiirteisendus vähendab keerukust O(N log N) peale. Algoritmil oli murranguline mõju digitaalsignaalide töötlemise meetoditele – see on tänapäevani kasutusel inseneriteaduses, muusikatööstuses, matemaatikas jne. Populaarseks sai kiirteisenduse kasutamine 1965. aastal, kuid sarnase sisuga algoritme uurisid matemaatikud juba 19. sajandi alguses.