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

Question

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

2-D 和 3-D 中的卷积呢？

有什么参考吗？

Answer 1

至于二维和三维卷积和快速傅里叶变换，复杂度如下：

                            2D                     3D

---

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

---

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

参考：数字图像处理幻灯片，幻灯片编号。34.