您的图像是 M 行 x N 列，并且 2D FFT 需要对所有行进行 1D FFT，然后对结果进行 1D 列 FFT。

所以你有了：

$M N \log N + N M \log M = MN (\log M + \log N) = MN \log MN$

操作总数。

可以使用类似的方法推导出 DFT 案例——这留给读者作为练习。

在 DFT-FFT 操作中，N 代表您在该序列中拥有的样本数。

例如，如果您有像 3*3 顺序的矩阵函数，那么这意味着在第一个序列中您有 3 个样本，在第二个序列中您有 3 个样本。

这里代表给定函数序列中的样本数。