高速フーリエ変換
逆変換は正変換と同じと考えて良いが、指数の符号が逆であり、係数 1/N が掛かる。
高速フーリエ変換のプログラム中、どの符号が逆転するかを一々分岐させると、分岐の判定に時間がかかり、パフォーマンスが落ちる。一方、正変換のプログラムと、逆変換のプログラムを両方用意しておくことも考えられるが、共通部分が多いため、無駄が多くなる。このため、複素共役を使った次のような方法が考えられる。
離散フーリエ変換を
F ( t ) = ∑ x = 0 N − 1 f ( x ) exp  ( − i 2 π t x N ) {\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right)}
で定義したとき、逆変換は
Q = 2 の場合は、exp(−2πirq/Q) は 1 か −1 なので、Q 次の離散フーリエ変換は符号の逆転と足し算だけで計算できる。
Q = 4 の場合は、exp(−2πirq/Q) は 1, −1, i, −i のいずれかなので、Q 次の離散フーリエ変換の計算は、符号の逆転、実部虚部の交換と足し算だけで計算できる。
このため、2の累乗あるいは4の累乗次の離散フーリエ変換は簡単に計算できる。実務的に用いられるのは、Q = 2 か Q = 4 の場合のみである。なお、Q = 2 かQ = 4 の場合のこの部分のQ次の離散フーリエ変換のことを、バタフライ演算と言う。
また、Q = 2かQ = 4の場合において、計算を終了するまでに何回の「掛け算」が必要かを考える。符号の逆転、実部虚部の交換は「掛け算」として数えなければ、回転因子の掛け算のみが「掛け算」である。N = Qの次数を1落とすためにN回の「掛け算」が必要であり、次数をkから0に落とすにはそれをk回繰り返す必要があるため、「掛け算」の数は Nk = N logQ N となる。高速フーリエ変換の計算において時間がかかるのは「掛け算」の部分であるため、これが「高速フーリエ変換では計算速度は O(N' log N) になる」ことの根拠になっている。