第03章 运行时间刻画 — 章节汇总

章节概览

第3章”运行时间刻画”是《算法导论》中算法分析数学基础的系统化阐述，由三节组成。3.1 O 记号、$\Omega$ 记号与 $\Theta$ 记号从直觉层面引入三种核心渐近记号，以插入排序为案例展示上界、下界和紧界的推导方法；3.2 渐近记号的形式化定义给出五种渐近记号（$O$、$\Omega$、$\Theta$、$o$、$\omega$）的严格集合论定义，并系统阐述其数学性质（传递性、自反性、对称性、转置对称性）与运算规则；3.3 标准记号与常见函数回顾算法分析中常用的数学函数（取整、多项式、指数、对数、阶乘、Fibonacci 数、调和级数、迭代对数），建立函数增长率的层次关系。全章为后续章节的算法复杂度分析提供了完整的数学语言和工具集。

---

3.1 O 记号、$\Omega$ 记号与 $\Theta$ 记号 — 要点汇总

三种核心渐近记号

记号	含义	直觉	示例
$O(g(n))$	渐近上界	”不超过” $g(n)$ 的速率	$7n^3+100n^2=O(n^3)$
$\Omega (g(n))$	渐近下界	”至少有” $g(n)$ 的速率	$7n^3+100n^2=\Omega (n^3)$
$\Theta (g(n))$	渐近紧界	”恰好是” $g(n)$ 的速率	$7n^3+100n^2=\Theta (n^3)$

核心结论

• $\Theta$ 记号等价于同时满足 $O$ 和 $\Omega$：$f(n)=\Theta (g(n))$ 当且仅当 $f(n)=O(g(n))$ 且 $f(n)=\Omega (g(n))$
• 渐近记号忽略低阶项和常数系数，专注于输入规模趋于无穷时的本质行为
• 插入排序的最坏情况运行时间为 $\Theta (n^2)$：通过嵌套循环结构推导 $O(n^2)$ 上界，通过构造特定输入推导 $\Omega (n^2)$ 下界

增长率层次

$\Theta (1)<\Theta (\lg n)<\Theta (\sqrt{n})<\Theta (n)<\Theta (n\lg n)<\Theta (n^2)<\Theta (n^3)<\Theta (2^n)<\Theta (n!)$

---

3.2 渐近记号的形式化定义 — 要点汇总

五种渐近记号的形式化定义

记号	定义	与实数运算的类比
$O(g(n))$	$\exists c>0,n_0>0,\forall n\ge n_0:0\le f(n)\le cg(n)$	$\le$（小于等于）
$\Omega (g(n))$	$\exists c>0,n_0>0,\forall n\ge n_0:0\le cg(n)\le f(n)$	$\ge$（大于等于）
$\Theta (g(n))$	$\exists c_1,c_2>0,n_0>0,\forall n\ge n_0:0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$	$=$（等于）
$o(g(n))$	$\forall c>0,\exists n_0>0,\forall n\ge n_0:0\le f(n)<cg(n)$	$<$（严格小于）
$\omega (g(n))$	$\forall c>0,\exists n_0>0,\forall n\ge n_0:0\le cg(n)<f(n)$	$>$（严格大于）

数学性质

• 传递性：$O$、$\Omega$、$\Theta$、$o$、$\omega$ 均满足传递性
• 自反性：$O$、$\Omega$、$\Theta$ 满足自反性；$o$、$\omega$ 不满足
• 对称性：仅 $\Theta$ 满足对称性（$f=\Theta (g)\iff g=\Theta (f)$）
• 转置对称性：$f=O(g)\iff g=\Omega (f)$；$f=o(g)\iff g=\omega (f)$
• 三歧性不成立：并非所有函数对都能进行渐近比较（如 $f(n)=n\sin n$ 与 $g(n)=1$）

定理 3.1

$f(n)=\Theta (g(n))⟺f(n)=O(g(n))\text{ 且 }f(n)=\Omega (g(n))$

---

3.3 标准记号与常见函数 — 要点汇总

函数增长率层次

$\Theta (1)<\Theta ({\lg }^{\ast }n)<\Theta (\lg n)<\Theta ({\lg }^{k}n)<\Theta (n^a)<\Theta (n^b)<\Theta (a^n)<\Theta (n!)<\Theta (n^n)$

（其中 $a<b$，$0<a<1$，$k$ 为常数）

核心结论

主题	核心结论
取整函数	$\lfloor x\rfloor$ 和 $\lceil x\rceil$ 单调递增；$\lceil x/a\rceil /b\rceil =\lceil x/(ab)\rceil$
多项式	渐近正多项式 $p(n)=\Theta (n^d)$，$d$ 为次数
指数 vs 多项式	$n^b=o(a^n)$（$a>1$），指数严格快于多项式
Stirling 近似	$n!=\Theta (\sqrt{n}(n/e{)}^n)$，$\lg (n!)=\Theta (n\lg n)$
Fibonacci 数	$F_i=\frac{{\varphi }^i-{\hat{\varphi }}^i}{\sqrt{5}}=\Theta ({\varphi }^i)$，$\varphi =\frac{1+\sqrt{5}}{2}$
调和级数	$H_n={\sum }_{k=1}^{n}1/k=\ln n+O(1)=\Theta (\lg n)$
迭代对数	${\lg }^{\ast }n$ 增长极慢，实际中 ${\lg }^{\ast }n\le 5$
对数	换底仅改变常数因子；$(\lg n{)}^b=o(n^a)$（$a>0$）

---

跨章关联

关联章节	关联内容	关联说明
第2章	$\Theta$ 记号的非形式化引入	2.2 节非形式化引入 $\Theta$ 记号，第3章给出严格数学定义
第4章	渐近记号在递归关系式求解中的应用	主定理、代入法、递归树法均依赖渐近记号来描述递归解的增长率

---

笔记索引

节	笔记	核心主题
3.1	3.1 O记号、Ω记号与Θ记号	渐近上界/下界/紧界的直觉理解、插入排序案例分析
3.2	3.2 渐近记号的形式化定义	五种渐近记号的集合论定义、数学性质、运算规则
3.3	3.3 标准记号与常见函数	Stirling 近似、Fibonacci 数、调和级数、迭代对数、取整函数

第03章_运行时间刻画