====== 高速フーリエ変換 ======
==== fast Fourier transform（**FFT**） ====

{{tag>..c03 ..c13}}

　離散的フーリエ変換を高速に実行する計算方法であり，1965年にCooleyとTukeyにより考案された．離散的フーリエ変換（DFT）の数値計算をそのまま実行すると計算量は//N//<sup>2</sup>であるのに対してFFTでは（//N///2）log//N//に減少する．DFTは通常FFTにより実行されるので，FFTはDFTを含めた広い意味で使われることが多い．


~~NOCACHE~~