https://same.blog/2021/05/28/c言語高速フーリエ変換の実装周波数間引き型

https://same.blog/2021/05/28/c言語高速フーリエ変換の実装周波数間引き型fftコ/

より、仮に画像のフーリエ変換の式をＣ言語のプログラムにしたらどんな風に書くのでしょうか？
また、フーリエ変換を高速フーリエ変換にどうやって導いたのでしょうか？
なぜ高速化できるとわかったのでしょうか？


また、こちらのサイトの「普通のフーリエ変換はO(n^2)に対し、高速フーリエ変換はO(n*log n)で計算できます。」に関して、
普通のフーリエ変換のO(n^2)は画像の式でいうどの部分を表しているのでしょうか？
また、なぜO(n*log n)とすると普通のフーリエ変換より高速で計算できるとわかったのでしょうか？
出来れば、高速フーリエ変換の式のどの部分がO(n*log n)なのか教えて頂けますか？
最後に
https://www.gfd-dennou.org/arch/prepri/2002/hoku …
のサイトの(3.5.1)の高速フーリエ変換がなぜ一番最初に載せたプログラムのような複雑なプログラムになるのでしょうか？
普通に(3.5.1)の式のまま書けば良いのではないでしょうか？

No.2 回答者： tknakamuri 回答日時： 2022/02/28 07:59

かなりいい加減なことを書いたので訂正。

基本は、任意のDFTは、データが偶数個なら、
処理量が1/4の2つのDFTに分解できるということ。
#ここまでは合ってます(^_^;)

これを繰り返すとN個の極小なDFTに
分解できるので、分解の手間を考えなければ
処理量はNに比例することになります。

しかし分解にNに比例する演算が必要。
個々の極小DFTの演算は1回だけで無視できる。
なので
分解に必要な手間だけ考えると
分解の手間はlog(N)とNに比例するので
NLog(N)
に比例することになります。

これが基本となるアイデアです。

No.1 回答者： tknakamuri 回答日時： 2022/02/27 03:20

ここで詳細を書くのはきついので

フーリエ変換の教科書を読んで見ては?

基本は、任意のDFTは、データが偶数個なら、
処理量が1/4の2つのDFTに分解できるということ。
これを繰り返すとlog(N)個の極小なDFTに
分解できるので処理量はlog(N)に比例することに
なります。

ソートで処理量をLog(N)にするパターンと
とてもよくにてます。