为何摊还分析会计方法中总摊还成本需为总实际成本的上界？

首先明确核心目的：我们做摊还分析，是为了证明最坏情况下每次操作的平均实际成本很低。

为什么总摊还成本必须是总实际成本的上界？

• 摊还成本是人为给每个操作“分配”的成本，本质是一种会计记账逻辑：把高成本操作的部分开销“预存”到之前低成本操作的摊还成本里（也就是所谓的“信用”）。
• 如果总摊还成本 ≤ 总实际成本，意味着我们分配的摊还成本不足以覆盖实际开销，说白了就是低估了实际总成本——这时候用摊还成本算出的平均成本，会比真实的平均实际成本低，这种结论没有任何说服力，因为我们要证明的是实际成本的平均表现优异，而非自己设定的摊还成本的平均表现。
• 只有当总摊还成本 ≥ 总实际成本时，摊还成本的平均值才是实际成本平均值的上界。也就是说，实际的平均成本一定≤我们算出的摊还平均成本。这时候如果算出摊还平均成本很低，就能直接得出“实际操作的平均成本确实很低”的结论，这才达成了摊还分析的目标。

对应CLRS中的表述：

若想通过摊还成本证明最坏情况下每次操作的平均成本较低，必须确保操作序列的总摊还成本是该序列总实际成本的上界。

这句话的本质是：只有总摊还成本兜得住总实际成本，我们用摊还成本算出的平均水平，才能作为实际成本平均水平的“上限参考”——你想证明实际平均成本低，就得先给出一个比它高的数值，再说明“实际的比这个还低”，逻辑才成立。如果反过来，你给的数值比实际成本还低，根本没法证明实际成本的优异表现。

内容的提问来源于stack exchange，提问作者Hugh Mann