# 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)$$ |