time-complexity - 如何分析在不同情况下行为可能发生变化的程序的复杂性？

Question

当我遇到这个问题时——使用两个堆栈来实现一个队列，我想知道如何分析它的复杂性。

以此为例：

• 对于 queue()，复杂度总是 O(1)，因为它只是简单地推入收件箱。
• 对于dequeue()，大部分时候复杂度也是O(1)，但是当发件箱为空时，需要一个循环将所有元素从收件箱移动到发件箱。那么这个操作的复杂度是多少呢？

分析此类问题时的想法是什么？

Answer 1

正如 Dave L. 在他的解释中所说，“每个元素将被推送两次并弹出两次，从而提供摊销的常数时间操作”。这是因为需要将 n 个元素从一个堆栈移动到另一个堆栈（花费 O(n) 时间）的每个出队将跟随仅花费 O(1) 时间的 n-1 个出队。

所以表达复杂性的一种方法dequeue()是说它已经摊销了常数时间，最好的情况是 O(1)，最坏的情况是 O(n)。