痔になりやすい生活習慣とは?

DFTを半分に分割していくのがFFTの特徴だと考えています。

で、どうしてDFTを半分に分割していくと計算コストが下がるのかりかいできていません。
理由を教えていただけないでしょうか?

よろしくお願いいたします。

A 回答 (4件)

どこまで理解できているのかわからないのでちょっと不安だけど, まあだいたいそう思っていいです.



「データ数を半分にする」ごとに
・DFT に必要な時間が半分になる.
・回転因子を掛けるための時間 (これはデータ数に比例する) がかかる.

前者は計算時間を減らし, それに対し後者は計算時間を増やします. その結果「ある程度のところ」で両方に必要な時間がバランスし, そのとき計算時間は最短になります.
    • good
    • 0
この回答へのお礼

ご丁寧にありがとうぎざいました。まだわからない部分もありますが、自分で考えてみます。

お礼日時:2011/04/05 23:04

 計算量の評価は、#1さんの仰るとおりと思いますが、自分もFFTの原理は良くわかっていませんが、Nが大きくなると、FFTの方が無茶苦茶に速くなります(体感できます)。



 FFTの効率の良さは、三角関数の周期性を利用するところにあるみたいです。つまり変換区間のある値から周期分ずれた所では、sin,cosは同じ値を出すはずだ、という発想です。これを考慮しないDFTは、同じ値を何回も計算し、大量の無駄を行ってる事になります。

 周期性をうまく利用できるように、変換区間を半分づつに分割するのが、ミソみたいです。mを2以上の整数として、m^nに分割してもFFTはできるそうです。効率は理屈ではいっしょです。
    • good
    • 0
この回答へのお礼

自分もFFTの速さはさきほどプログラムを使って体感しました。ただ、どんな手法を経て計算コストが下がっているのか理解し切れてません。
アドバイスなどあれば教えてください。

お礼日時:2011/04/05 18:24

そこは実は 4 に意味があるわけじゃないんだけどね.



Wikipedia の「高速フーリエ変換」の「原理の説明」を参考にするけど, N = PQ 個のデータに対する DFT は
1. Q 個のデータに対する DFT を P 回
2. 回転因子の乗算を合計 PQ 回
3. P 個のデータに対する DFT を Q 回
でできます. ここで, 「より少ない数のデータに対する DFT」だけではダメで, どうしても 2 の「回転因子の乗算」というステップが必要です. ここは PQ = N に比例する計算コストがかかります.

ということで, #1 の「+4N」はその分だと思ってください.
    • good
    • 0
この回答へのお礼

だんだんわかってきました。ありがとうございます。

つまり、2の回転因子の乗算のステップが必要ということは常に+4Nが発生するのでしょうか?

お礼日時:2011/04/05 18:23

端的にいうと


N = 1024 のとき N^2 と 2×(N/2)^2 + 4N のどっちが大きいですか
ってことだ.
    • good
    • 0
この回答へのお礼

なるほど。よくわかりました。

ただ、最後の項の+4Nはどこからでてきたのですか?

お礼日時:2011/04/05 09:14

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング