20

特定のn次元配列で離散フーリエ変換を実行するのにかかる時間を予測するコードを少し書き込もうとしていますが、n次元FFTの計算の複雑さに頭を悩ませています。

私が理解しているように：

  • 長さのベクトルの1DFFTは、次のようにNなりますk*(N*log(N))。ここで、kはタイミング定数です。

  • 行列の場合M*N、2DFFTは次のようになります。

    N*(k*M*log(M)) + M*(k*N*log(N)) = k*M*N*(log(M)+log(N))

    各行と列で1DFFTを取得する必要があるため

これはどのようにNDの場合に一般化されますか？それはそうあるべきだということになるのk*prod(dimensions)*sum(log(dimensions))でしょうか？

4

1 に答える 1

19

2D の導出をもう少し進めると、次のことが明らかになります。

N*(k*M*log(M)) + M*(k*N*log(N)) = k*M*N*(log(M)+log(N))

になります：

                                = k*M*N*(log(M*N))

N 次元 (A、B、C など) の場合、複雑さは次のとおりです。

O( A*B*C*... * log(A*B*C*...) )

数学的に言えば、回転因子が異なることを除いて、N 次元 FFT は次元の積のサイズを持つ 1-D FFT と同じです。したがって、当然、計算量は同じになります。

于 2012-09-03T14:31:27.467 に答える