Ch14 数据结构与算法 · 思维导图 (Mermaid)¶

一 · 章节主入口¶

🌳 Ch14 章 知识图谱
├─ §00 基础
│  └─ 复杂度
│  └─ 递归
│  └─ 分治
├─ §01 数组哈希
│  └─ 动态数组
│  └─ 哈希表
│  └─ 滑动窗口
├─ §02 链表栈队
│  └─ 链表
│  └─ 栈
│  └─ 队列
├─ §03 树
│  └─ 二叉树
│  └─ BST
│  └─ 平衡树
│  └─ 堆
├─ §04 图
│  └─ BFS
│  └─ DFS
│  └─ 最短路
│  └─ MST
├─ §05 排序搜索
│  └─ 比较排序
│  └─ 线性排序
│  └─ 二分

二 · 复杂度速查¶

graph LR
    A[算法] --> B[时间 T_n]
    A --> C[空间 S_n]
    B --> B1[O_1 常数]
    B --> B2[O_log n 对数]
    B --> B3[O_n 线性]
    B --> B4[O_n log n]
    B --> B5[O_n²]
    B --> B6[O_2ⁿ]

三 · §00 基础子图¶

🌳 Ch14 章 知识图谱
├─ 复杂度
│  └─ O/Ω/Θ
│  └─ 主定理
│  └─ 平摊
├─ 递归
│  └─ 基例
│  └─ 递归式
│  └─ 尾递归
├─ 分治
│  └─ 归并
│  └─ 快排
│  └─ 二分

四 · §01 数组哈希子图¶

🌳 Ch14 章 知识图谱
├─ 数组
│  └─ 静态
│  └─ 动态
├─ 双指针
│  └─ 对撞
│  └─ 快慢
├─ 滑动窗口
│  └─ 固定
│  └─ 变长
├─ 哈希
│  └─ 链地址
│  └─ 开放定址
│  └─ 一致性哈希

五 · §02 链表栈队子图¶

🌳 Ch14 章 知识图谱
├─ 链表
│  └─ 单链
│  └─ 双链
│  └─ 循环
├─ 栈
│  └─ LIFO
│  └─ 单调栈
│  └─ 表达式
├─ 队列
│  └─ FIFO
│  └─ 优先队列
│  └─ 双端
├─ 应用
│  └─ LRU
│  └─ BFS
│  └─ DFS

六 · §03 树子图¶

🌳 Ch14 章 知识图谱
├─ 二叉树
│  └─ 遍历
│  └─ 重建
├─ BST
│  └─ 查找
│  └─ 插入
│  └─ 删除
├─ 平衡
│  └─ AVL
│  └─ 红黑
│  └─ 伸展
├─ 字典树
│  └─ Trie
├─ 堆
│  └─ 最小堆
│  └─ 最大堆
│  └─ 二项堆

七 · §04 图子图¶

🌳 Ch14 章 知识图谱
├─ 遍历
│  └─ BFS
│  └─ DFS
│  └─ 拓扑
├─ 最短路
│  └─ Dijkstra
│  └─ Bellman-Ford
│  └─ Floyd
├─ MST
│  └─ Prim
│  └─ Kruskal
├─ Union-Find
│  └─ 路径压缩
│  └─ 按秩合并
├─ 应用
│  └─ GNN
│  └─ SLAM
│  └─ 路由

八 · §05 排序搜索子图¶

🌳 Ch14 章 知识图谱
├─ 比较排序
│  └─ 冒泡
│  └─ 插入
│  └─ 选择
│  └─ 快排
│  └─ 归并
│  └─ 堆排
├─ 线性排序
│  └─ 计数
│  └─ 基数
│  └─ 桶
├─ 自适应
│  └─ Tim
│  └─ 内省
├─ 搜索
│  └─ 顺序
│  └─ 二分
│  └─ 哈希

九 · 跨章桥接¶

graph TB
    C12[Ch12 GNN] --> T1
    C13[Ch13 OS] --> T2
    C07[Ch07 Transformer] --> T3
    C11[Ch11 SLAM] --> T4
    C05[Ch05 贝叶斯] --> T5

    T1[Ch14 §04 图算法 BFS/DFS] --> FUSE{AI 系统}
    T2[Ch14 §02 LRU] --> FUSE
    T3[Ch14 §03 Trie/KD-Tree] --> FUSE
    T4[Ch14 §04 Dijkstra 路径] --> FUSE
    T5[Ch14 §03 堆] --> FUSE

    FUSE --> APP[GNN/SLAM/LLM 加速]

十 · 演进时间线¶

timeline
    1960 : Quick Sort (Hoare)
    1962 : AVL Tree
    1964 : Heap Sort
    1968 : Dijkstra / BFS / DFS
    1972 : Union-Find
    1975 : Red-Black Tree
    1976 : Bellman-Ford
    1983 : Tarjan SCC
    1993 : Sleator-Tarjan Splay
    2002 : Tim Sort (Tim Peters)
    2004 : MapReduce
    2014 : Spark
    2017 : Transformer
    2020 : Flash Attention
    2023 : PagedAttention (vLLM)

十一 · 数据结构 vs 操作复杂度¶

操作	数组	链表	哈希	BST	堆
访问第 k	\(O(1)\)	\(O(n)\)	-	\(O(\log n)\)	\(O(n)\)
查找	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(\log n)\)	\(O(n)\)
插入	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(\log n)\)	\(O(\log n)\)
删除	\(O(n)\)	\(O(1)\)	\(O(1)\)	\(O(\log n)\)	\(O(\log n)\)
取最小	\(O(n)\)	\(O(n)\)	\(O(n)\)	\(O(\log n)\)	\(O(1)\)

十二 · 排序对比¶

算法	最优	平均	最坏	空间	稳定
冒泡	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	✓
插入	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	✓
选择	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	✗
快排	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n^2)\)	\(O(\log n)\)	✗
归并	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n)\)	✓
堆排	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(1)\)	✗
计数	\(O(n+k)\)	\(O(n+k)\)	\(O(n+k)\)	\(O(k)\)	✓
Tim	\(O(n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n)\)	✓

十三 · 图算法对比¶

算法	适用	时间	空间
BFS	无权最短路	\(O(V+E)\)	\(O(V)\)
DFS	拓扑 / 强连通	\(O(V+E)\)	\(O(V)\)
Dijkstra	加权非负	\(O((V+E) \log V)\)	\(O(V)\)
Bellman-Ford	有负权	\(O(VE)\)	\(O(V)\)
Floyd	全对最短	\(O(V^3)\)	\(O(V^2)\)
Prim	MST	\(O(E \log V)\)	\(O(V)\)
Kruskal	MST	\(O(E \log E)\)	\(O(V)\)

这张导图覆盖 Ch14 全章。建议: 先背章节主入口 → 按节背子图 → 排序 / 图算法对比表 → 演进时间线。