FFT(高速フーリエ変換)

FFTは離散フーリエ変換を計算機上で高速に計算するアルゴリズムである． 離散フーリエ変換は，時間軸上でサンプリング(離散化)して得られたデータ列に 対するフーリエ変換である． Nの2乗個のデータ数しか，扱えない(Nは任意)． 離散フーリエ変換の式を(3.1)式に示す．

$$f_j = \sum_{k=0}^{N-1} x_k \exp\left( - \frac{2 \pi i j k}{N} \right) \qquad j = 0,\dots,N-1$$ (3.1)

これは，時間計算量がO ( N2 )である．高速フーリエ変換では，時間計算量をO ( N log N )に減らすことが可能である．