Mattson栈距离算法时间复杂度疑问：O(N*M)属O(N)还是O(N²)？

首先得明确O(N*M)里两个变量的定义：在Mattson算法的语境中，N一般指内存访问序列的总长度，M则是缓存的容量大小。这个复杂度到底归为O(N)还是O(N²)，取决于M的取值逻辑：

• 若M是固定常数（这也是缓存场景的常规情况——缓存大小是预先设定的系统参数，不会随访问序列长度N无限扩张），那么O(N*M)可以简化为O(N)，因为常数因子在大O表示法中会被忽略。
• 若M随N的增长而同阶增长（比如极端理论假设中，缓存大小和访问序列长度成比例），此时O(N*M)就等价于O(N²)。

回到Mattson算法的实际应用场景，我们通常是针对固定大小的缓存来统计栈距离、生成命中率曲线，所以这种情况下算法的时间复杂度本质上是线性的O(N)。

内容的提问来源于stack exchange，提问作者Anime Zone