離散フーリエ変換の計算効率
DFTを定義に基づいて計算した場合、どれくらいの計算ステップが必要なのかを調べてみる。
まず、DFTの定義から出発する。
$$G_n=\sum_{k=0}^{N-1}g_ke^{-\frac{2\pi ink}{N}}$$
いま、式を見やすくするために
$$W^k=e^{-2\pi ik}$$
という複素数を導入する。定義式のΣを展開し、さらに周波数に関する添え字nも展開した形で式を書き直すと
\[
\begin{align*}
&G_0 =W^0g_0+W^0g_1+W^0g_2+…+W^0g_{N-1} \\
&G_1 =W^0g_0+W^{\frac{1}{N}}g_1+W^{\frac{2}{N}}g_2+…+W^{\frac{N-1}{N}}g_{N-1} \\
&G_2 =W^0g_0+W^{\frac{2}{N}}g_1+W^{\frac{4}{N}}g_2+…+W^{\frac{2(N-1)}{N}}g_{N-1} \\
&… \\
&G_{N-1} =W^0g_0+W^{\frac{N-1}{N}}g_1+W^{\frac{2(N-1)}{N}}g_2+…+W^{\frac{(N-1)^2}{N}}g_{N-1}
\end{align*}
\]
となる。
一般に、コンピュータによる計算では加減に比べ乗除の方が計算時間がかかるため、この式の中で最も時間のかかる計算は複素数Wとデータgの掛け算である。したがって、この式に掛け算がいくつあるかを数えることで計算量を見積もることができる。
上式には、N回×N行＝N^2回の掛け算があることがわかる。このことを、「DFTの計算量のオーダーはN^2である」と表現する。
高速フーリエ変換(FFT)
上で見た通り、離散フーリエ変換を定義通りに計算すると計算回数はNの2乗というオーダーになり、データ数が増えると計算量が爆発的に増えてしまい、実用的ではない。
この離散フーリエ変換を効率よく計算するためのアルゴリズムが高速フーリエ変換(Fast Fourier transform：FFT)である。高速フーリエ変換では、離散フーリエ変換をNlog_2Nのオーダーで計算することができる。
