由浅入深。
最近在回归深度学习的一些基础知识，希望把一些最基本的概念或者原理梳理一遍，方便自己在此后的工作和学习中对 深度学习 算法有更高层次的理解。这次介绍的是一个平时不太关注的话题，如何计算 卷积神经网络 的 时间复杂度 和 空间复杂度。原文链接：卷积神经网络的复杂度分析
1.时间复杂度
这里使用浮点运算次数 (FLoating-point OPerations) 来评估一个 CNN 模型的时间复杂度，其实就是模型的运算次数。
1.1 单个卷积层的时间复杂度
我们都知道完整的卷积神经网络由若干个卷积层和池化层组合而成，这里计算单个卷积层所带来的时间复杂度，公式如下：
$$O(n^2 \cdot f^2 \cdot C_{in} \cdot C_{out}) \tag{1} $$
参数解析：
- $n$: 每个卷积核输出特征图( Feature Map)的边长，$n^2$ 即特征图的面积；
- $f$: 每个卷积核 (Kernel) 的边长，$f^2$ 即卷积核的面积；
- $C_{in}$: 卷积层的输入通道数（上一层的输出通道）；
- $C_{out}$: 当前卷积层的输出通道数；
同时如果学习过吴恩达老师的深度学习课程的话，应该对计算卷积层输出尺寸的计算有所了解：
$$\biggl\lfloor \frac{n+2p-f}{s}+1 \biggr\rfloor \times \biggl\lfloor \frac{n+2p-f}{s}+1 \biggr\rfloor \tag{2} $$
其中：
- $s$ 为步长
- $p$ 为填充长度
- $n \times n$ 为输入图片大小
- $f \times f$ 为滤波器大小
这样也可以对公式（1）进行简化。
1.2 整个卷积神经网络的时间复杂度
$$O(\sum_{l=1}^D n_{l}^2 \cdot f_{l}^2 \cdot C_{l-1} \cdot C_{l}) \tag{3}$$
参数解析：
- D：表示卷积层的个数，也即网络的深度；
- l：表示网络的第 l 层；
2. 空间复杂度
空间复杂度严格来讲包括两个部分：总参数量 和 各层输出的特征图
计算公式如下 ：
$$O(\sum_{l=1}^D f_{l}^2 \cdot C_{l-1} \cdot C_{l}+\sum_{l=1}^D n^2 \cdot C_{l}) \tag{4}$$
- 总参数量只与卷积核的尺寸 $f$、通道数 $C$ 、层数 $D$ 相关，而与输入数据的大小无关。
- 输出特征图的空间占用比较容易，就是其空间尺寸 $n^2$ 和通道数 C 的连乘。
- 实际上有些层（例如 ReLU）其实是可以通过原位运算完成的，此时就不用统计输出特征图这一项了。
