質問: fftでの計算コストの削減の理由が? dftを半分に分割していくのがfftの特徴だと考えています。 で、どうしてdftを半分に分割していくと計算コストが下がるのかりかいできていません。 理由を教えていただけないでしょうか? よろしくお願いいたします。
回答: そこは実は 4 に意味があるわけじゃないんだけどね. wikipedia の「高速フーリエ変換」の「原理の説明」を参考にするけど, n = pq 個のデータに対する dft は 1. q 個のデータに対する dft を p 回 2. 回転因子の乗算を合計 pq 回 3. p 個のデータに対する dft を q 回 でできます. ここで, 「より少ない数のデータに対する dft」だけではダメで, どうしても 2 の「回転因子の乗算」というステップが必要です. ここは pq = n に比例する計算コストがかかります. ということで, #1 の「+4n」はその分だと思ってください.