Mika Field Notes

Article

算法导论-CH3-描述运行时间

本章研究当输入规模 $n$ 增大时，算法运行时间的主要变化趋势。我们使用渐近记号来简化对算法性能的描述，忽略掉不重要的常数项和低次项。

May 7, 2026 修考 7 min read

第三章：描述运行时间（函数的增长）

本章研究当输入规模 nn 增大时，算法运行时间的主要变化趋势。我们使用渐近记号来简化对算法性能的描述，忽略掉不重要的常数项和低次项。

一、 渐近记号 (Asymptotic Notation)

1. OO 记号：渐近上界 (Upper Bound)

  • 描述：OO 记号给出了函数的一个上界（最坏情况的保障）。
  • 直观理解：等价于数学中的“小于等于”关系 (≤\le)。它表示函数 f(n)f(n) 的增长阶不会超过 g(n)g(n) 的常数倍。
  • 例题： 若 T(n)=7n3+100n2−20n+6T(n) = 7n^3 + 100n^2 - 20n + 6
    • 则我们可以说 T(n)=O(n3)T(n) = O(n^3)。 同时也满足 T(n)=O(nc)T(n) = O(n^c)，其中 c≥3c \ge 3（如 O(n4)O(n^4) 也成立，但通常取最紧的阶）。

2. Ω\Omega 记号：渐近下界 (Lower Bound)

  • 描述：Ω\Omega 记号给出了函数的一个下界（最好情况的保障）。
  • 直观理解：等价于数学中的“大于等于”关系 (≥\ge)。它表示函数 f(n)f(n) 的增长阶至少是 g(n)g(n) 的常数倍。
  • 例题： 若 T(n)=7n3+100n2−20n+6T(n) = 7n^3 + 100n^2 - 20n + 6
    • 则我们可以说 T(n)=Ω(n3)T(n) = \Omega(n^3)。 同时也满足 T(n)=Ω(nc)T(n) = \Omega(n^c)，其中 c≤3c \le 3（如 Ω(n2)\Omega(n^2) 或 Ω(1)\Omega(1) 也成立）。

3. Θ\Theta 记号：紧确界 (Tight Bound)

  • 描述：当一个函数既有相同阶的上界又有相同阶的下界时，我们称其为紧确界。
  • 直观理解：等价于数学中的“等于”关系 (==)。上界与下界中间夹着的，就是紧确界。
  • 性质：f(n)=Θ(g(n))f(n) = \Theta(g(n)) 的前提是 f(n)f(n) 的阶与 g(n)g(n) 完全一致。

二、 渐近记号的数学定义

设 f(n)f(n) 和 g(n)g(n) 是定义在非负整数集上的非负函数。

  1. OO 记号： ∃c>0,n0>0,使得 ∀n≥n0,0≤f(n)≤cg(n)\exists c > 0, n_0 > 0, \text{使得 } \forall n \ge n_0, 0 \le f(n) \le cg(n)
  2. Ω\Omega 记号： ∃c>0,n0>0,使得 ∀n≥n0,0≤cg(n)≤f(n)\exists c > 0, n_0 > 0, \text{使得 } \forall n \ge n_0, 0 \le cg(n) \le f(n)
  3. Θ\Theta 记号： ∃c1,c2>0,n0>0,使得 ∀n≥n0,0≤c1g(n)≤f(n)≤c2g(n)\exists c_1, c_2 > 0, n_0 > 0, \text{使得 } \forall n \ge n_0, 0 \le c_1g(n) \le f(n) \le c_2g(n)

三、 重要定理与极限关系

定理 3.1

对于任意两个函数 f(n)f(n) 和 g(n)g(n)，有： f(n)=Θ(g(n))f(n) = \Theta(g(n)) 当且仅当 f(n)=O(g(n))f(n) = O(g(n)) 且 f(n)=Ω(g(n))f(n) = \Omega(g(n))。

极限角度理解（补充）

通过对比两个函数的阶，我们可以通过极限判断：

  • 若 lim⁡n→∞f(n)g(n)=0\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0，则 f(n)=o(g(n))f(n) = o(g(n))（低阶）。
  • 若 lim⁡n→∞f(n)g(n)=C>0\lim_{n \to \infty} \frac{f(n)}{g(n)} = C > 0，则 f(n)=Θ(g(n))f(n) = \Theta(g(n))（同阶）。
  • 若 lim⁡n→∞f(n)g(n)=∞\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty，则 f(n)=ω(g(n))f(n) = \omega(g(n))（高阶）。

四、 排序算法的时间复杂度证明与分析

1. 插入排序 (Insertion Sort)

  • 最坏情况：O(n2)O(n^2)。当数组完全倒序时，每一轮都需要移动大量元素。
    • 分析：共有 n−1n-1 轮，第 ii 轮需要 i−1i-1 次比较和交换，求和得：∑i=1n(i−1)=n(n−1)2=Θ(n2)\sum_{i=1}^{n} (i-1) = \frac{n(n-1)}{2} = \Theta(n^2)。
  • 最好情况：Ω(n)\Omega(n)。当数组已经有序时，只需进行 n−1n-1 次比较。
  • Ω(n2)\Omega(n^2) 下界的证明思路（参考 Figure 3.1）： 若前 n/3n/3 个位置包含数组中最大的 n/3n/3 个值，那么每一个值都必须跨过中间的 n/3n/3 个位置才能到达最终位置。总移动步数至少为 (n/3)×(n/3)=n2/9(n/3) \times (n/3) = n^2/9，因此是 Ω(n2)\Omega(n^2)。

image-20260507153630614

2. 选择排序 (Selection Sort) —— 练习 3.1-2

选择排序无论在最好还是最坏情况下，时间复杂度均为 Θ(n2)\Theta(n^2)。

  • 伪代码分析： 外层循环执行 n−1n-1 次。 内层循环寻找剩余元素中的最小值，执行次数依次为 n−1,n−2,…,1n-1, n-2, \dots, 1。

  • 精确计算：

    T(n)=∑i=1n−1(i+c)=12n2+(c−12)n−c=Θ(n2)T(n) = \sum_{i=1}^{n-1} (i + c) = \frac{1}{2}n^2 + (c - \frac{1}{2})n - c = \Theta(n^2)

    其中 cc 为交换操作所需的常数时间。

3. 归并排序 (Merge Sort)

  • 归并排序在最好、平均、最坏情况下的时间复杂度均为 Θ(nlg⁡n)\Theta(n \lg n)。
    • 注：修正了原笔记中关于归并排序为 Θ(n2)\Theta(n^2) 的误写。

五、 图形化理解

image-20260507153714016