Data Structure for Dynamic Sequence Interface

回顾

回顾一下 dynamic sequence interface 的定义:维护一个数据序列 x0,x1,x2,...,xn1x_0, x_1, x_2, ..., x_{n-1}

  • len():返回数据序列的长度 n

  • seq-iter():遍历 x0,x1,x2,...,xn1x_0, x_1, x_2, ..., x_{n-1}

  • at(i):返回序号为 i 的数据xixi​

    • left() => at(0)

    • right() => at(n-1)

  • set-at(i, x):将序号为 i 的元素替换为 x

  • insert-at(i, x):将 x 插入到序号为 i 的位置上,同时将所有原来序号 ≥ i 的元素向右移动一个位置

  • delete-at(i): 将所有序号 ≥ i+1 的元素向左移动一个位置

  • set-at(i, x):语义上等同于连续执行 delete-at(i) 和 insert-at(i, x)

假设

  • 内存分配模型:分配一个长度为 n 数组的时间复杂度为 θ(n)θ(n)

实现

静态数组(Static Arrays)

静态数组的实现很容易,这里不讨论具体的实现,各个操作的计算复杂度如下表

操作

时间复杂度

空间复杂度

len

O(1)O(1)

O(1)O(1)

seq-iter

O(n)O(n)

O(n)O(n)

at

O(1)O(1)

O(1)O(1)

set-at

O(1)O(1)

O(1)O(1)

insert-at

O(n)O(n)

O(n)O(n)

delete-at

O(n)O(n)

O(n)O(n)

可以看出,在 insert/delete-at 的操作上,性能不够理想。

链表(Linked Lists)

链表是基于指针的数据结构,它将每个数据如糖葫芦一般串起来,并维护 left/head, right/tail 两个指针。这样 insert/delete left/right 的复杂度都减小到了 O(1)O(1)。这对于 stack,queue,deque 等特殊 ADT 都是非常合适的。但对于 dynamic sequence interface 来说,at 操作的复杂度变差了。整体分析如下表所示:

操作

时间复杂度

空间复杂度

len

O(1)O(1)

O(1)O(1)

seq-iter

O(n)O(n)

O(n)O(n)

at

O(n)O(n)

O(1)O(1)

set-at

O(n)O(n)

O(1)O(1)

insert-at

O(n)O(n)

O(n)O(n)

delete-at

O(n)O(n)

O(n)O(n)

insert/delete left/right

O(1)O(1)

O(1)O(1)

动态数组 (Dynamic Arrays)

dynamic arrays 内部则维护一个长度一定的数组,且在必要时将该数组缩小或者扩大,通过将操作成本均摊到每次操作中,使得 insert/delete right 的均摊复杂度达到 O(1)O(1)

Insert-right

当 dynamic arrays 内部的数组元素数量达到 n 时,扩容到 2n,因此连续插入的复杂度变成:

cost=θ(1+2+4+8+...+nn)=θ((12n)(12)n)=θ(1)cost = θ(\frac{1 + 2 + 4 + 8 + ... + n}{n}) = θ(\frac{(1 - 2^n)}{(1-2)n}) = θ(1)

Delete-right

当 dynamic arrays 内部的数组元素数量小于 n4\frac{n}{4} 时,将其缩小到 n2\frac{n}{2} 。具体证明待补充

复杂度

操作

时间复杂度

空间复杂度

len

O(1)O(1)

O(1)O(1)

seq-iter

O(n)O(n)

O(n)O(n)

at

O(1)O(1)

O(1)O(1)

set-at

O(1)O(1)

O(1)O(1)

insert-at

O(n)O(n)

O(n)O(n)

delete-at

O(n)O(n)

O(n)O(n)

insert/delete left/right

O(1)O(1)

O(1)O(1)