复杂度

背景假设

同一个算法在不同计算机上的运行速度存在差异，实际运行时间难以在理论上精确计算，实际测量又受限于硬件与环境。因此，我们通常不直接计算算法的实际用时，而是计算算法运行所需执行的基本操作的数量。

基本操作是指算法执行过程中不可再拆分的最小运算单元。不同算法中，基本操作的界定可能有所差异，但通常包括加减乘除等算术运算、变量读写与赋值、基本数据类型的内存访问等。

值得注意的是，同一抽象目标下的不同物理实现，其执行单次“逻辑操作”所需的基本操作数量可能截然不同。对物理实现层的穿透式审视，正是复杂度分析的根基所在。

衡量算法的效率，必须结合数据规模。数据规模通常指输入所包含的数字个数、图中顶点数与边数等量化指标。一般而言，数据规模越大，算法所需的基本操作次数就越多。评判一个算法的效率，核心并非观察其在某一个特定数据规模下的绝对用时，而是观察其时用随数据规模增长而呈现的增长趋势，也就是时间复杂度。

“用时随数据规模而增长的趋势”这一概念需要精确的形式化描述，这便是下面引入渐进符号的目的。

渐进复杂度

对于函数 $f(n)$ 和 $g(n)$：

  • 称 $f(n) = \Theta(g(n))$，当且仅当 $\exists c_1, c_2, n_0 > 0$，使得 $\forall n \ge n_0$，有 $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$。
    • 含义：$f(n)$ 与 $g(n)$ 同阶，二者增长速度相当。
  • 称 $f(n) = O(g(n))$，当且仅当 $\exists c, n_0 > 0$，使得 $\forall n \ge n_0$，有 $0 \le f(n) \le c \cdot g(n)$。
    • 含义：$f(n)$ 的增长速度不超过 $g(n)$，是上界。
  • 称 $f(n) = \Omega(g(n))$，当且仅当 $\exists c, n_0 > 0$，使得 $\forall n \ge n_0$，有 $0 \le c \cdot g(n) \le f(n)$。
    • 含义：$f(n)$ 的增长速度不低于 $g(n)$，是下界。

上述三种符号，依次描述了一个函数增长的紧确界、上界和下界。在分析最坏时间复杂度时最常用的是大O符号，它刻画的是算法在最不利的输入下，运行时间的增长上限。

主定理

主定理为分析特定形式的递归算法时间复杂度提供了统一工具。

若某一递归算法的时间复杂度 $T(n)$ 满足递推关系：

$$ T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n) $$

即：将规模为 $n$ 的问题，拆分为 $a$ 个规模为 $n/b$ 的子问题，拆分与合并的代价为 $f(n)$。那么，$T(n)$ 的渐进紧确界可按照以下三种情形确定：

$$ T(n) = \begin{cases} \Theta(n^{\log_b a}) & \text{若 } f(n) = O(n^{\log_b a - \epsilon}), \ \epsilon > 0 \\ \Theta(f(n)) & \text{若 } f(n) = \Omega(n^{\log_b a + \epsilon}), \ \epsilon \ge 0 \text{，且存在 } c < 1, N > 0, \\ &\text{使得 } \forall n > N \text{ 有 } a \cdot f(n/b) \le c \cdot f(n) \\ \Theta(n^{\log_b a} \log^{k+1} n) & \text{若 } f(n) = \Theta(n^{\log_b a} \log^k n), \ k \ge 0 \end{cases} $$

三种情形的直观解读如下：

  1. 叶节点代价占主导。子问题数量多，合并代价相对轻，总复杂度由底层叶节点的数量级 $n^{\log_b a}$ 决定。
  2. 合并代价占主导。合并步骤足够重，且满足正则条件 $a \cdot f(n/b) \le c \cdot f(n)$，总复杂度由顶层合并代价 $f(n)$ 决定。
  3. 二者同阶博弈。叶节点代价与合并代价相当，会附加一个对数因子，总复杂度为 $n^{\log_b a} \log^{k+1} n$。

对于不满足上述形式的递归式，主定理无法直接套用，需借助递归树、代入法等其他分析手段。

复杂度分类

算法的运行用时不仅由输入规模决定，也与输入的具体内容相关。因此，时间复杂度依据对输入情形的假设，分为几类：

  • 最坏时间复杂度：在给定规模的所有可能输入中，算法执行基本操作次数的最大值。它保证算法在任何输入下都不会超过这个上界。
  • 平均时间复杂度：在给定规模的输入空间上，依据某种概率分布（通常假设均匀分布），算法执行基本操作次数的期望值。
  • 均摊时间复杂度：针对一系列连续操作，将其中偶尔发生的昂贵操作的代价平摊到所有操作上，计算每个操作的平摊代价。它适用于分析单次操作代价波动较大，但连续执行总体可控的场景。

三者从不同角度刻画了算法的效率。最坏时间复杂度提供安全保障，平均时间复杂度描述典型行为，均摊时间复杂度适合分析批量操作的整体代价。

空间复杂度

类似的，算法运行过程中所占用的存储空间随输入规模的增长趋势，称为空间复杂度。

空间开销可粗略拆分为两部分：存储输入数据本身所必需的空间，以及算法在执行过程中额外开辟的辅助空间。不同物理实现方式，在辅助空间开销上往往存在显著差异——同样的逻辑结构，采用链式存储需额外保留指针，采用顺序存储则无需此类开销。这些差异将在后续数据结构的具体实现中逐一分析。

算法分析中，通常以时间复杂度为主，空间复杂度为辅。当存储资源有限时，空间复杂度会成为设计取舍中的关键约束。

枚举与模拟

递归与分治

搜索

贪心

二分

动态规划

倍增

前缀和与差分

双指针与滑动窗口