ユーザ用ツール

サイト用ツール


高速フーリエ変換

fast Fourier transform(FFT

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