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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/data-structure-for-dynamic-sequence-interface.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.