deque如何具有摊销的常数时间复杂度

Question

我读到这里从一个std ::双端队列具有以下特点公认的答案

1- Random access - constant O(1)
2- Insertion or removal of elements at the end or beginning - amortized constant O(1)
3- Insertion or removal of elements - linear O(n)

我的问题是关于第2点.双端队列如何在结束或开始时进行摊销？

我知道a std::vector在最后插入时具有摊销的常数时间复杂度.这是因为矢量是连续的并且是动态阵列.因此,当最后一个内存耗尽push_back时,它将分配一个全新的内存块,将现有项目从旧位置复制到新位置,然后从旧位置删除项目.我理解的这个操作是摊销不变的.这如何适用于双端队列？如何在双端队列的顶部和底部插入是否可以摊销.我的印象是它应该是常数O(1).我知道一个双端队列由内存块组成.

Answer 1

deque的通常实现基本上是指向固定大小节点的指针的向量.

分配固定大小的节点显然具有恒定的复杂性,因此非常容易处理 - 您只需分摊在该节点中的多个项目之间分配单个节点的成本,以便为每个节点获得恒定的复杂性.

指针部分的向量是(稍微)更有趣的.当我们分配足够的固定大小节点时,指针向量已满,我们需要增加向量的大小.就像std::vector,我们需要将其内容复制到新分配的向量,因此它的增长必须遵循几何(而不是算术)进展.这意味着我们有更多的指针可以复制,我们的复制越来越少,因此复制指针的总时间保持不变.

作为旁注:"向量"部分通常被视为循环缓冲区,因此如果您将deque用作队列,不断添加到一端并从另一端移除不会导致重新分配向量 - - 这只意味着移动头部和尾部指针,以跟踪指定时间内哪些指针处于"活动状态".