complexity-theory - 卷积的计算复杂度

Question

我读到，一般卷积算法的计算复杂度为O(n^2)，而通过FFT的计算复杂度为O(n log n)。

那么在2D和3D中进行卷积呢？

有引用吗？

Answer 1

至于二维和三维卷积以及快速傅立叶变换，其复杂度如下:

                            2D                     3D

Convolution               O(n^4)                  O(n^6)

FFT                   O(n^2 log^2 n)           O(n^3 log^3 n)

引用: Slides on Digital Image Processing，幻灯片编号。 34。