408 数据结构 · 知识图谱

复杂度分析 → 所有算法

大O表示法是评估所有算法效率的基础工具，时间/空间复杂度的分析贯穿全部章节。

栈 → DFS 深度优先搜索

DFS的递归调用栈是栈结构的直接应用，后进先出保证深入优先遍历。

队列 → BFS 广度优先搜索

BFS使用队列保证逐层访问，先进先出特性实现层序遍历。

二叉树 → 堆与堆排序

堆是逻辑上的完全二叉树，物理上用数组存储，堆排序由此而来。

BST → 折半查找 → B树

BST中序遍历即有序序列，折半查找需有序表，B树是其多路扩展。

AVL → BST 平衡优化

AVL通过4种旋转保证O(log n)，防止BST退化为链表。

快排 → 归并排序（分治）

同用分治思想：快排"先分再排"，归并"先排再合"。复杂度相同，稳定性不同。

散列表 → 折半查找

散列表平均O(1)，远快于折半O(log n)，但不支持有序遍历。

Dijkstra → Floyd

Dijkstra贪心求单源，Floyd动态规划求多源，后者可处理负权边。

Prim → Kruskal (MST)

同求最小生成树：Prim顶点出发（稠密图），Kruskal边排序（稀疏图+并查集）。

拓扑排序 → 关键路径

关键路径的第一步即拓扑排序。AOV网关注活动先后，AOE网关注最短完成时间。

外部排序 → 多路归并

大数据量需外部排序，败者树减少I/O次数，置换-选择生成更长归并段。