離散フーリエ変換を高速に計算する手法を高速フーリエ変換（FFT）といいます．コンピュータでフーリエ変換を行うには，フーリエ変換を離散化した離散フーリエ変換（DFT）を実行する必要があります．しかし，DFT は元データがN点の場合，その計算量がN2 に比例して増加してしまいます．FFT はDFT の周期性を利用することで演算の冗長性を省き，計算量をN log Nにまで減らすことができる手法です．