10. 全课复杂度速查¶
附录导引
本页保留原讲义复杂度速查、结构选择模板和维护区锚点，集中放置复习辅助内容与后续扩展边界。
参考资料与引用边界¶
- 整理者：Lumner。
- 课程来源：根据
FDS/目录下现有数据结构课件整理。 - 原始讲义文件：
note/FDS_数据结构基础讲义.md。 - 引用边界：附录用于辅助复习，不替代课程正式教材、教师课件或考试要求。
| 结构/算法 | 关键操作 | 时间复杂度 | 备注 |
|---|---|---|---|
| 数组表 | 第 k 个元素 | \(O(1)\) | 随机访问 |
| 数组表 | 中间插入/删除 | \(O(N)\) | 需要移动元素 |
| 单链表 | 已知位置后插入 | \(O(1)\) | 查找位置另算 |
| 单链表 | 查找元素 | \(O(N)\) | 顺序扫描 |
| 栈 | Push/Pop/Top |
\(O(1)\) | 数组或链表均可 |
| 队列 | Enqueue/Dequeue |
\(O(1)\) | 循环数组或链表 |
| 二叉树遍历 | 访问所有节点 | \(O(N)\) | 每节点一次 |
| BST | 查找/插入/删除 | \(O(h)\) | 平衡时 \(O(\log N)\)，退化时 \(O(N)\) |
| 二叉堆 | FindMin |
\(O(1)\) | 根节点 |
| 二叉堆 | Insert/DeleteMin |
\(O(\log N)\) | 上滤/下滤 |
| 二叉堆 | BuildHeap |
\(O(N)\) | 自底向上下滤 |
| 并查集 | Union/Find |
近似均摊 \(O(1)\) | 按秩合并 + 路径压缩 |
| 线段树 | 建树 | \(O(N)\) | 节点数线性 |
| 线段树 | 区间查询/点更新 | \(O(\log N)\) | 查询可拆成少量节点 |
| 线段树 | 区间更新 | \(O(\log N)\) | 需要懒标记 |
| 邻接矩阵 | 判断边 | \(O(1)\) | 空间 \(O(V^2)\) |
| 邻接表 | 遍历边 | \(O(V+E)\) | 适合稀疏图 |
| 拓扑排序 | 输出拓扑序 | \(O(V+E)\) | 队列维护零入度点 |
11. 选结构的思考模板¶
面对一道数据结构题，可以按以下顺序拆解：
- 明确对象：数据是序列、集合、树、图，还是区间？
- 明确操作频率：查询多、修改多、插入删除多，还是合并多？
- 找不变量：结构要维护有序性、堆序性、连通代表元，还是区间聚合值？
- 估复杂度：最频繁操作必须足够快，偶尔操作可以慢一些。
- 处理边界：空结构、单元素、重复值、越界、负数、环、懒标记下传。
几个典型匹配：
| 需求 | 首选结构 |
|---|---|
| 频繁按下标访问 | 数组 |
| 频繁在已知位置插入删除 | 链表 |
| 最近未匹配对象 | 栈 |
| 先来先服务 | 队列 |
| 动态最小/最大优先级 | 堆 |
| 动态连通性/等价类 | 并查集 |
| 动态区间聚合查询 | 线段树 |
| 依赖顺序安排 | 图 + 拓扑排序 |
12. 后续扩展区¶
后续新增 FDS 课件时，建议按这个流程维护本文：
- 在“资料来源索引”新增文件、主题和页数。
- 判断它属于已有章节还是新章节。
- 如果属于已有章节，在对应小节中追加“定义、算法、复杂度、例子、易错点”。
- 如果是新主题，先在本节登记，再扩展为正式章节。
- 若新增算法有代码，优先补充 C 风格模板和复杂度表。
后续扩展登记表¶
| 新文件 | 主题 | 处理状态 | 应补章节 |
|---|---|---|---|
| 暂无新增文件 | 暂无新主题 | 未触发 | 后续确认 |