Self-Attention 的时间复杂度/空间复杂度是怎么计算的

主要观点总结

本文介绍了Self-Attention和Multi-Head Attention的时间复杂度分析。文章详细解释了Self-Attention的三个步骤：相似度计算、softmax和加权平均，并指出其时间复杂度为O(n^2·d)。对于Multi-Head Attention，文章解释了其类似于CNN中的多核作用，并分析了其时间复杂度也是O(n^2·d)。此外，文章还涉及了空间复杂度的分析，并提供了相关参考文献。

关键观点总结

关键观点1: Self-Attention的时间复杂度分析

Self-Attention包括三个步骤：相似度计算、softmax和加权平均。其中，相似度计算的时间复杂度为O(n^2·d)，softmax的时间复杂度为O(n^2)，加权平均的时间复杂度也为O(n^2·d)。因此，Self-Attention的总时间复杂度为O(n^2·d)。

关键观点2: Multi-Head Attention的时间复杂度分析

Multi-Head Attention的作用类似于CNN中的多核。其时间复杂度分析与Self-Attention类似，也是O(n^2·d)。

关键观点3: 空间复杂度的分析

存储QK T的空间复杂度为O(N^2)，存储Softmax(QK T/d^0.5)V的空间复杂度为O(N^2 + Nd)，如果把向量维度d看作常数，则可以说Self-Attention的空间复杂度是序列长度的平方。