Data Structure for Dynamic Sequence Interface

回顾

回顾一下 dynamic sequence interface 的定义：维护一个数据序列 $x_0, x_1, x_2, ..., x_{n-1}$

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

• seq-iter()：遍历 $x_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)$

实现

静态数组（Static Arrays）

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

操作	时间复杂度	空间复杂度
len	$O(1)$	$O(1)$
seq-iter	$O(n)$	$O(n)$
at	$O(1)$	$O(1)$
set-at	$O(1)$	$O(1)$
insert-at	$O(n)$	$O(n)$
delete-at	$O(n)$	$O(n)$

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

链表（Linked Lists）

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

操作	时间复杂度	空间复杂度
len	$O(1)$	$O(1)$
seq-iter	$O(n)$	$O(n)$
at	$O(n)$	$O(1)$
set-at	$O(n)$	$O(1)$
insert-at	$O(n)$	$O(n)$
delete-at	$O(n)$	$O(n)$
insert/delete left/right	$O(1)$	$O(1)$

动态数组 （Dynamic Arrays）

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

Insert-right

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

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

Delete-right

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

复杂度

操作	时间复杂度	空间复杂度
len	$O(1)$	$O(1)$
seq-iter	$O(n)$	$O(n)$
at	$O(1)$	$O(1)$
set-at	$O(1)$	$O(1)$
insert-at	$O(n)$	$O(n)$
delete-at	$O(n)$	$O(n)$
insert/delete left/right	$O(1)$	$O(1)$