“分摊复杂性”的原则是，尽管当你做某事时可能相当复杂，因为它不经常做，它被认为“不复杂”。例如，如果你创建一个二叉树，需要时不时地进行平衡——比如每次 2^n插入一次——因为尽管平衡树非常复杂，但是每 n 次插入只会发生一次(例如，在插入号256处平衡一次，然后在512、1024等处平衡一次)。在所有其他的插入中，复杂度是 O (1)-是的，每 n 次插入都需要 O (n) ，但这只是 1/n概率-所以我们将 O (n)乘以1/n 得到 O (1)。这就是所谓的“ O (1)的摊销复杂度”——因为当你添加更多的元素时，重新平衡树所花费的时间是最小的。
与非摊销复杂性一样，用于摊销复杂性的大 O 表示法忽略了固定的初始开销和固定的性能因素。因此，为了评估大 O 分期付款的性能，你通常可以假设任何分期付款的操作序列将“足够长”，以分期付清固定的启动费用。具体地说，对于 std::vector<>示例，这就是为什么您不需要担心是否会遇到 N附加操作: 分析的渐近性质已经假定您会遇到。
put(x): Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
Pop each element off the right-hand stack and
push it onto the left-hand stack. This effectively
reverses the right-hand stack onto the left-hand stack.
Pop and return the top element of the left-hand stack.
现在，我声明 put和 get的摊销成本是 O(1)，假设我以一个空队列开始和结束。分析很简单: 我总是将 put放在右侧堆栈上，将 get放在左侧堆栈上。因此，除了 If子句之外，每个 put都是 push，每个 get都是 pop，它们都是 O(1)。我不知道执行 If子句多少次——这取决于 put和 get的模式——但是我知道每个元素从右边堆栈到左边堆栈只移动一次。因此，在整个序列的 n 个 put和 n 个 get上的总成本是: n 个 pushes，n 个 pops 和 n 个 get8s，其中 get8是一个 pop，接着是一个 push: 换句话说，2n 个操作(n 个 put和 n 个 gets)导致2n 个 pushes 和2n 个 pops。所以单个 put或 get的摊销成本是一个 push和一个 pop。
请注意，银行家队列之所以被称为银行家队列，正是因为摊销复杂性分析(以及“摊销”这个词与金融的关联)。银行家的队列是过去常见的面试问题的答案，尽管我认为它现在被认为太有名了: 想出一个队列，在分摊的 O (1)时间内实现以下三个操作:
