【MIT6.006】lec2 数据结构和动态数组

算法导论 - 第二讲：数据结构与动态数组

一、课程介绍

• 课程名称：6.006 算法导论
• 讲师：Erik Demaine
• 主题：数据结构与动态数组

二、接口与数据结构

• 接口（Interface）：
  • 定义了可以执行的操作。
  • 不涉及具体实现。
• 数据结构（Data Structure）：
  • 提供了接口的具体实现。
  • 包含数据的存储方式和操作算法。

三、序列（Sequence）接口

1. 静态序列（Static Sequence）

• 操作：
  • build：构建序列。
  • length：返回序列长度。
  • iteration：遍历序列。
  • get_at：获取指定位置的元素。
  • set_at：修改指定位置的元素。
• 实现：
  • 使用静态数组（Static Array）。
  • 时间复杂度：
    • get_at/set_at：$O(1)$。
    • build：$O(n)$。
    • iteration：$O(n)$。

2. 动态序列（Dynamic Sequence）

• 新增操作：
  • insert_at：在指定位置插入元素。
  • delete_at：删除指定位置的元素。
  • insert_first/insert_last：在序列开头或末尾插入元素。
  • delete_first/delete_last：删除序列开头或末尾的元素。
• 实现：
  • 使用动态数组（Dynamic Array）或链表（Linked List）。

四、数据结构实现

1. 静态数组（Static Array）

• 特点：
  • 存储在连续内存中。
  • 支持快速随机访问。
• 时间复杂度：
  • get_at/set_at：$O(1)$。
  • insert/delete：$O(n)$（需要移动元素）。

2. 链表（Linked List）

• 特点：
  • 每个节点包含一个元素和一个指向下一个节点的指针。
  • 动态存储，不连续。
• 时间复杂度：
  • insert_first/delete_first：$O(1)$。
  • get_at/set_at：$O(n)$（需要遍历）。
  • insert_last/delete_last：$O(1)$（需要维护尾指针）。

3. 动态数组（Dynamic Array）

• 特点：
  • 结合了静态数组和链表的优点。
  • 数组大小动态调整。
• 实现：
  • 维护一个数组 A 和两个变量：length（当前元素数量）和 size（数组大小）。
  • 当数组满时，分配一个更大的数组（通常是当前大小的两倍），并将元素复制过去。
• 时间复杂度：
  • get_at/set_at：$O(1)$。
  • insert_last/delete_last：$O(1)$（摊还时间）。
  • insert_at/delete_at：$O(n)$（可能需要移动元素）。

五、摊还分析（Amortized Analysis）

• 定义：通过平均操作序列的时间复杂度来评估操作的效率。
• 动态数组的摊还时间：
  • 插入操作的总时间是线性的，因此每次插入的摊还时间是 $O(1)$。
  • 即使某些操作（如数组扩容）需要线性时间，但大部分操作是常数时间，因此整体效率接近常数时间。

六、总结

• 静态数组：适合随机访问，但动态操作效率低。
• 链表：适合动态操作，但随机访问效率低。
• 动态数组：结合了两者的优点，适合大多数场景。
• Python 中的列表：实际上就是动态数组的实现。