Amortized Cost

释义 Definition

摊还成本 / 均摊代价：指在一系列操作中，把偶尔发生的“昂贵操作”的开销分摊到多次操作上，从而得到每次操作的平均成本（上界）。常用于算法分析（如数据结构的动态扩容、并查集等）；在会计/金融语境中也可指“摊销后的成本”，但计算机科学中更常见的是“均摊分析”的含义。

例句 Examples

Appending an item to a dynamic array has amortized cost O(1).
向动态数组追加一个元素的均摊代价是 O(1)。

Although resizing is expensive, the amortized cost per insertion remains constant over many operations.
尽管扩容很昂贵，但在大量操作中，每次插入的均摊代价仍保持为常数。

发音 Pronunciation (IPA)

/mtazd kst/

词源 Etymology

amortized 来自法语与拉丁语词根，含义与“逐步偿还/摊销（to amortize）”相关，原本多用于债务或资产的分期摊销；在计算机科学中借用这一概念，强调把少数高成本事件“分摊”到多次操作上，以刻画长期平均开销。cost 源自古法语 coste（费用、代价）。

相关词 Related Words

• Amortized
• Amortization
• Aggregate
• Potential
• Average
• Worst-Case
• Complexity
• Dynamic Array

文学与名著用例 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein；《算法导论》）：在动态表（dynamic table）扩容、栈操作等章节中使用并解释 amortized cost。
• Algorithms（Robert Sedgewick & Kevin Wayne；《算法》）：在数据结构操作与分析中讨论均摊分析与 amortized cost。
• The Art of Computer Programming（Donald E. Knuth；《计算机程序设计艺术》）：在算法分析相关内容中涉及类似的均摊思想与成本分摊表述。