n维快速傅立叶变换的计算复杂性? [英] Computational complexity of an n-dimensional Fast Fourier Transform?

问题描述

我正在尝试编写一些代码，以预测在给定的n维数组上执行离散傅立叶变换所需的时间，但是我一直在努力使自己的脑袋绕过n维的计算复杂性FFT.

I'm trying to write a bit of code that will predict the time taken to perform a discrete Fourier transform on a given n-dimensional array, but I'm struggling to get my head around the computational complexity of n-dimensional FFTs.

据我了解:

• 长度为N的向量的一维FFT应该取k*(N*log(N))，其中k是某个定时常数

• The 1D FFT of a vector of length N should take k*(N*log(N)) where k is some timing constant

对于M*N矩阵，二维FFT应采用:

For an M*N matrix, the 2D FFT should take:

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

因为它需要在每一行和每一列中进行一维FFT

since it requires taking 1D FFTs in each row and column

这如何推广到ND病例?是否应该为k*prod(dimensions)*sum(log(dimensions))?

How does this generalize to the ND case? Does it follow that it should be k*prod(dimensions)*sum(log(dimensions))?

推荐答案

如果我们进一步推导您的2D推论，就会很清楚:

If we take your derivation of 2D a bit further, it becomes clear:

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等)，复杂度为:

For N dimensions (A,B,C, etc...), the complexity is:

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

从数学上讲，N维FFT与一维FFT的尺寸乘积大小相同，只是

Mathematically speaking, an N-Dimensional FFT is the same as a 1-D FFT with the size of the product of the dimensions, except that the twiddle factors are different. So it naturally follows that the computational complexity is the same.

这篇关于n维快速傅立叶变换的计算复杂性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！