なぜ高速フーリエ変換はO(n*log n)で計算できるのでしょうか？ どうか理由を詳しく教えて下さい

なぜ高速フーリエ変換はO(n*log n)で計算できるのでしょうか？
どうか理由を詳しく教えて下さい。

質問者からの補足コメント

• わたしは 「X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
  X1 = f0･W^0 + f1･W^1 + f2･W^2 + f3･W^3
  X2 = f0･W^0 + f1･W^2 + f2･W^4 + f3･W^6
  X3 = f0･W^0 + f1･W^3 + f2･W^6 + f3･W^9
  となるがW^(km)の性質から
  X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
  X1 = f0･W^0 + f1･W^1 - f2･W^0 - f3･W^1
  X2 = f0･W^0 - f1･W^0 + f2･W^0 - f3･W^0
  X3 = f0･W^0 - f1･W^1 - f2･W^0 + f3･W^1
  と簡単になる。しかし、これでも16回の掛け算が必要なのは変わらない。そこで上の式を奇数行と偶数行に分けた。

    補足日時：2022/03/20 07:06

• X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
  X2 = f0･W^0 - f1･W^0 + f2･W^0 - f3･W^0
  X1 = f0･W^0 + f1･W^1 - f2･W^0 - f3･W^1
  X3 = f0･W^0 - f1･W^1 - f2･W^0 + f3･W^1
  ここからは上の展開式を行列で表さないとわかりにくいのだが、メンドーなので省略する。

    補足日時：2022/03/20 07:07

• とにかく上のように行を入れ替えると
  X0 = W^0(f0+f2) + W^0(f1+f3)
  X2 = W^0(f0+f2) - W^0(f1+f3)
  X1 = W^0(f0-f2) + W^1(f1-f3)
  X3 = W^0(f0-f2) - W^1(f1-f3)
  のように8個の掛け算だけで済むように変形できる。これがバタフライ演算である」と考えたため、バタフライ演算からO(n*log n)が導けたのではないかと考えました。

    補足日時：2022/03/20 07:07

• ちなみに、画像の青い下線部の二つの式を組み合わせると水色で書かれた高速フーリエ変換の式(2)になると思うのですが、それ以前に青い下線部の二つの式はなんなのですか？

  
    補足日時：2022/03/21 16:00

• 図はn=8の場合だけど、3段(=log[2]8)のバタフライ
  (3回の計算)で処理してる。と言われたのですが
  3段ではなく4段ではないでしょうか？

  
    補足日時：2022/03/24 18:48

• なるほど、nは処理前のデータの量で、nを8とした時のバタフライ演算の回数が4回だと解りました。

    補足日時：2022/03/25 12:17

• usa3usa様、
  
  編集致します。
  
  「nは処理前のデータの量で、nを8とした時のバタフライ演算の回数が4回」
  ではなく、正しくは
  「nは処理前のデータの量で、nを8とした時のバタフライ演算を適応した場合の掛け算の回数が4回」
  という事でしょうか？
  
  また、
  
  バタフライ演算を適応した場合の掛け算の回数は画像のどの部分を表しているのでしょうか？

  
    補足日時：2022/03/29 13:46

• 4回と出したのは画像より、赤で囲まれたバタフライ演算の回数が4回のバタフライ演算を行っているため4回と書きました。

  
    補足日時：2022/03/30 07:09

• なるほど、
  「
  　図から明らかなように、処理するデータ数が N = 8 の時より
  第1ステージ(1段目)の N = 8 のバタフライ演算は1組
  　1組の乗算回数は4回だから計1×4=4回
  第2ステージ(2段目)の N = 4 のバタフライ演算は2組
  　1組の乗算回数は2回だから計2×2=4回
  第3ステージ(3段目)の N = 2 のバタフライ演算が4組
  　1組の乗算回数は1回だから計4×1=4回
  　だから、バタフライ演算の乗算回数の合計は12回。」

  
    補足日時：2022/03/30 08:03

• この各段のバタフライ演算の乗算回数を素早く求めるためにO(Nlog(N))(N=8の時、乗算回数は8log(8)=12、すなわち乗算回数は12回)を作ったのですね。
  そのため、「バタフライ演算を適応した場合の掛け算の回数」が12回とわかりました。
  
  以前私が言っていた「バタフライ演算の回数が4回」とは画像より各段のバタフライ演算のそれぞれの乗算回数の計が4回を表しているのだとわかりました。
  
  合っていますでしょうか？

    補足日時：2022/03/30 08:03

No.20 回答者： usa3usa 回答日時： 2022/04/01 05:24

No19のお礼見ました

O記法（オーダー記法）について完全に誤解されていますね。

>文章的にO(n*log n)にnの値を代入すればnに対するバタフライ演算の回数が導けると思っていました。
確かに、O(n*log n)を数値（関数）と誤解しても意味が通る文章ですね。しかし、間違ってます。
O(n*log n)は数値ではありません。
O記法（オーダー記法）は、「計算にかかる時間とデータ量の関係について表した記法」で、加速度性能のようなものでしょうか。

私の質問した「最適な撮影位置を求めるアルゴリズム」
https://oshiete.goo.ne.jp/qa/12855247.html
がO記法（オーダー記法）の使い方の例になる気がします。参考まで。

＜ここから後はおまけ＞
>だとしたら、先程のO(8*log 8)から導かれた24はバタフライ演算の計算速度を表しているのですか？
間違ってます
そもそもO(8*log 8)のようなO記法はありません。

>また、O(N/2)log_2(N)の式がNの値に対するバタフライ演算の回数を導けると言う事でしょうか？
間違っています
O(N/2は数値ではないので、O(N/2)log_2(N)は無意味な文字列なだけで、数式になっていないと思いますが・・

＞具体的な値が計算できないならなぜ①からO(n*log n)を導いたのですか？
①で複数のN（8,256,512,1024)の場合の掛け算の回数を数え上げてデータとして用意し、そのデータ列から、
　Nの増加と計算量の増加の関係を観察してオーダーを推測する
ことでO(n*log n)を導くということです。

なお、この段階ではまだO(n*log n)は推測しただけなので、「オーダーがO(n*log n)である」と断言するには別途、証明が必要ですね。
なお、オーダーの証明だけで論文になるくらい面倒なものですけど・・

つまり、
O記法（オーダー記法）は、加速度性能のようなものなので、N=8の場合の計算量だけを見ていてもO(n*log n)なのか、O(n^2)なのかの判断はできませんよ。

この回答へのお礼

解説どうもありがとうございます。

Nの増加と計算量の増加の関係を観察してオーダーを推測する
ことでO(n*log n)と導けたのにnに値が代入出来ないというのが正直よくわかりませんでした。

他の質問にも答えて頂けるとありがたいです。

お礼日時：2022/04/01 16:02

No.19 回答者： usa3usa 回答日時： 2022/03/31 07:54

>Nの値に対してバタフライ演算の具体的な回数を求めるにはO(n*log n)を使うと思ったのですが、違うのですか？

違います

O(n*log n)やO(n)、O(n²)などは、「計算にかかる時間とデータ量の関係について表した記法」で　数値　ではありませんよ。

「O(n*log n)で計算できる」→「カメの速度で計算できる」
「O(n)で計算できる」→「新幹線並みの速度で計算できる」
みたいな感じですかね。

O記法を議論するなら、No6で書いたように
　計算回数を激減できることを「体感」し、
　激減の度合いを「定式化したいと感じ」てから、
　「O記法を使えば、激減の度合いを表現できる」ことを発見する
のが先決ですかね

この回答へのお礼

「ーーーーーーーーーー
N＝８の場合は、普通に計算すると＿A＿回の掛け算が必要だが、バタフライ演算を適応すると＿B＿回の掛け算で計算できる。

N＝２５６の場合は、普通に計算すると＿C＿回の掛け算が必要だが、バタフライ演算を適応すると＿D＿回の掛け算で計算できる。

以上のことから、一般にN＝２＾Kの場合は、普通に計算すると＿I＿回の掛け算が必要だが、バタフライ演算を適応すると＿J＿回の掛け算で計算できる。

すなわち、バタフライ演算を用いないとO(n＾２)であるが、バタフライ演算を用いる高速フーリエ変換はO(n*log n)で計算できる。」
と言われたので、文章的にO(n*log n)にnの値を代入すればnに対するバタフライ演算の回数が導けると思っていました。

だとしたら、先程のO(8*log 8)から導かれた24はバタフライ演算の計算速度を表しているのですか？

また、O(N/2)log_2(N)の式がNの値に対するバタフライ演算の回数を導けると言う事でしょうか？

お礼日時：2022/03/31 08:16

No.18 回答者： usa3usa 回答日時： 2022/03/31 07:10

＞あの、一つだけ今計算して疑問があります。

>O(8*log 8)を計算すると24と出ました。
「O(8*log 8)を計算する」??

No4:
＞ちなみに、O(n*log n)のOは何を表しているのでしょうか？
O記法（オーダー記法）のOです。計算にかかる時間とデータ量の関係について表した記法です。
https://note.com/strictlyes/n/n82d0a3874256

No16:
　　O(n*log n)で「本当に具体的な値を計算できる」
と勘違いしませんかね？

この回答へのお礼

ん？以前、
「ーーーーーーーーーー
N＝８の場合は、普通に計算すると＿A＿回の掛け算が必要だが、バタフライ演算を適応すると＿B＿回の掛け算で計算できる。

N＝２５６の場合は、普通に計算すると＿C＿回の掛け算が必要だが、バタフライ演算を適応すると＿D＿回の掛け算で計算できる。

以上のことから、一般にN＝２＾Kの場合は、普通に計算すると＿I＿回の掛け算が必要だが、バタフライ演算を適応すると＿J＿回の掛け算で計算できる。

すなわち、バタフライ演算を用いないとO(n＾２)であるが、バタフライ演算を用いる高速フーリエ変換はO(n*log n)で計算できる。」...①
と言われたので、Nの値に対してバタフライ演算の具体的な回数を求めるにはO(n*log n)を使うと思ったのですが、違うのですか？

>> 「O(8*log 8)を計算する」??
N=8の時にNに8を代入するためO(8*log 8)となりますよね？
具体的な値が計算できないならなぜ①からO(n*log n)を導いたのですか？

お礼日時：2022/03/31 07:25

No.17 回答者： usa3usa 回答日時： 2022/03/30 21:56

>すいません。

だとしたらO(N/2log(N))が正しい式だとしてO(Nlog(N))はなぜ出てきたのでしょうか？

新な疑問は、別の質問とすること

脇道にそれずに、回答８のA-Jを埋めれば、本件の質問の答えになるので、自分で「説明を生み出す努力」をしましょう

この回答へのお礼

わかりました。

あの、一つだけ今計算して疑問があります。

「N＝８の場合は、普通に計算すると＿A＿回の掛け算が必要だが、バタフライ演算を適応すると　１２　回の掛け算で計算できる。
すなわち、バタフライ演算を用いないとO(n＾２)であるが、バタフライ演算を用いる高速フーリエ変換はO(n*log n)で計算できる。」
に置いて、O(n*log n)は正しくはO(n/2*log n)ではないでしょうか？

O(8*log 8)を計算すると24と出ました。これだとN=8としてバタフライ演算を適応した場合の結果と一致しません。
私が間違っていると思いますが、どうかよろしくお願い致します。

お礼日時：2022/03/31 00:59

No.16 回答者： 都の西北我瀬駄の隣バカ田大学危機管理学科 回答日時： 2022/03/30 19:16

>「乗算回数は12回」は正解として、大目に見てあげてよい気がします。

「乗算回数は12回」が正解であることは最初から明記しています。求める式まで提示しているのですから。

　問題は
> 具体的に数えたのではなく、8log(8)=12　の式計算から算出したのなら論外ですけど・・
・・・です。対数のことすらよくわかっていないのでは推察されます。他の投稿を見てもそう感じます。
　そういう人に

> バタフライ演算を用いないとO(n＾２)であるが、バタフライ演算を用いる
> 高速フーリエ変換はO(n*log n)で計算できる。

という表現はいかがなものかと。オーダーにつていもよくわかってないのだから

　　O(n*log n)で「本当に具体的な値を計算できる」

と勘違いしませんかね？
　本当はこの質問者の投稿は最初無視すればよかったのですが、私が軽い気持ちで回答した内容をそっくりそのままネット上に拡散されたのを苦々しく思ってチェックしていた次第です。
　この投稿を最後に私もここらへんで降ります。
　ああ、疲れた（笑）。

No.15 回答者： usa3usa 回答日時： 2022/03/30 17:42

No14>間違い！ 私の回答を引用するのならもう少しよく読んでほしい。

その通りですが・・・
何を1回の乗算と見なして数えるかの違いとして、教育的配慮として今は、「乗算回数は12回」は正解として、大目に見てあげてよい気がします。

具体的に数えたのではなく、8log(8)=12　の式計算から算出したのなら論外ですけど・・

そもそも、Nlog(N)を導くための確認作業に、結論の式に代入していては意味ないですからね。

No6でも書きましたが、
自分で「説明を生み出す努力」、すなわち
適当なN1,N2,...を想定して、それぞれに対し実際の計算の「真似事」をして、
乗算回数に注目して、バタフライ演算を適応するとそれらが激減できることを「体感」し、
激減の度合いを「定式化したいと感じ」てから、
O(n*log n)の公式を「導いて」いくことが、本件の根本的な解決策と思いますよ。

この回答へのお礼

すいません。だとしたらO(N/2log(N))が正しい式だとしてO(Nlog(N))はなぜ出てきたのでしょうか？

お礼日時：2022/03/30 20:35

No.14 回答者： 都の西北我瀬駄の隣バカ田大学危機管理学科 回答日時： 2022/03/30 11:15

> O(Nlog(N))(N=8の時、乗算回数は8log(8)=12、すなわち

> 乗算回数は12回)を作ったのですね。

　間違い！ 私の回答を引用するのならもう少しよく読んでほしい。
　対数で log(8) は通常
　　log_10(8)≒0.9　　10 を底とする8の常用対数
　　log_e(8)≒2.1　　　e を底とする8の自然対数
を意味するからどちらを選んでも
　　8log(8) = 12
というデタラメな式にはなりようがない。下にも書いたようにデータ数 N のバタフライの乗算回数は
　　(N/2)log_2(N)　（ log_2(N) は 2 を底とする N の対数 ）
で正確に計算できる。N = 8 ならば
　　(8/2)log_2(8) = 4log_2(8) = 4*3 = 12

　log(N)を常用対数、つまり log(N) = log_10(N)であるとする。
　N = 8 のとき O(Nlog(N)) から Nlog(N) を具体的に計算すると
　　Nlog(N) = 8log(8) ≒ 8*0.9 = 7.2
となり、正確な回数である12とは大きな差がある。
　N = 1024 のときでも
　　Nlog(N) = Nlog_10(N) = 1024*log_10(1024)≒1024*3 = 3072
となり、正確な乗算回数
　　(1024/2)log_2(1024) = 512*10 = 5120
と大きな差がある。つまり O(Nlog(N)) とは N が大きな数であるときの大雑把な目安に過ぎず、N に具体的な数値を入れて計算するようなしろものではない。
　バタフライ演算についていえば DFT の乗算回数 N^2 に対し
　　O(N^2) >> O(Nlog(N))
を強調したいだけのこと。オーダーによる評価については
https://oshiete.goo.ne.jp/qa/4388957.html
のNo3の回答などが参考になろう。

No.13 回答者： usa3usa 回答日時： 2022/03/30 08:33

>そのため、「バタフライ演算を適応した場合の掛け算の回数」が12回とわかりました。

正解に一歩、近づきましたね！！
つまり、No8の空欄の＿B＿が１２ということです。

No8の回答、採録します

脇道にそれずに、下記のA-Jを埋めれば、本件の質問の答えになるので、自分で「説明を生み出す努力」をしましょう
ーーーーーーーーーー
N＝８の場合は、普通に計算すると＿A＿回の掛け算が必要だが、バタフライ演算を適応すると　１２　回の掛け算で計算できる。

N＝２５６の場合は、普通に計算すると＿C＿回の掛け算が必要だが、バタフライ演算を適応すると＿D＿回の掛け算で計算できる。

N＝５１２の場合は、普通に計算すると＿E＿回の掛け算が必要だが、バタフライ演算を適応すると＿F＿回の掛け算で計算できる。

N＝１０２４の場合は、普通に計算すると＿G＿回の掛け算が必要だが、バタフライ演算を適応すると＿H＿回の掛け算で計算できる。

以上のことから、一般にN＝２＾Kの場合は、普通に計算すると＿I＿回の掛け算が必要だが、バタフライ演算を適応すると＿J＿回の掛け算で計算できる。

すなわち、バタフライ演算を用いないとO(n＾２)であるが、バタフライ演算を用いる高速フーリエ変換はO(n*log n)で計算できる。

この回答へのお礼

見落としていました。正しくは

この各段のバタフライ演算の乗算回数を素早く求めるためにO(N/2log(N))(N=8の時、乗算回数は4log(8)=12、すなわち乗算回数は12回)を作ったのですね。
そのため、「バタフライ演算を適応した場合の掛け算の回数」が12回とわかりました。

以前私が言っていた「バタフライ演算の回数が4回」とは画像より各段のバタフライ演算のそれぞれの乗算回数の計が4回を表しているのだとわかりました。

合っていますでしょうか？

お礼日時：2022/03/30 20:27

No.12 回答者： 都の西北我瀬駄の隣バカ田大学危機管理学科 回答日時： 2022/03/29 20:09

まだあきらめていなかったのか。

たいしたもんだ（笑）。
　しかし、質問内容の貧弱さから言ってきちんとした本で勉強したとはとても思えないが。
　あきらめない精神力を評価してムダを承知で書いておく。ま、わからんだろうけど。だからといって以下の文章をそのまま一切細工することなくネット上のあちこちで質問し、拡散するのは著作権侵害にあたるので絶対にやってはいけない。wwwwwwwwwwwwwww
　ちゃんとわかりたかったら、定評のある参考書と真剣に取り組むしかないよ。ヒマと金はありそうだから講師を雇い、対面で教えてもらえればいい。それが一番効果的だと思う。

　図から明らかなように、処理するデータ数が N = 8 のときは
　　N = 8、 N = 4、 N = 2
のバタフライ演算がこの順番で実行される。N = 32 であれば
　　N = 32、 N = 16、 N = 8、 N = 4、 N = 2
の順番で実行されるのだ。
　バタフライ演算では、図の矢印が右下向きのときだけ回転子をかける乗算（掛け算）が必要となり、その回転子は N に応じたものを使用する。ほんとはなぜそうするかを理解する必要があるが、さらにわからんだろうから省略する。

第1ステージの N = 8 のバタフライ演算は1組
　1組の乗算回数は4回
第2ステージの N = 4 のバタフライ演算は2組
　1組の乗算回数は2回だから計2×2=4回
第3ステージの N = 2 のバタフライ演算が4組
　1組の乗算回数は1回だから計4×1=4回
　だから、バタフライ演算の乗算回数の合計は12回。どのステージのバタフライでも乗算回数は4回、つまり
　　(N/2) = (8/2) = 4
であるから、もっとも素朴な（アルゴリズムのムダを無視する）FFT におけるデータ数 N のバタフライの乗算回数は

　　(N/2)log_2(N)　（ log_2(N) は 2 を底とする N の対数 ）

で正確に計算できる。log_2(N) はバタフライのステージの数（段数）を表す。今は N = 8 で考えているから
　　(8/2)log_2(8) = 4*3 = 12
で上の結果と一致する。

> バタフライ演算からO(n*log n)が導けたのではないかと考えました。
　O(Nlog(N)) は計算量をざっと見積もるときに使う。今の例ではデータ数 N = 8 のバタフライの正確な乗算回数
　(N/2)log_2(N)
に対しオーダー記法では定数倍を無視することで Nlog_2(N) でざっと見積り
　　O( Nlog_2(N) )
と記す。さらに log_2(N) = log(N)/log(2) であるから、やはり定数倍を無視すると
　　O( Nlog(N) )
で乗算回数を大雑把に評価することになる。

No.11 回答者： usa3usa 回答日時： 2022/03/29 17:35

No10 です

お礼見ました

バタフライ演算を適応した場合の掛け算の回数、本当に数えたの？
どこから　４回　が出てきたのですか？

ちなみに、バタフライ演算を適応しない場合の掛け算の回数、わかりますか？

具体的な実際に手を動かして考えてからお礼、書きましょうよ！