03. 算法复杂度分析与计算复杂性理论

1. 函数的增长与渐进分析 (Growth of Functions and Asymptotic Analysis)

在算法分析中，我们关心的是当输入规模 $n$ 变得非常大时，算法所需资源（如时间或空间）的增长趋势。我们使用渐进符号来描述这种增长趋势，忽略常数因子和低阶项。

1.1 核心渐进符号：$O$, $\Omega$, $\Theta$

这三个符号是评估算法复杂度的基石，是考试的绝对重点。它们的定义和区别必须清晰掌握。

符号 (Notation)	名称 (Name)	含义 (Meaning)	数学定义 (Definition)	通俗理解
$O(g(x))$	大 O (Big-O)	增长上界 (Upper Bound)	存在正常数 $C, k$，使得对所有 $x > k$，有 $\vert{f(x)}\vert \le C\vert{g (x)}\vert$	$f(x)$ 的增长至多像 $g(x)$ 一样快
$\Omega(g(x))$	大 Omega (Big-Omega)	增长下界 (Lower Bound)	存在正常数 $C, k$，使得对所有 $x > k$，有 $\vert{f (x)}\vert \ge C\vert{g (x)}\vert$	$f(x)$ 的增长至少像 $g(x)$ 一样快
$\Theta(g(x))$	大 Theta (Big-Theta)	紧确界 (Tight Bound)	$f(x) = O(g(x))$ 且 $f(x) = \Omega(g(x))$	$f(x)$ 的增长速度与 $g(x)$ 相同

---

难点详述：如何理解和使用大 O 符号？

大 O 符号是三者中最常用的，因为它描述了算法性能的“最坏情况”保证。

• 核心思想：我们想给函数 $f(x)$ 的增长率找一个“天花板” $g(x)$。只要 $x$ 足够大（$x>k$），$f(x)$ 就永远不会超过 $g(x)$ 的某个常数倍（$C \cdot g(x)$）。

• 清晰用例：证明 $f(n) = 2n^2 + 5n + 10$ 是 $O(n^2)$。

  1. 目标：我们需要找到正常数 $C$ 和 $k$，使得当 $n > k$ 时，不等式 $2n^2 + 5n + 10 \le C \cdot n^2$ 恒成立。
  2. 推导： 为了让不等式成立，我们可以对左侧进行放缩。假设 $n \ge 1$：
     • $5n \le 5n^2$
     • $10 \le 10n^2$ 因此，
     $$2n^2 + 5n + 10 \le 2n^2 + 5n^2 + 10n^2 = 17n^2$$
  3. 结论：我们找到了 $C=17$ 和 $k=1$。当 $n > 1$ 时，$2n^2 + 5n + 10 \le 17n^2$ 成立。因此，根据定义，$f(n) = O(n^2)$。

• 重要结论：对于一个多项式 $f(x) = a_m x^m + \dots + a_1 x + a_0$，其增长率由最高次项决定。

  $$f(x) = O(x^m)$$

1.2 常见函数增长阶

**必须熟记**以下函数的增长速度排序，这对于快速比较算法优劣至关重要。

慢 $\to$ 快:

$$O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < \dots < O(2^n) < O(n!) < O(n^n)$$

• $O(1)$: 常数时间 (Constant)
• $O(\log n)$: 对数时间 (Logarithmic)
• $O(n)$: 线性时间 (Linear)
• $O(n^c)$: 多项式时间 (Polynomial)
• $O(c^n)$: 指数时间 (Exponential)
• $O(n!)$: 阶乘时间 (Factorial)

2. 算法的复杂度 (Complexity of Algorithms)

算法的复杂度是衡量其效率的度量，主要分为时间复杂度和空间复杂度。

• 时间复杂度 (Time Complexity): 算法执行所需的基本操作次数。
• 空间复杂度 (Space Complexity): 算法执行所需的内存空间量。

2.1 复杂度分析类型

对于同一个算法，输入数据的不同特性可能导致其运行时间产生巨大差异。因此，我们从不同角度进行分析。

分析类型	定义	关注点	示例：插入排序 (Insertion Sort)
最佳情况 (Best-case)	算法运行时间最短的输入情况。	理想条件下的性能极限。	输入数组已排序。只需 $n-1$ 次比较，无需交换元素。复杂度为 $\Theta(n)$。
最坏情况 (Worst-case)	算法运行时间最长的输入情况。	提供性能下限保证，是实际应用中最受关注的指标。	输入数组逆序。每次插入都需要与所有已排序元素比较和交换。复杂度为 $\Theta(n^2)$。
平均情况 (Average-case)	在所有可能的输入上，算法的期望运行时间。	算法在“典型”情况下的表现。	输入数组是随机排列的。期望复杂度为 $\Theta(n^2)$。

重点：在没有特别说明的情况下，我们讨论的“复杂度”通常指最坏情况时间复杂度。

3. 问题的计算复杂性 (Computational Complexity of Problems)

计算复杂性理论研究的是问题本身的难易程度，而非解决某个问题的特定算法。

3.1 核心概念：输入规模 (Input Size)

这是一个非常关键且容易混淆的概念。

• 定义：问题的输入规模 (Input Size) 是指用于编码该问题实例所需的比特数。

• 陷阱与辨析：算法的复杂度是关于输入规模的函数，而不是输入值的大小。

• 循循善诱的例子：判断合数问题 (COMPOSITE)

  1. 问题：给定一个正整数 $n$，判断它是否为合数（即能否被大于 1 且小于自身的整数整除）。
  2. 朴素算法：从 $d=2$ 到 $\sqrt{n}$ 逐个尝试，看 $d$ 是否能整除 $n$。这个算法的计算步骤大约是 $\sqrt{n}$ 次除法。
  3. 初看之下：这个算法是 $O(\sqrt{n})$，似乎是多项式时间，效率很高。
  4. 深入分析：这是错误的看法！
     • 计算机接收的输入 $n$ 是以二进制形式表示的。表示一个整数 $n$ 需要的比特数，即输入规模，是 $L \approx \log_2 n$。
     • 因此，算法的运行时间 $O(\sqrt{n})$ 如果用输入规模 $L$ 来表示，就是 $O(\sqrt{2^L}) = O(2^{L/2})$。
     • 结论：这个算法的时间复杂度是输入规模 $L$ 的指数函数，而不是多项式函数。因此，它是一个低效的算法。

3.2 复杂性类 (Complexity Classes)

复杂性理论将判定问题（回答是/否的问题）划分为不同的类别。

• P 类 (Class P - Polynomial time)

  • 定义：所有可以由一个确定性算法在多项式时间内解决的判定问题集合。
  • 通俗理解：这类问题被认为是**“易解的” (Tractable)**。
  • 示例：排序问题、查找最大值、判断一个数是否为素数（已于 2002 年被证明）。

• NP 类 (Class NP - Nondeterministic Polynomial time)

  • 定义：如果一个问题的“是”解存在一个**“证明” (Certificate/Witness)，并且这个证明可以在多项式时间内被验证 (Verify)**，那么该问题就属于 NP 类。
  • P 与 NP 的核心区别：
    • P 类：找到解很快。
    • NP 类：验证解很快。（但找到解可能非常慢）
  • 用例：旅行商问题 (TSP) 的判定版本
    • 问题：给定 $n$ 个城市和它们之间的距离，是否存在一条总长度小于 $k$ 的回路，恰好访问每个城市一次？
    • 证明 (Certificate)：一条具体的路径（如 A -> C -> B -> D -> A）。
    • 验证 (Verification)：给定这条路径，计算其总长度并与 $k$ 比较。这个验证过程是多项式时间的（线性时间）。
    • 结论：TSP 问题属于 NP 类。但是，目前没有人知道如何在多项式时间内找到这样一条路径。

• P 与 NP 问题 (P vs. NP Problem)

  • 已知：$P \subseteq NP$。因为如果一个问题能在多项式时间内解决，那么它的解自然也能在多项式时间内被验证。
  • 核心悬念：$P = NP$ 是否成立？ 这是计算机科学领域最重要、最著名的未解难题。大多数科学家相信 $P \ne NP$。

• NP-完全 (NP-Complete, NPC) 和 NP-难 (NP-Hard)

  • NP-完全 (NPC)：
    1. 它是一个 NP 问题。
    2. 它是 NP 中最难的问题。任何其他 NP 问题都可以在多项式时间内“归约”到它。
    • 意义：如果任何一个 NPC 问题被发现在多项式时间内可解，那么所有 NP 问题都可以在多项式时间内解决，即 $P=NP$。
  • NP-难 (NP-Hard)：
    • 定义：一个问题至少和任何 NPC 问题一样难。它不一定是 NP 问题。
    • 实践指导：当你在工作中遇到的问题被证明是 NPC 或 NP-Hard 时，通常意味着你应该放弃寻找一个完美的、高效的通用解法，转而寻求近似解、启发式算法或针对特定情况的特解。