01 数学基础：渐进记号与递推式求解

本章对应考试中的：判断题第 1～11 条（渐进记号性质）、选择题第 10 题（大 O 定义）、简答 Q14（函数增长率排序，三个版本）、简答 Q15（证明 $1.5n^2+365n\log n=O(n^2)$）、递推式 T1～T5、填空题第 2、3 题（算法性质与评价标准）、作业题 O2（HeapPermute 复杂度）。

这一篇是整套体系的数学地基。后面每一道分治、减治大题最后都要"分析时间复杂度"，靠的就是本章的渐进记号和递推式。先把这篇吃透，后面会轻松很多。

---

核心考点

这一章其实只考四件事，全部都是"会套用就能拿分"的题：

1. 看懂三个记号 $O$、$\mathrm{\Omega }$、$\mathrm{\Theta }$，并判断一句话是对是错（判断题）。
2. 把一串函数按"增长快慢"排序（Q14）。
3. 写出"某函数 $=O(\text{某函数})$"的证明（Q15），就是找两个常数。
4. 解递推式（T1～T5），即给定一个"自己表示自己"的式子，求出它等于多少、是什么复杂度。

这四件事都有固定套路，下面逐一拆解。

---

从零开始的前置知识

什么是"增长率"和"阶"

增长率（growth rate）：当输入规模 $n$ 变大时，一个函数的值变大的"速度"。阶（order）：对增长率的分档，比如"线性阶""平方阶""指数阶"。

举一个具体的对比。下面是三个函数在 $n$ 取不同值时的数值：

$n$	$n$（线性）	$n^2$（平方）	$2^n$（指数）
$5$	$5$	$25$	$32$
$10$	$10$	$100$	$1024$
$20$	$20$	$400$	$1048576$
$50$	$50$	$2500$	约 $1.1\times {10}^{15}$

可以看到：$n$ 变大时，$2^n$ 涨得最猛，$n^2$ 其次，$n$ 最慢。这就是"增长率不同"。算法分析只关心当 $n$ 很大时谁涨得快，因为那时差距才会拉开到决定算法能不能用。

为什么只看 $n$ 很大的时候、为什么忽略常数倍

两个关键约定，贯穿整章：

第一，只看 $n\to \mathrm{\infty }$（$n$ 趋向无穷大）时的表现。 比如 $f(n)=n^2$ 在 $n=2$ 时只有 $4$，比 $g(n)=100n$（此时是 $200$）小；但当 $n$ 超过 $100$ 以后，$n^2$ 就永远超过 $100n$ 了。我们说"$n^2$ 的阶高于 $100n$"，看的是最终趋势，不是小数值时谁大。

第二，忽略常数倍数和低阶项。 $3n^2$、$100n^2$、$n^2+5n+8$ 都算作"平方阶 $n^2$"。因为常数倍和低阶项在 $n$ 很大时不改变"档次"。例如 $n^2+5n+8$，当 $n=1000$ 时，$n^2=1000000$ 而 $5n+8=5008$，后者占比微乎其微。

渐进记号 $O$、$\mathrm{\Omega }$、$\mathrm{\Theta }$ 就是把这两个约定写成严格数学的工具。

---

核心理论与方法

一、三种渐进记号的定义与判断方法

1. 大 O 记号（上界，"不超过"）

定义：称 $f(n)=O(g(n))$，如果存在正常数 $c$ 和自然数 $n_0$，使得对所有 $n\ge n_0$，都有

$$0\le f(n)\le c\cdot g(n).$$

逐个符号解释：$f(n)$ 是我们要分析的函数；$g(n)$ 是用来"卡上界"的参照函数；$c$ 是一个固定的倍数；$n_0$ 是一个起点，意思是"从 $n_0$ 往后"。整句话的含义是：只要 $n$ 足够大，$f$ 就被 $g$ 的某个常数倍压在下面，所以 $g$ 是 $f$ 的上界，$f$ 的阶不高于 $g$。

这正是选择题第 10 题的原文定义：存在正常数 $C$ 和自然数 $N_0$，当 $N\ge N_0$ 时 $f(N)\le Cg(N)$，记作 $f(N)=O(g(N))$，即 $f(N)$ 的阶不高于（答案 A）$g(N)$ 的阶。

怎么判断 $f(n)=O(g(n))$ 是否成立——方法一：找常数法。 想办法找出一对 $c$ 和 $n_0$ 让不等式成立即可。

例：判断 $f(n)=3n+5$ 是不是 $O(n)$。因为当 $n\ge 1$ 时 $5\le 5n$，所以 $3n+5\le 3n+5n=8n$。取 $c=8$、$n_0=1$，对一切 $n\ge 1$ 有 $3n+5\le 8n$。所以 $3n+5=O(n)$，成立。

方法二：看比值极限法。 计算 ${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}}$：

• 极限为有限值（包括 $0$）$\Rightarrow$ $f(n)=O(g(n))$。
• 极限为 $0$ $\Rightarrow$ $f$ 比 $g$ 严格低阶。
• 极限为有限正数 $\Rightarrow$ $f$ 与 $g$ 同阶，即 $f=\mathrm{\Theta }(g)$。
• 极限为 $\mathrm{\infty }$ $\Rightarrow$ $f$ 比 $g$ 高阶，$f\ne O(g)$。

例：${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{3n+5}{n}=3}$，有限正数，所以 $3n+5=\mathrm{\Theta }(n)$（当然也就 $=O(n)$）。

2. 大 $\mathrm{\Omega }$ 记号（下界，"不低于"）

定义：称 $f(n)=\mathrm{\Omega }(g(n))$，如果存在正常数 $c$ 和自然数 $n_0$，使得对所有 $n\ge n_0$，

$$f(n)\ge c\cdot g(n)\ge 0.$$

含义：从某处往后，$f$ 总在 $g$ 的某个常数倍之上，所以 $g$ 是 $f$ 的下界，$f$ 的阶不低于 $g$。

例：$f(n)=3n+5\ge 3n$，取 $c=3$、$n_0=1$，所以 $3n+5=\mathrm{\Omega }(n)$。

3. 大 $\mathrm{\Theta }$ 记号（同阶，"差不多"）

定义：称 $f(n)=\mathrm{\Theta }(g(n))$，如果同时有 $f(n)=O(g(n))$ 和 $f(n)=\mathrm{\Omega }(g(n))$。等价地，存在正常数 $c_1,c_2$ 和 $n_0$，使得对所有 $n\ge n_0$，

$$c_1\cdot g(n)\le f(n)\le c_2\cdot g(n).$$

含义：$f$ 被 $g$ 上下夹住，两者同一个阶。例：$3n+5=\mathrm{\Theta }(n)$，因为它既 $=O(n)$ 又 $=\mathrm{\Omega }(n)$。

一句话记忆：$O$ 是"$\le$ 的阶"，$\mathrm{\Omega }$ 是"$\ge$ 的阶"，$\mathrm{\Theta }$ 是"$=$ 的阶"。

二、大 O 的运算性质（判断题就考这些）

下面每条性质都直接对应判断题，记住结论和"为什么"。

性质 1（自反性）：$f(n)=O(f(n))$。对。 取 $c=1$、$n_0=1$，显然 $f(n)\le 1\cdot f(n)$。（判断题 1）

性质 2（加法取较大阶）：$O(f(n))+O(g(n))=O(max\{f(n),g(n)\})$。对。 两个函数相加，总和的阶由较大的那个决定。例：$O(n^2)+O(n)=O(n^2)$。（判断题 2）

性质 2 的错误变体：$O(f(n))+O(g(n))=O(min\{f(n),g(n)\})$。错。 应该取 $max$ 不是 $min$。例如 $n^2+n$ 的阶是 $n^2$（大的），不可能是 $n$（小的）。（判断题 3）

性质 3（$\mathrm{\Omega }$ 的传递性）：若 $f(n)=\mathrm{\Omega }(g(n))$ 且 $g(n)=\mathrm{\Omega }(h(n))$，则 $f(n)=\mathrm{\Omega }(h(n))$。对。 "不低于"可以一环扣一环传下去：$f$ 不低于 $g$、$g$ 不低于 $h$，那 $f$ 自然不低于 $h$。（$O$、$\mathrm{\Theta }$ 同样具有传递性。）（判断题 4）

性质 4（$O$ 与 $\mathrm{\Omega }$ 对偶）：若 $f(n)=O(g(n))$，则 $g(n)=\mathrm{\Omega }(f(n))$。对。 "$f$ 的阶不高于 $g$"换个角度说就是"$g$ 的阶不低于 $f$"，这两句是同一件事。（判断题 5）

性质 4 的错误变体：若 $f(n)=\mathrm{\Omega }(g(n))$，则 $g(n)=\mathrm{\Omega }(f(n))$。错。 方向反了。由 $f=\mathrm{\Omega }(g)$（$f$ 不低于 $g$）应推出 $g=O(f)$（$g$ 不高于 $f$），而不是 $g=\mathrm{\Omega }(f)$。例：$f=n^2$、$g=n$，有 $n^2=\mathrm{\Omega }(n)$ 成立，但 $n=\mathrm{\Omega }(n^2)$ 不成立。（判断题 6）

性质 5（$max$ 与求和同阶）：对非负函数，$max(f(n),g(n))=\mathrm{\Theta }(f(n)+g(n))$。对。 因为 $max(f,g)\le f+g\le 2max(f,g)$，上下都被 $max(f,g)$ 的常数倍夹住。例：$max(n^2,n)=n^2$，而 $n^2+n$ 也是 $\mathrm{\Theta }(n^2)$，两者同阶。（判断题 7）

性质 6（指数的处理）：$2^{n+1}=O(2^n)$ 且 $2^n=O(2^{2n})$。对。

• $2^{n+1}=2\cdot 2^n\le 2\cdot 2^n$，取 $c=2$ 即可，所以 $2^{n+1}=O(2^n)$。关键点：指数上 $+1$ 只是乘了个常数 $2$，不改变阶。
• $2^n\le 2^{2n}$ 显然，所以 $2^n=O(2^{2n})$。（判断题 8）

性质 6 的错误变体：$2^{n+1}=O(2^n)$ 且 $2^{2n}=O(2^n)$。错。 前半句对，后半句错：$2^{2n}=(2^n{)}^2=4^n$，而 ${\displaystyle \frac{4^n}{2^n}}=2^n\to \mathrm{\infty }$，比值趋于无穷，所以 $2^{2n}\ne O(2^n)$。关键点：指数上 $\times 2$（从 $n$ 变 $2n$）会彻底改变阶。（判断题 9）

性质 7（算法复杂度是问题复杂度的上界）：若求解问题 $p$ 的某算法 A 的复杂度为 $f(n)$，则问题 $p$ 的复杂度 $C(p)\le f(n)$。对。 问题的复杂度指"解决这个问题最少需要多少操作"；只要你拿出一个复杂度为 $f(n)$ 的算法，就证明了这个问题"最多 $f(n)$ 就能解决"，即给了一个上界。（判断题 10）

性质 8（最坏情况比平均情况好算）：通常算法的最坏情况时间复杂度比平均情况时间复杂度容易计算。对。 最坏情况只需找"最糟的那个输入"；平均情况要对所有可能输入按概率分布求期望（加权平均），数学上更复杂。（判断题 11）

三、函数增长率的"标准梯子"与比较技巧

把常见函数按增长率从小到大排成一排，这就是排序题（Q14）的依据。记号 $\prec$ 读作"阶低于"（即左边是右边的 $O$，且严格更低）：

$$1\prec \log \log n\prec \log n\prec (\log n{)}^2\prec \sqrt{n}\prec n\prec n\log n\prec n^2\prec n^3\prec 2^n\prec 3^n\prec n!\prec n^n.$$

逐段说明这把梯子的"分界线"，这是排序的核心规律：

• 常数 $\prec$ 对数 $\prec$ 多项式 $\prec$ 指数 $\prec$ 阶乘 $\prec$ $n^n$，这是五个大档次，跨档次直接判定。
• 任何对数的幂都低于任何正次幂的 $n$：$(\log n{)}^a\prec n^b$（只要 $b>0$）。例：$(\log n{)}^{100}\prec n^{0.01}$，虽然看着前者指数大，但 $n$ 的任意正次幂最终都赢。
• 任何 $n$ 的幂都低于任何底大于 $1$ 的指数：$n^a\prec c^n$（$c>1$）。例：$n^{1000}\prec {1.001}^n$。

当两个函数看不出谁大时，用下面两招：

技巧一：取对数比较。 如果 $\log f(n)\prec \log g(n)$，那么 $f(n)\prec g(n)$（对数不改变大小关系，却能把指数拉下来、便于比较）。

例：比较 $f=n^{1/3}$ 与 $h=2^{\sqrt{{\log }_{2}n}}$。令 $L={\log }_{2}n$。则 ${\log }_{2}f=\frac{1}{3}{\log }_{2}n=\frac{L}{3}$，${\log }_{2}h=\sqrt{L}$。当 $L\to \mathrm{\infty }$ 时 $\frac{L}{3}$ 远大于 $\sqrt{L}$（一次方碾压平方根），所以 ${\log }_{2}f\succ {\log }_{2}h$，即 $f\succ h$，也就是 $2^{\sqrt{{\log }_{2}n}}\prec n^{1/3}$。

技巧二：看比值极限。 算 $\underset{n\to \mathrm{\infty }}{lim}f(n)/g(n)$，极限为 $0$ 说明 $f\prec g$，为 $\mathrm{\infty }$ 说明 $f\succ g$，为有限正数说明同阶。

四、解递推式的三种方法

递推式（recurrence）：用"规模更小时的值"来表示"规模为 $n$ 时的值"的式子，加上一个边界条件（最小规模时的值）。每个递归/分治算法的复杂度都写成递推式。解递推式就是求出它的"非递归表达式"（直接关于 $n$ 的公式）和复杂度。

方法一：迭代展开法（最通用）

做法：把递推式右边的项一层层往里代入展开，写出前几步找出规律，一直展开到边界条件，再把所有项加起来。

例：解 $T(n)=2T(n-1)+n$，边界 $T(2)=2$（这就是 T1）。一层层代：

$$T(n)=2T(n-1)+n=2[2T(n-2)+(n-1)]+n=4T(n-2)+2(n-1)+n$$$$=8T(n-3)+4(n-2)+2(n-1)+n=\cdots$$

观察规律：系数是 $1,2,4,8,\dots$（即 $2^0,2^1,2^2,\dots$），展开到 $T(2)$ 时把这些项求和即可。求和后得到（完整结果见下面 T1 的精解）

$$T(n)=\frac{3}{2}\cdot 2^n-(n+2)=\mathrm{\Theta }(2^n).$$

方法二：主定理（Master Theorem，最快）

适用形式：$T(n)=aT(n/b)+f(n)$，其中 $a\ge 1$、$b>1$ 是常数，$f(n)$ 是合并/额外工作量。逐符号解释：$a$ 是子问题个数，$b$ 是每个子问题规模缩小的倍数（规模从 $n$ 变成 $n/b$），$f(n)$ 是把子问题解合并起来的代价。

判别步骤（三步走）：

1. 算出"分水岭"指数 $p={\log }_{b}a$，得到参照函数 $n^p=n^{{\log }_{b}a}$。
2. 把 $f(n)$ 和 $n^p$ 比大小。
3. 按下表对号入座：

情况	条件（$f(n)$ 与 $n^{{\log }_{b}a}$ 比）	结论
情况 1	$f(n)$ 阶低于 $n^{{\log }_{b}a}$	$T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$
情况 2	$f(n)$ 与 $n^{{\log }_{b}a}$ 同阶	$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$
情况 3	$f(n)$ 阶高于 $n^{{\log }_{b}a}$	$T(n)=\mathrm{\Theta }(f(n))$

怎么记：谁的阶大就听谁的；如果一样大，结果再多乘一个 $\log n$。

代入数字的例子：

• $T(n)=2T(n/2)+n$（归并排序）：$a=2,b=2$，$p={\log }_{2}2=1$，$n^1=n$，恰好与 $f(n)=n$ 同阶，属情况 2，$T(n)=\mathrm{\Theta }(n\log n)$。
• $T(n)=4T(n/2)+2n$：$a=4,b=2$，$p={\log }_{2}4=2$，$n^2$ 高于 $f(n)=2n$，属情况 1，$T(n)=\mathrm{\Theta }(n^2)$。
• $T(n)=2T(n/3)+2n$：$a=2,b=3$，$p={\log }_{3}2\approx 0.63$，$n^{0.63}$ 低于 $f(n)=2n$，属情况 3，$T(n)=\mathrm{\Theta }(n)$。
• $T(n)=T(n/2)+O(1)$（二分查找）：$a=1,b=2$，$p={\log }_{2}1=0$，$n^0=1$ 与 $f(n)=O(1)$ 同阶，属情况 2，$T(n)=\mathrm{\Theta }(\log n)$。

方法三：课件"定理 1"（给精确公式，HW1 用）

定理 1（题库 T5 给出的原文）：设 $a,c$ 为非负整数，$b,d,x$ 为非负常数，对某个非负整数 $k$ 令 $n=c^k$，则递推式

$$f(n)=d(n=1),f(n)=af(n/c)+b{n}^x(n\ge 2)$$

的解是：

$$f(n)=b{n}^x{\log }_{c}n+d{n}^x(\text{若 }a=c^x);$$$$f(n)=(d+\frac{b{c}^x}{a-c^x})n^{{\log }_{c}a}-(\frac{b{c}^x}{a-c^x})n^x(\text{若 }a\ne c^x).$$

怎么套用：把你的递推式和标准形 $f(n)=af(n/c)+b{n}^x$ 一一对照，读出五个数 $a,b,c,d,x$（其中 $d$ 是边界 $f(1)$ 的值，$x$ 是 $f(n)$ 里那个多项式项 $n^x$ 的指数，$b$ 是它的系数）。然后看 $a$ 和 $c^x$ 是否相等，选对应的公式直接代入。

代入例子：$f(n)=2f(n/2)+n$，$f(1)=0$。对照得 $a=2,c=2,x=1,b=1,d=0$。判断 $a=c^x$？$c^x=2^1=2=a$，相等，用第一式：$f(n)=1\cdot n^1\cdot {\log }_{2}n+0\cdot n^1=n{\log }_{2}n$。

三种方法怎么选：考场首选主定理（最快，且大多数大题的递推式都是 $aT(n/b)+f(n)$ 形）；递推式是"减一"型（如 $T(n-1)$）主定理不适用，用迭代展开；题目明确要求"由定理 1 导出"就用定理 1。

---

答题模板

模板一：函数增长率排序题

第1步：把每个函数归到"标准梯子"的某一档（常数/对数/多项式/指数/阶乘/n^n）。
第2步：同档的用"取对数"或"看比值极限"比较。
第3步：从阶最低到最高写出排序，并对每对相邻函数补一句"为什么前者低于后者"。
（题目要求：若 f 排在 g 后面，则 g = O(f)，即越靠后阶越高。）

模板二：渐进记号证明题（证 $f(n)=O(g(n))$）

目标：找一对常数 c>0 和 n0，使 n≥n0 时 f(n) ≤ c·g(n)。
第1步：把 f(n) 的每一项都放大成 g(n) 的倍数（小项用大项盖住）。
第2步：把这些倍数加起来得到 c。
第3步：写明"取 c=__, n0=__，对一切 n≥n0 有 f(n)≤c·g(n)，故 f(n)=O(g(n))"。∎

模板三：递推式求解题

第1步：判断形状。
  - 形如 a·T(n/b)+f(n) → 用主定理：算 p=log_b a，比 f(n) 与 n^p，套三种情况。
  - 题目要求"定理1" → 读出 a,b,c,d,x，判断 a 与 c^x，代入公式。
  - 形如 T(n-1)（减一型）→ 用迭代展开，找规律求和。
第2步：写出复杂度 Θ(...)；若要"非递归表达式"，给出精确闭式。
第3步：（如要求）代回边界条件验证一两个小值，确保没算错。

---

逐题精解

判断题 1～11（渐进记号性质）

下面把第 1～11 条的题面、答案、一句话理由汇总（详细理由见上面"运算性质"一节）：

题号	题面（简记）	答案	一句话理由
1	$f(n)=O(f(n))$	✓ 对	大 O 自反，取 $c=1$
2	$O(f)+O(g)=O(max\{f,g\})$	✓ 对	和的阶由大者定
3	$O(f)+O(g)=O(min\{f,g\})$	✗ 错	应取 $max$ 不是 $min$
4	$\mathrm{\Omega }$ 传递（$f=\mathrm{\Omega }(g),g=\mathrm{\Omega }(h)\Rightarrow f=\mathrm{\Omega }(h)$）	✓ 对	"不低于"可传递
5	$f=O(g)\Rightarrow g=\mathrm{\Omega }(f)$	✓ 对	$O$ 与 $\mathrm{\Omega }$ 对偶
6	$f=\mathrm{\Omega }(g)\Rightarrow g=\mathrm{\Omega }(f)$	✗ 错	应是 $g=O(f)$，方向反了
7	$max(f,g)=\mathrm{\Theta }(f+g)$	✓ 对	非负下两者同阶
8	$2^{n+1}=O(2^n)$ 且 $2^n=O(2^{2n})$	✓ 对	指数 $+1$ 只差常数倍
9	$2^{n+1}=O(2^n)$ 且 $2^{2n}=O(2^n)$	✗ 错	$2^{2n}=4^n$，比值 $\to \mathrm{\infty }$
10	算法复杂度 $f(n)\Rightarrow C(p)\le f(n)$	✓ 对	一个算法给出一个上界
11	最坏情况比平均情况易算	✓ 对	平均要对分布求期望

⚠️ 最爱挖的坑是第 3、6、9 条：把 $max$ 偷换成 $min$、把对偶方向写反、把指数 $\times 2$ 当成只差常数。看到这三种立刻警惕。

选择题第 10 题

已在上文"大 O 定义"处给出：答案 A（不高于）。$f(N)=O(g(N))$ 的含义就是 $f$ 的阶不高于 $g$。

简答 Q14：函数增长率排序（三个版本）

版本 A（来源 样题1 试卷1 试卷3）。原题函数：

$$f_1(n)={10}^n,f_2(n)=n^{1/3},f_3(n)=n^n,f_4(n)=2^{\sqrt{{\log }_{c}n}},f_5(n)={\log }_{2}n.$$

逐对判断（令 $L={\log }_{2}n$）：

• $f_5={\log }_{2}n=L$ 是对数档，最低。
• $f_4=2^{\sqrt{L}}$：与 $f_5$ 比，${\log }_2{f}_4=\sqrt{L}$ 远大于 ${\log }_2{f}_5={\log }_{2}L$，故 $f_4\succ f_5$；与 $f_2$ 比，${\log }_2{f}_2=\frac{L}{3}$ 远大于 $\sqrt{L}$，故 $f_4\prec f_2$。所以 $f_4$ 夹在 $f_5$ 和 $f_2$ 之间。
• $f_2=n^{1/3}$ 是多项式档，低于指数 $f_1={10}^n$。
• $f_1={10}^n$ 与 $f_3=n^n$：${\log }_2{f}_1=n{\log }_{2}10\approx 3.32n$，${\log }_2{f}_3=n{\log }_{2}n$，后者远大，故 $f_1\prec f_3$。

最终排序：

$$f_5\prec f_4\prec f_2\prec f_1\prec f_3,\text{即}{\log }_{2}n,2^{\sqrt{{\log }_{c}n}},n^{1/3},{10}^n,n^n.$$

版本 B（来源 2011期末 试卷4）。原题函数：

$$f_1=n^{3/4},f_2=2^n,f_3=\log n,f_4=n!,f_5=2^{n^2},f_6=n\log n.$$

逐对判断：$\log n$（对数）最低；$n^{3/4}$ 与 $n\log n$ 都是多项式档，但 $\frac{n\log n}{n^{3/4}}=n^{1/4}\log n\to \mathrm{\infty }$，故 $n^{3/4}\prec n\log n$；再往上是指数 $2^n$；阶乘 $n!$ 高于 $2^n$（因 $n!=1\cdot 2\cdots n$，当 $n\ge 4$ 起每个因子都 $\ge 2$ 且越来越大）；最高是 $2^{n^2}$，因 ${\log }_2(2^{n^2})=n^2$ 远大于 ${\log }_2(n!)\approx n{\log }_{2}n$。

最终排序：

$$f_3\prec f_1\prec f_6\prec f_2\prec f_4\prec f_5,\text{即}\log n,n^{3/4},n\log n,2^n,n!,2^{n^2}.$$

版本 C（来源 样题2 试卷2，原卷部分识别模糊）。原题大致为 $h_1=2^n,h_2=3n^{1/3},h_3=n^n,h_4=2^{{\ln }^{n}n}\text{(识别模糊)},h_5={\ln }^{1/5}n$。可确定的部分排序为

$$h_5\prec h_2\prec h_1\prec h_3.$$

其中 $h_5$（对数的 $1/5$ 次幂）最低，$h_2$（多项式 $n^{1/3}$）次之，$h_1=2^n$（指数）再次，$h_3=n^n$ 最高。$h_4$ 因原式识别模糊需核对原卷：若 $h_4$ 实为 $2^{n\ln n}$ 量级，则它介于 $h_1$ 与 $h_3$ 之间。考场遇到这种识别模糊的，按你看到的实际题面，用上面"取对数"的技巧现场判断即可。

简答 Q15：证明 $1.5n^2+365n\log n=O(n^2)$

完整书写（直接套模板二）：

当 $n\ge 1$ 时，$\log n\le n$，所以 $n\log n\le n\cdot n=n^2$。于是

$$1.5n^2+365n\log n\le 1.5n^2+365n^2=366.5n^2.$$

取 $c=366.5$、$n_0=1$，则对一切 $n\ge n_0$ 都有 $1.5n^2+365n\log n\le c{n}^2$，故 $1.5n^2+365n\log n=O(n^2)$。$◼$

易错点：很多人卡在"$n\log n$ 怎么放大"。记住关键一步 $n\log n\le n^2$（因为 $\log n\le n$），就能把它并进 $n^2$ 项。

递推式 T1～T5

T1（来源 样题2 试卷2）：$T(2)=2$；$T(n)=2T(n-1)+n(n>2)$。

这是"减一型"，用迭代展开 + 待定法。设通解 $T(n)=c\cdot 2^n+(\text{特解})$。特解对应 $+n$ 这一项，试 $an+b$ 代入可解得特解 $=-(n+2)$。于是 $T(n)=c\cdot 2^n-(n+2)$。代边界 $T(2)=2$：$4c-4=2\Rightarrow c=\frac{3}{2}$。所以

$$T(n)=\frac{3}{2}\cdot 2^n-(n+2)=\mathrm{\Theta }(2^n).$$

T2（来源 样题1 试卷1 试卷3）：$T(3)=2$；$T(n)=2T(n/3)+2(n>3)$。

设 $n=3^k$，记 $t_k=T(3^k)$，则 $t_k=2t_{k-1}+2$，$t_1=T(3)=2$。解这个一阶递推：通解 $t_k=c\cdot 2^k-2$（特解为常数 $-2$）。代 $t_1=2$：$2c-2=2\Rightarrow c=2$，所以 $t_k=2\cdot 2^k-2=2^{k+1}-2$。再换回 $n$：由 $n=3^k$ 得 $2^k=2^{{\log }_{3}n}=n^{{\log }_{3}2}$，故

$$T(n)=2n^{{\log }_{3}2}-2=\mathrm{\Theta }\left(n^{{\log }_{3}2}\right)\approx \mathrm{\Theta }(n^{0.63}).$$

T3（来源 2011期末）：$T(1)=2$；$T(n)=4T(n/2)+2n(n\ge 2)$。

主定理：$a=4,b=2$，$p={\log }_{2}4=2$，$n^2$ 高于 $f(n)=2n$，属情况 1，所以 $T(n)=\mathrm{\Theta }(n^2)$。

精确求解（设 $n=2^k$，$t_k=T(2^k)$，$t_0=2$）：$t_k=4t_{k-1}+2^{k+1}$。解得 $t_k=4\cdot 4^k-2^{k+1}$，换回 $n$（$4^k=n^2$，$2^k=n$）得

$$T(n)=4n^2-2n=\mathrm{\Theta }(n^2).$$

验证：$n=2$ 时 $4\cdot 4-4=12$，而 $T(2)=4T(1)+4=12$ ✓；$n=4$ 时 $4\cdot 16-8=56$，而 $T(4)=4T(2)+8=56$ ✓。

⚠️ 题库勘误：题库给的精确式写作 $T(n)=2n^2+2n$，但代入 $n=4$ 得 $40$，与真实值 $56$ 不符；正确闭式应为 $T(n)=4n^2-2n$。两者的渐进阶都是 $\mathrm{\Theta }(n^2)$，考试只要答 $\mathrm{\Theta }(n^2)$ 即得分，但若要写精确式请用 $4n^2-2n$。

T4（来源 试卷4）：$T(1)=2$；$T(n)=2T(n/3)+2n(n\ge 2)$。

主定理：$a=2,b=3$，$p={\log }_{3}2\approx 0.63$，$n^{0.63}$ 低于 $f(n)=2n$，属情况 3，所以 $T(n)=\mathrm{\Theta }(n)$。

精确求解（设 $n=3^k$，$t_0=2$）：$t_k=2t_{k-1}+2\cdot 3^k$，解得 $t_k=-4\cdot 2^k+6\cdot 3^k$，换回 $n$（$3^k=n$，$2^k=n^{{\log }_{3}2}$）得

$$T(n)=6n-4n^{{\log }_{3}2}=\mathrm{\Theta }(n).$$

验证：$n=3$ 时 $18-8=10$，而 $T(3)=2T(1)+6=10$ ✓。

T5（来源 HW1，要求用定理 1）：$C(1)=1$；$C(n)=2C(n/2)+n-1(n\ge 2)$。

套用定理 1：对照标准形 $f(n)=af(n/c)+b{n}^x$，读出 $a=2,c=2,x=1,b=1,d=C(1)=1$（这里把 $n-1$ 近似看作主项 $n$，即 $b{n}^x=n$）。判断 $a$ 与 $c^x$：$c^x=2^1=2=a$，相等，用第一式：

$$C(n)=b{n}^x{\log }_{c}n+d{n}^x=n{\log }_{2}n+n=O(n\log n).$$

⚠️ 关于精确常数：若严格解原递推（带上 $-1$），精确闭式是 $C(n)=n{\log }_{2}n+1$（验证：$n=4$ 时 $2\cdot 4+1=9=C(4)$ ✓）。题库写的 $(n-1){\log }_{2}n+n$ 在 $n=4$ 时得 $10$，与真实值 $9$ 略有出入。三者渐进复杂度都是 $O(n\log n)$，这是本题的得分点；题目要求"由定理 1 导出"，按定理 1 写 $n{\log }_{2}n+n=O(n\log n)$ 即可。

填空题第 2、3 题（算法的性质与评价标准）

第 2 题：算法是由若干条指令组成的有序序列，具有（　）、（　）、（　）和（　）的性质。 答案：输入、输出、确定性、有限性。（有些教材还会列"可行性/正确性"，按本课答案填这四个。）逐个解释：输入指有零个或多个外部数据；输出指至少产生一个结果；确定性指每一步的含义明确无歧义；有限性指执行有限步后一定结束。

第 3 题：评价算法的标准包括（　）、（　）以及正确性、简单性等。 答案：时间复杂性、空间复杂性。即"跑得快不快"和"占内存多不多"。

作业题 O2：HeapPermute 全排列算法的正确性与时间效率

原题算法（来源 HW1）：

HeapPermute(n)
//输入：正整数 n 和全局数组 A[1..n]；输出：A 的全排列
if n = 1
    write A
else
    for i ← 1 to n do
        HeapPermute(n-1)
        if n is odd:  swap A[1] and A[n]
        else:         swap A[i] and A[n]

正确性：用数学归纳法。可证明：当 $n$ 为偶数时，HeapPermute(n) 输出全部排列后，数组相当于循环移动了一位；当 $n$ 为奇数时，输出后数组顺序不变。由此，外层 for 的每一次循环都能把"前 $n-1$ 个元素中的某一个"换到第 $n$ 位，于是 $n$ 次循环正好让每个元素都当过一次"末位"，配合内层递归生成前 $n-1$ 位的全排列，最终输出 $A[1..n]$ 的全部 $n!$ 个排列，无重复无遗漏。

时间效率：设 $f(n)$ 为基本操作（write 与 swap）次数，递推为

$$f(n)=n\cdot f(n-1)+n.$$

含义：外层循环 $n$ 次，每次先递归调用 $f(n-1)$，再做 $1$ 次 swap（共 $n$ 次）。这个递推的解是 $\mathrm{\Theta }(n!)$ 量级——因为算法要输出全部 $n!$ 个排列，输出次数本身就是 $n!$，所以时间复杂度 $\mathrm{\Theta }(n!)$，与排列总数同阶，已是最优（再快也不可能，因为光"写出"所有排列就要 $n!$ 步）。

---

高频陷阱 / 易错点小结

1. 加法取 $max$ 不是 $min$（判断 3）。$n^2+n=O(n^2)$。
2. 对偶方向：$f=O(g)\iff g=\mathrm{\Omega }(f)$；由 $f=\mathrm{\Omega }(g)$ 得到的是 $g=O(f)$，别写成 $g=\mathrm{\Omega }(f)$（判断 6）。
3. 指数 $+$ 常数 vs $\times$ 常数：$2^{n+1}=O(2^n)$ 对（差常数倍）；$2^{2n}=O(2^n)$ 错（$=4^n$，比值趋于无穷）（判断 8、9）。
4. 排序题方向：题目要求"$f$ 排在 $g$ 后面则 $g=O(f)$"，即越往后阶越高，别写反。
5. 主定理三种情况别记混：阶大者胜；同阶时结果多乘一个 $\log n$。
6. 减一型递推（含 $T(n-1)$）不能用主定理，要用迭代展开。
7. 复杂度记号写规范：写 $O(n\log n)$ 而不是 "nlogn"，写 $\mathrm{\Theta }(n^2)$ 而不是 "n^2"。

---

自测清单

能不看答案做到下面几条，本章就过关：

• [ ] 默写 $O$、$\mathrm{\Omega }$、$\mathrm{\Theta }$ 三个记号的定义（各含 $c$ 和 $n_0$）。
• [ ] 说出判断题 1～11 每条的对错和一句话理由（尤其 3、6、9）。
• [ ] 把版本 A、B 的函数从小到大排出来，并说出每对的比较理由。
• [ ] 完整写出 $1.5n^2+365n\log n=O(n^2)$ 的证明（找出 $c=366.5,n_0=1$）。
• [ ] 用主定理秒答：$2T(n/2)+n$、$4T(n/2)+2n$、$2T(n/3)+2n$、$T(n/2)+1$ 各是什么阶。
• [ ] 写出 T1～T5 的求解过程和最终复杂度。
• [ ] 说出算法的四条性质和两条主要评价标准。