均摊复杂度基础

一句话理解

均摊：单次可能贵，但一串操作平均下来便宜。

为什么要学

vector 扩容、并查集路径压缩，都有均摊。

讲解

vector push_back 偶发 O(n) 扩容，均摊 O(1)。分析时看总代价除以次数。

均摊不是每次都 O(1)，所以实时系统可能仍有卡顿，但竞赛看总时限。

例子

n 次 push_back 总复制量大约 2n，均摊常数。

常见错误

• 把均摊当成每次严格上限。
• 单次查询被卡成最坏却还用均摊数据结构的错误场景——竞赛总时限下通常仍可。