算法复杂度：从时间到计算的全面解析
1. 算法时间复杂度基础
算法的时间复杂度衡量了算法执行时间随输入规模增长的变化趋势。对于给定长度为 $n$ 的输入，算法 $A$ 执行的最大步骤数 $f(n)$ 是 $n$ 的函数。而算法 $A$ 的时间复杂度是 $f(n)$ 的最小可能上界 $g(n)$，记为 $O(g(n))$。
1.1 常见时间复杂度类
常见的时间复杂度类及其示例算法如下表所示：
| 名称 | 运行时间 | 示例算法 |
| — | — | — |
| 常数 | $O(1)$ | 从长度为 $n$ 的数组中随机选择一个元素 |
| 对数 | $O(\log n)$ | 对排序数组进行二分查找 |
| 线性 | $O(n)$ | 图的单源最短路径问题 |
| 线性对数 | $O(n \log(n))$ | Watts - Strogatz 小世界图的采样 |
| 二次 | $O(n^2)$ | 所有节点的介数中心性 |
| 三次 | $O(n^3)$ | 加权图中的最短路径（Floyd 算法） |
| 指数 | $2^{O(n)}$ | 枚举图的所有循环 |
| 阶乘 | $O(n!)$ | 枚举完全图的所有路径 |
这些复杂度类之间存在如下关系：
$O(1) < O(\log n) < O(n) < O(n \log^{\ell}n) < O(n^k) < O(b^n) < O(n!)$
其中 $\ell, b, k \in R^+$，$\ell \geq 1$，$b > 1$，$k &
