[从0开始AIGC][Transformer相关]：算法的时间和空间复杂度-Toy模板网

这篇具有很好参考价值的文章主要介绍了[从0开始AIGC][Transformer相关]：算法的时间和空间复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、算法的时间和空间复杂度

算法是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但是过程中消耗的资源和时间却会有很大区别。

那么如何衡量不同算法之间的优劣？

主要还是从算法所占用的时间和空间两个维度去考量。

想要知道算法的时间复杂度，简单方法是把算法运行一遍，就知道所消耗的时间。但是这种方法会有很多弊端，首先该方式非常容易受到运行环境的影响，不同性能的机器运行的时间差异很大；再者，写算法的时候也没法完整运行整个算法。

因此，另一种更为通用的方法就出来了：大O表示法。

常见的时间复杂度量级有：

多头注意力机制的时间复杂度,# 从0开始AIGC,算法与数据结构,AIGC,transformer,算法

既然时间复杂度不是用来计算程序具体耗时的，那空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是一个对算法来运行过程中临时占用储存空间大小的一个量度，同样反映的是一个趋势。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)

一个形状为N × M的矩阵，与另一个形状为M × P的矩阵相乘，其运算复杂度来源于乘法操作的次数，时间复杂度为O（NMP）

Transformer模型的时间复杂度主要取决于输入序列的长度N和模型中隐藏层的数量H。而且tansformer的时间复杂度主要在于self-attention那块，至于激活函数、归一化、残差连接、前馈神经网络等这些计算的时间复杂度可忽略不计。

因此Transformer的时间复杂度，可以从两个角度看，一个是self-attention，另一个是多头attention。

self-attention 主要包括三个步骤：输入的线性映射、相似度计算、softmax和加权平均

因此，Self-Attention的时间复杂度是: $O(n^2d)$

对于多头注意力机制，假设有h个head,这里h是一个常数，对于每个head，首先需要把三个矩阵映射到 $d_q,d_k,d_v$ 。

Q,K,V： $n\times d$ 与 $n\times \frac{d}{h}$ 运算，复杂度为 $O(d^2n)$
相似度计算 $QK^T$ : 多头的相似度计算不是通过循环完成的，而是通过transpose和reshapes，用矩阵乘法来完成的。假设有h个head，则 $m=\frac{d}{h}$ 。将 $n\times d$ 的矩阵拆分为 $n\times h\times m$ 的张量，再利用转置操作转为 $h\times n\times m$ 。故 $QK^T$ 的计算为与 $h\times n\times m$ 与 $h\times n\times m$ 做计算，得到 $h\times n\times n$ 的张量，复杂度为 $O(h^2n^2m)$ , 即 $O(hn^2d)$ ,。由于h是一个常数，故复杂度为 $O(n^2d)$ ,。
softmax计算：对每行做softmax，复杂度为O(n)，则n行的复杂度为 $O(n^2)$
加权求和： $n\times n$ 与 $n\times d$ 运算，得到 $n\times d$ 矩阵，复杂度为 $O(n^2d)$