高速フーリエ変換について調べないと行けないんですけど
解説ページみてたら分からなくなりました。
以下解説文から抜粋----------------


　まず，長さ N の DFT

　 　 N-1　　 　jk 　 　 　 　 -2πi / N
Ａ ＝ Σ ａ Ｗ ， Ｗ ＝ ｅ 　
　k 　 j=0　　j 　N 　 　N 　 　 　


を素直に計算する場合を考えます．この場合 Ａ_0 から
Ａ_N-1 までの各項の 計算に N 回の乗算が必要なため，全体で
N^2 回の乗算が必要になります． しかし，少し考えてみてください．
もし，N が 2 で割り切れるならば， 添字 k を偶数と奇数とに分ける
ことで，長さ N の DFT は，次の二つの， 長さ N/2 の DFT

　 　 N/2-1　　　　　 　 　 　 　 　jk
Ａ ＝ Σ 　（ａ ＋ ａ ） 　 　 Ｗ
　2k 　 j=0 　　　　j　 　N/2+j　 　 　 　N/2


　 　 N/2-1　　　　　 　 　 　j　 　jk
Ａ ＝ Σ （（ａ − ａ ） Ｗ ） Ｗ
　2k+1 　 j=0 　　　　j　 　N/2+j　 　N　 　N/2