"amortized" 这个词在算法的摊销分析中是什么意思？

Question

我显然熟悉提到它是平均下限等的文本...但仍然想知道为什么将摊销这个词放在那里？

为什么用amortize描述算法分析？

Answer 1

因为提出这个想法的计算机科学家正在使用金融类比。

您通过分期付款（可能使用 抵押贷款 来分期偿还大笔支出（例如建造新房）。

类似地，在算法的摊销分析中，您通过将其成本分摊到后续操作（或银行家模型中的先前操作）来为巨大且不常见的事件（复制整个矢量，当它变满时）付出代价。