fft

なんでlogがでてきますか？

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

• ふざけるのかわかりません。

  No.1の回答に寄せられた補足コメントです。 補足日時：2024/06/30 11:13

No.3 ベストアンサー 回答者： mtrajcp 回答日時： 2024/06/30 17:00

N個のデータをマージ(クイック)ソートするとき

比較回数は　N(logN) 回(のオーダー)だから

この回答へのお礼

ちょっと違うかな？って思います。。
-1の三乗根をつかって速くするのに関係ないと思います。

お礼日時：2024/06/30 17:02

No.2 回答者： mtrajcp 回答日時： 2024/06/30 16:06

f(x)=Σ[j=0～N]A(j)x^j

と
g(x)=Σ[j=0～N]B(j)x^j
を
乗算することを考えます
この積は,

f(x)g(x)=Σ[i=0～N]Σ[j=0～N]A(i)B(j)x^(i+j)

C(k)=Σ{j=0～k}A(j)B(k-j)

とすると

f(x)g(x)=Σ[k=0～2N]C(k)x^k

となります
このC(k)を(0≦k≦2N)をみたすすべてのkについて求めるには

fの全項A(i)(i=0～N)
と
gの全項B(j)(j=0～N)
の間で

N*N=N^2　回　(のオーダーの)の乗算が必要なのだけれども

N*(logN) 回　(のオーダーの)の乗算ですますことができる
といっているのです

この回答へのお礼

ありがとうございます:)
そのlogはどうやってだれがもとめたんですか？？

お礼日時：2024/06/30 16:43

No.1 回答者： ありものがたり 回答日時： 2024/06/29 00:07

fft だと、log がでてくるんですね？

NＴＴ だったら、弁護士通して開示請求しても
ちゃんと log が出ないことがあるんですが。

この回答へのお礼

こわれたの？

お礼日時：2024/06/29 09:12