卷积的计算复杂度 [英] computational complexity of convolution

问题描述

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

I read that the computational complexity of the general convolution algorithm is O(n^2), while by means of the FFT is O(n log n).

在2-D和3-D中进行卷积怎么样?

What about convolution in 2-D and 3-D?

有参考吗?

推荐答案

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

As for two- and three-dimensional convolution and Fast Fourier Transform the complexity is following:

                            2D                     3D

---

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

---

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

参考:数字图像处理幻灯片，否. 34.

这篇关于卷积的计算复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！