第 3 章函数的增长 (Growth of Functions)

核心结论

Θ 记号 (Theta-notation)：渐近紧界——存在正常数 \(c_1, c_2, n_0\) 使得 \(c_1 g(n) \leq f(n) \leq c_2 g(n)\) 对所有 \(n \geq n_0\) 成立。
O 记号 (Big-Oh)：渐近上界——只关注「最坏不超过」；比 Θ 弱，但更常用。
Ω 记号 (Big-Omega)：渐近下界——刻画「至少」。定理 3.1：\(f(n) = \Theta(g(n)) \iff f(n) = O(g(n))\) 且 \(f(n) = \Omega(g(n))\)。
o 记号 (little-oh) 与 ω 记号 (little-omega)：非紧界——分别对应 \(\lim f/g = 0\) 和 \(\lim f/g = \infty\)。
标准函数行为：多项式 \(\Theta(n^d)\)、多项式 < 指数（\(n^b = o(a^n)\) 对 \(a > 1\)）、对数 < 任何正多项式（\(\lg^b n = o(n^a)\)）、阶乘 \(\lg(n!) = \Theta(n \lg n)\)（Stirling 近似）。
渐近记号的代数性质：传递性、自反性、对称性、置换对称性；但三岐性不成立——存在「不可比较」的函数对（如 \(n\) 与 \(n^{1+\sin n}\)）。

本章主旨

本章为第 2 章的非形式化「增长量级」给出形式化记号：Θ（紧界）、O（上界）、Ω（下界）、o/ω（非紧上下界）。同时复习一组在算法分析中反复出现的函数族（多项式、指数、对数、阶乘、迭代对数、斐波那契数）及其渐近关系。本章不涉及具体算法，但记号系统是后续所有复杂度分析的共同语言。

一、核心概念

本章围绕 5 个核心概念展开：先给出 Θ/O/Ω 三种紧界记号，再用 o/ω 刻画非紧界，最后复习一组标准函数及其渐近关系。

概念	定义 + 重要性	实现提示
Θ 记号 (Theta)	紧界：存在正常数 \(c_1, c_2, n_0\)，对所有 \(n \geq n_0\)，\(c_1 g(n) \leq f(n) \leq c_2 g(n)\)。	§3.1；插入排序最坏运行时间 = \(\Theta(n^2)\)。
O 记号 (Big-Oh) 与 Ω 记号 (Big-Omega)	O = 渐近上界；Ω = 渐近下界。定理 3.1：Θ = O ∩ Ω（两方向充要）。	§3.1；O 用于描述上界（最坏分析），Ω 用于描述下界（最优性）。
o 记号与 ω 记号	非紧界：o(g(n)) = 严格小于 g 的所有函数上界；ω = 严格大于 g 的所有函数下界。	§3.1；等价定义：\(f(n) = o(g(n)) \iff \lim_{n \to \infty} f(n)/g(n) = 0\)。
代数性质与三岐性	传递性、自反性、对称性、置换对称性；但三岐性失败——存在不可比较的函数对。	§3.1；不可比较例子：\(n\) vs \(n^{1+\sin n}\)。
标准函数族	多项式、指数、对数、阶乘、迭代对数、斐波那契数；常用渐近关系：多项式 < 指数、对数 < 任何正多项式、\(\lg(n!) = \Theta(n \lg n)\)。	§3.2；许多算法分析最后化简到这些函数的比较。

概念

定义 + 重要性

实现提示

Θ 记号 (Theta)

紧界：存在正常数 \(c_1, c_2, n_0\)，对所有 \(n \geq n_0\)，\(c_1 g(n) \leq f(n) \leq c_2 g(n)\)。

§3.1；插入排序最坏运行时间 = \(\Theta(n^2)\)。

O 记号 (Big-Oh) 与 Ω 记号 (Big-Omega)

O = 渐近上界；Ω = 渐近下界。定理 3.1：Θ = O ∩ Ω（两方向充要）。

§3.1；O 用于描述上界（最坏分析），Ω 用于描述下界（最优性）。

o 记号与 ω 记号

非紧界：o(g(n)) = 严格小于 g 的所有函数上界；ω = 严格大于 g 的所有函数下界。

§3.1；等价定义：\(f(n) = o(g(n)) \iff \lim_{n \to \infty} f(n)/g(n) = 0\)。

代数性质与三岐性

传递性、自反性、对称性、置换对称性；但三岐性失败——存在不可比较的函数对。

§3.1；不可比较例子：\(n\) vs \(n^{1+\sin n}\)。

标准函数族

多项式、指数、对数、阶乘、迭代对数、斐波那契数；常用渐近关系：多项式 < 指数、对数 < 任何正多项式、\(\lg(n!) = \Theta(n \lg n)\)。

§3.2；许多算法分析最后化简到这些函数的比较。

二、详细笔记

3.1 Θ 记号 (Theta-notation)

What：\(\Theta(g(n))\) 是满足下列条件的函数 \(f(n)\) 的集合：

\[\exists c_1, c_2 > 0, n_0 > 0 : 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n), \forall n \geq n_0\]

直觉：\(f(n)\) 被夹在 \(c_1 g(n)\) 与 \(c_2 g(n)\) 之间——\(g(n)\) 是 \(f(n)\) 的「渐近紧界 (asymptotically tight bound)」。

Why：插入排序的最坏运行时间是某个具体的多项式（如 \(\tfrac{1}{2}n^2 - 3n\)）；用 Θ 记号写成 \(\Theta(n^2)\) 后，常数与低阶项被忽略，只看主项，便于横向比较算法。

How：证明 \(\tfrac{1}{2} n^2 - 3n = \Theta(n^2)\)（§3.1）：需找 \(c_1, c_2, n_0\) 使

\[c_1 n^2 \leq \tfrac{1}{2} n^2 - 3n \leq c_2 n^2, \quad \forall n \geq n_0\]

两边除以 \(n^2\)：\(c_1 \leq \tfrac{1}{2} - \tfrac{3}{n} \leq c_2\)。

取 \(c_1 = 1/14\), \(c_2 = 1/2\), \(n_0 = 7\) → 成立。
验证「反向」：\(6n^3 \neq \Theta(n^2)\)——若存在 \(c_2, n_0\) 使 \(6n^3 \leq c_2 n^2\) 对所有 \(n \geq n_0\)，则 \(n \leq c_2/6\)，与 \(n\) 无界矛盾。

注意 Θ 要求 \(f(n)\) 渐近非负（即对足够大的 \(n\) 非负）。

When：需要刻画函数的精确增长量级时；当需要比较两个算法的渐近性能时；当需要证明算法是最优时（与 Ω 联立）。

Example：

任何二次函数 \(a n^2 + b n + c\)（\(a > 0\)）= \(\Theta(n^2)\)。
任何 d 次多项式 = \(\Theta(n^d)\)（问题 3-1）。
任何常数函数 = \(\Theta(1)\)（约定：\(n^0 = 1\)）。

3.2 O 记号 (Big-Oh) 与 Ω 记号 (Big-Omega)

What：

O 记号：渐近上界。\(O(g(n))\) = 满足下列条件的 \(f(n)\)：

\[\exists c > 0, n_0 > 0 : 0 \leq f(n) \leq c g(n), \forall n \geq n_0\]

Ω 记号：渐近下界。\(\Omega(g(n))\) = 满足下列条件的 \(f(n)\)：

\[\exists c > 0, n_0 > 0 : 0 \leq c g(n) \leq f(n), \forall n \geq n_0\]

Why：有时我们只能证明上界（如某算法的运行时间 \(O(n^2)\)），有时只能证明下界（如「任何比较排序至少需要 Ω(n lg n) 次比较」）；O 和 Ω 分别刻画这两种情形。

How：定理 3.1：对任意两个函数 \(f(n), g(n)\)，

\[f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \textbf{ and } f(n) = \Omega(g(n))\]

直觉：Θ 紧界等价于同时有 O 上界和 Ω 下界。

常见用法：

「插入排序的最坏运行时间是 \(O(n^2)\)」= 在最坏情况下，运行时间被某个常数乘的 \(n^2\) 控制——涵盖所有输入。
「插入排序的最坏运行时间是 Ω(n^2)」= 在最坏情况下，至少常数乘的 \(n^2\)——存在逆序输入达到此下界。
「插入排序的运行时间是 Ω(n)」= 对所有输入，至少线性时间——存在必须看的元素。

When：

用 O：当只需要上界（算法设计中的常见情形）；当想表达「最坏不超过」。
用 Ω：当证明算法最优（与上界联立得到 Θ）；当表达「至少」。
Θ：证明算法的运行时间紧界时。

Example：

二次函数 \(a n^2 + b n + c\) = Θ(n^2) ⇒ = O(n^2) = Ω(n^2)。
任意线性函数 \(a n + b\) = O(n^2)（取 \(c = a + |b|, n_0 = 1\)）——O 上界可以「松」。
插入排序的最坏运行时间 = Θ(n^2)，但运行时间（无修饰）= Ω(n) 且 = O(n^2)（因为存在已排序输入达到下界，也存在逆序输入达到上界）。

3.3 o 记号与 ω 记号（非紧界）

What：

o 记号：非紧上界。\(o(g(n))\) = 满足下列条件的 \(f(n)\)：

\[\forall c > 0, \exists n_0 > 0 : 0 \leq f(n) < c g(n), \forall n \geq n_0\]

ω 记号：非紧下界。类似地，

\[\forall c > 0, \exists n_0 > 0 : 0 \leq c g(n) < f(n), \forall n \geq n_0\]

Why：有时上界是「松」的（如 \(2n = o(n^2)\)），用 o 强调「远小于」。用极限判定更直观：

\[f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\]

\[f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\]

How：与 O/Θ 的区别

\(f(n) = O(g(n))\)：存在某个 \(c\) 使 \(f(n) \leq c g(n)\) 成立。
\(f(n) = o(g(n))\)：对任意 \(c\) 都成立（无论常数多小，\(f\) 最终都比 \(c g\) 小）。

类比实数：O ∼ ≤，o ∼ <；Θ ∼ =，Ω ∼ ≥，ω ∼ >。

When：表达「严格小于」「严格大于」的渐近关系；当一个增长量级严格小于另一个时（多项式 o 指数、对数 o 多项式）。

Example：

\(2n = o(n^2)\)，但 \(2n^2 \neq o(n^2)\)。
\(n^2/2 = \omega(n)\)，但 \(n^2/2 \neq \omega(n^2)\)。
任何正多项式 = ω(对数)；任何指数 = ω(多项式)。

3.4 渐近记号的性质

What：实数的比较性质（传递、自反、对称、三岐）在渐近记号上的类比——大多数成立，三岐不成立。

Why：这些性质让我们能像操作实数一样操作函数比较；了解三岐失败可以避免错误推理。

How：核心性质（§3.1）：

性质	表述
传递性 (Transitivity)	\(f = \Theta(g), g = \Theta(h) \Rightarrow f = \Theta(h)\)；O / Ω / o / ω 类似。
自反性 (Reflexivity)	\(f = \Theta(f)\)；\(f = O(f)\)；\(f = \Omega(f)\)。
对称性 (Symmetry)	\(f = \Theta(g) \iff g = \Theta(f)\)。
置换对称 (Transpose)	\(f = O(g) \iff g = \Omega(f)\)；\(f = o(g) \iff g = \omega(f)\)。
三岐性 (Trichotomy)	不成立——存在函数对无法用 O/Ω 比较。

性质

表述

传递性 (Transitivity)

\(f = \Theta(g), g = \Theta(h) \Rightarrow f = \Theta(h)\)；O / Ω / o / ω 类似。

自反性 (Reflexivity)

\(f = \Theta(f)\)；\(f = O(f)\)；\(f = \Omega(f)\)。

对称性 (Symmetry)

\(f = \Theta(g) \iff g = \Theta(f)\)。

置换对称 (Transpose)

\(f = O(g) \iff g = \Omega(f)\)；\(f = o(g) \iff g = \omega(f)\)。

三岐性 (Trichotomy)

不成立——存在函数对无法用 O/Ω 比较。

实数 vs 渐近类比（§3.1）：

\(f = O(g)\) ∼ \(a \leq b\)
\(f = \Omega(g)\) ∼ \(a \geq b\)
\(f = \Theta(g)\) ∼ \(a = b\)
\(f = o(g)\) ∼ \(a < b\)
\(f = \omega(g)\) ∼ \(a > b\)

When：推导渐近关系时；书写「链式」关系（如 \(2n^2 + 3n + 1 = 2n^2 + \Theta(n) = \Theta(n^2)\)）；判定「不能比较」的情形。

Example：

可比较：\(n^2 = \omega(n \lg n)\)，因为 \(\lim n^2/(n \lg n) = \infty\)。
不可比较：\(n\) 与 \(n^{1+\sin n}\)——指数在 [1, 2] 之间振荡，\(\lim\) 不存在。
链式化简：\(2n^2 + 3n + 1 = 2n^2 + \Theta(n) = \Theta(n^2)\)。

3.5 标准函数族 (Standard Functions)

What：一组在算法分析中反复出现的函数及其渐近关系——单调性、上下取整、模、多项式、指数、对数、阶乘、迭代对数、斐波那契数。

Why：算法运行时间经常化简到这些函数；知道它们的相对增长速率是分析的关键。

How：核心函数与关系（§3.2）：

单调性：\(f\) 单调递增当 \(m \leq n \Rightarrow f(m) \leq f(n)\)；严格类似。
上下取整：\(\lfloor x \rfloor\) = 最大 ≤ x 的整数，\(\lceil x \rceil\) = 最小 ≥ x 的整数；\(x - 1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1\)（式 3.3）。
模算术：\(a \bmod n\) = \(a - n \lfloor a/n \rfloor\)；\(0 \leq a \bmod n < n\)（式 3.8）。
多项式：\(p(n) = \sum_{i=0}^d a_i n^i\)；渐近正且 \(a_d > 0\) ⇒ \(p(n) = \Theta(n^d)\)。
指数：\(a > 1\) ⇒ \(n^b = o(a^n)\)（式 3.10）；任何指数函数严格快于任何多项式。
对数：本书默认 \(\lg = \log_2\)；换底只引入常数因子（式 3.15）；\(\lg^b n = o(n^a)\) 对任何 \(a > 0\)。
阶乘：Stirling 近似（式 3.18）：\(n! = \sqrt{2\pi n} (n/e)^n (1 + \Theta(1/n))\)；重要推论：\(\lg(n!) = \Theta(n \lg n)\)（式 3.19）。
迭代对数：\(\lg^* n\) = 使 \(\lg^{(i)} n \leq 1\) 的最小 \(i\)；增长极慢——对所有实际 \(n\)，\(\lg^* n \leq 5\)。
斐波那契数：\(F_i = F_{i-1} + F_{i-2}\)；\(F_i = \phi^i / \sqrt{5}\) 渐近（式 3.25），其中黄金比 \(\phi = (1+\sqrt 5)/2 \approx 1.618\)——指数增长。

When：每次化简算法的运行时间时，都依赖这些标准函数的关系；特别是：

多项式 vs 指数：决定算法在「足够大」时是否实用。
对数 vs 多项式：分治算法常见的「对数因子」优势（如 \(n \lg n\) vs \(n^2\)）。
阶乘 ↔ 指数：组合算法（如旅行商）的运行时间常常涉及 \(\Theta(n!)\) 或 \(\Theta(2^n)\)。
迭代对数：出现在并查集的复杂度分析（第 21 章）。

Example：

插入排序 vs 归并排序：\(\Theta(n^2)\) vs \(\Theta(n \lg n)\)——对数因子带来渐近优势。
FFT（第 30 章）：\(\Theta(n \lg n)\) 比朴素 DFT 的 \(\Theta(n^2)\) 快指数因子（这里是「对数因子」vs「多项式因子」）。
旅行商 (TSP)：暴力枚举 \(\Theta(n!)\)（Stirling ⇒ 指数级）；动态规划/分支定界 ≈ \(\Theta(2^n n^2)\)。

三、关键图表

核心公式对照表

式编号

内容

式 3.1

\(\lim_{n\to\infty} f(n)/g(n) = 0\)（o 记号的极限定义）

式 3.3

上下取整不等式：\(x-1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x+1\)

式 3.8

模定义：\(a \bmod n = a - n \lfloor a/n \rfloor\)

式 3.10

\(\lim_{n\to\infty} n^b / a^n = 0\)（\(a > 1\)）→ 多项式 o 指数

式 3.11

\(e^x = \sum_{i=0}^{\infty} x^i/i!\)

式 3.15

换底公式：\(\log_b a = \log_c a / \log_c b\)

式 3.18

Stirling 近似：\(n! = \sqrt{2\pi n} (n/e)^n (1 + \Theta(1/n))\)

式 3.19

\(\lg(n!) = \Theta(n \lg n)\)；\(n! = \omega(2^n)\)；\(n! = o(n^n)\)

式 3.22

斐波那契定义：\(F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2}\)

式 3.25

斐波那契闭式：\(F_i = \text{round}(\phi^i / \sqrt 5)\)

定理 3.1

\(f = \Theta(g) \iff f = O(g) \textbf{ and } f = \Omega(g)\)

四、思维导图

mindmap
  root((第 3 章 函数的增长))
    Θ记号
      渐近紧界
      夹逼常数
      Θ(1)表示常数
    O记号
      渐近上界
      最坏分析
      任意输入
    Ω记号
      渐近下界
      最优性证明
      存在输入
    o与ω
      非紧上下界
      极限定义
      严格大小
    代数性质
      传递
      自反
      对称
      三岐失败
    标准函数
      多项式
      指数
      对数
      阶乘
      迭代对数
      斐波那契
    渐近关系
      多项式小指数
      对数小多项式
      lg(n!)≈n lg n

五、重点与易错点

Θ 不是「等于」而是「集合成员」：\(f(n) = \Theta(g(n))\) 实际意思是 \(f(n) \in \Theta(g(n))\)；集合符号被「滥用」为等号。
O 记号既可能紧也可能松：说「插入排序运行时间是 \(O(n^2)\)」是对的，但没体现紧界（实际是 Θ(n^2)）。论文中常见「O-滥用」——区分 O 与 Θ 是良好算法论文的标志。
「\(O(n^2)\)」含义的双重性：技术上指「最坏情况运行时间 ≤ cn^2」；口语上也用来「对所有输入运行时间 ≤ cn^2」——这两种说法等价，因为「最坏情况」就是上界。
三岐性失败：\(n\) 与 \(n^{1+\sin n}\) 不可比较；不要假设任何两个函数都能用 O/Ω 比较。
o vs O：\(2n^2 = O(n^2)\)（紧）但 \(2n^2 \neq o(n^2)\)；\(2n = o(n^2)\)（松）。
对数换底只改常数：\(\log_2 n\) 与 \(\ln n\) 与 \(\log_{10} n\) 互相 Θ 关系；本书统一用 \(\lg\) = \(\log_2\)。
「对数只作用于下一项」：\(\lg n + k\) 意思是 \((\lg n) + k\)，不是 \(\lg(n+k)\)。
阶乘 \(\lg(n!) = \Theta(n \lg n)\)：来自 Stirling 近似；用在「比较排序的下界」证明中（第 8 章）。
迭代对数增长极慢：\(\lg^* n \leq 5\) 对宇宙中所有原子数（\(\sim 10^{80}\)）；不要把它和 \(\lg \lg n\) 混。
斐波那契闭式（式 3.25）：\(F_i\) 指数增长，底数是黄金比 \(\phi\)；出现在某些算法的复杂度中（如朴素递归斐波那契 = \(\Theta(\phi^n)\)，但用动态规划可降到 Θ(n)）。
不要混淆「输入规模」的不同测度：排序用元素数 \(n\)；整数运算用位数；图用顶点数 + 边数——渐近分析必须在同一测度下比较。
代数化简：\(T(n) = 2n^2 + 3n \lg n + 5n + 7 \lg n + 100\) = \(\Theta(n^2)\)，因为 \(n^2\) 主导。逐项化简 → \(\Theta(n^2) + \Theta(n \lg n) + \Theta(n) + \Theta(\lg n) + \Theta(1)\) = \(\Theta(n^2)\)。
链式渐近等式：\(2n^2 + 3n + 1 = 2n^2 + \Theta(n) = \Theta(n^2)\)——左到右因为主导项吸收，右到左是 Θ 的对称性。
「Θ(1)」是滥用：没有指明变量；通常意思是「相对某个变量是常数」（如 \(n\) 的函数 \(T(n) = \Theta(1)\) 表示常数时间）。
本章记号的应用范围：全书所有运行时间分析（递归式解、最坏情况、最优性证明）都依赖本章记号；务必熟练掌握。

第 3 章 函数的增长 (Growth of Functions)

核心结论

一、核心概念

二、详细笔记

3.1 Θ 记号 (Theta-notation)

3.2 O 记号 (Big-Oh) 与 Ω 记号 (Big-Omega)

3.3 o 记号与 ω 记号（非紧界）

3.4 渐近记号的性质

3.5 标准函数族 (Standard Functions)

三、关键图表

四、思维导图

五、重点与易错点

第 3 章函数的增长 (Growth of Functions)