知识卡片
摊销看长期成本
内容
摊销分析把一串操作放在一起衡量，能解释某次昂贵操作如何为未来省钱。ArrayList扩容和并查集路径压缩都属于这种模式。发散：系统高吞吐不代表每次延迟都稳定，还要关注抖动。
参考来源
- 位置：《你真的会写代码吗-2021》第3章《速度的要求：时间效率》"3.3.4 摊销时间复杂度"及"3.3.5 可调整大小数组的摊销分析"（源文件：_epub-src/OEBPS/Text/0013.xhtml）
- 结论依据：原文明确"标准分析侧重于算法的单次运行，而摊销分析则考虑一系列运行的组合。后者最适合于通过执行额外的操作来提高未来调用性能的算法"，并以ArrayList扩容"添加n个元素需要的时间为O(n)"为例说明单次昂贵操作如何被长期摊平。
- 原始内容：标准分析侧重于算法的单次运行，而摊销分析则考虑一系列运行的组合……这些额外的操作是一种投资：它们是当下为了未来的收益而付出的成本……添加操作以摊销常数时间运行；也就是说，添加n个元素需要的时间为O(n)。