时间复杂度
概述
时间复杂度 是用渐近记号（、、）描述的算法运行时间的上界、下界或紧界。它是评估算法效率的标准度量方式，使不同算法之间的比较具有数学上的严谨性。
定义
时间复杂度
算法的时间复杂度是用渐近记号表示的运行时间 的增长行为：
- 记号（上界）： 表示 的增长速率不超过 的常数倍。
- 记号（下界）： 表示 的增长速率不低于 的常数倍。
- 记号（紧界）： 表示 的增长速率与 在常数因子范围内相同。
核心性质
- 记号提供最精确的描述，是CLRS中最常用的渐近记号。
- 记号给出运行时间的最坏情况保证，在实际应用中最常用。
- 渐近记号的形式化定义在第3章（3.1节和3.2节）中详细展开。
- 时间复杂度关注的是 时的行为，小规模输入下的常数因子差异可能被忽略。
章节扩展
第2章：入门
- 2.2 算法分析：首次使用 和 记号描述插入排序的运行时间，引入渐近分析的基本思想。
第3章：运行时间刻画
- 3.1 O记号、Ω记号与Θ记号：渐近记号的正式定义和直觉理解。
- 3.2 渐近记号的形式化定义：渐近记号的严格数学定义和性质。
第22章：图算法复杂度分析
图算法的复杂度分析引入了新的维度：不仅要看输入规模，还要看顶点数 V 和边数 E 的关系。
- 稀疏图（E = O(V)）：BFS/DFS 为 O(V)，Dijkstra 用二叉堆为 O(V lg V)
- 稠密图（E = Θ(V²)）：Dijkstra 用数组为 O(V²)，Floyd-Warshall 为 O(V³)
- 超稀疏图（E << V lg V）：Johnson 用斐波那契堆为 O(V² lg V + VE)
选择算法时需根据图的稀疏程度选择不同实现。