Amortized time

定义 Definition

Amortized time（摊还时间 / 均摊时间）：在算法分析中，把一系列操作的总成本平均分摊到每次操作上得到的“平均每次开销”。它强调序列整体的平均表现，即使个别操作可能很贵（例如偶尔扩容、重建），长期来看每次操作仍可能保持较低成本（常见如 *amortized O(1)*）。

发音 Pronunciation (IPA)

/əˈmɔːr.taɪzd taɪm/

例句 Examples

Array push is often amortized time O(1).
数组的 push/追加操作通常是 摊还时间 O(1)。

Although resizing can be expensive, a dynamic array supports appends in amortized time constant per operation over a long sequence.
尽管扩容可能很耗时，但在很长的一串操作中，动态数组的追加平均到每次操作上是摊还的常数时间。

词源 Etymology

amortized 源自动词 amortize，原义与“分期摊还（如贷款）”有关：把一次性的成本分散到多个时间段。算法里的 amortized time 借用了这个思路，把“偶尔很大的代价”分摊到多次操作上来评估平均成本。time 来自古英语 tīma，表示“时间”。

相关词 Related Words

• Aggregate
• Amortize
• Analysis
• Complexity
• Dynamic
• Potential
• Runtime
• Worst-Case

文学与经典教材作品 Literary Works

• Introduction to Algorithms（CLRS，《算法导论》）：在动态表、聚合分析、势能法等章节中系统使用 amortized time。
• The Art of Computer Programming（Donald E. Knuth，《计算机程序设计艺术》）：在数据结构与算法分析语境中讨论相关的平均/摊还思想。
• Purely Functional Data Structures（Chris Okasaki）：在函数式数据结构中大量使用摊还分析来证明操作序列的效率。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在并查集、动态数组等主题中常以摊还成本解释性能。