1.1 - 算法分析的数学基础 | QuetzalSidera 的个人博客

一篇围绕算法分析的数学基础与渐进复杂度展开的学习笔记。

算法分析需要两套前置知识：用于推导求和、比较增长率的数学工具，以及用于量化资源消耗的渐进记号体系。本篇先整理前者（指数、对数、级数、模运算、证明方法），再展开后者（ $O$ 、 $\Omega$ 、 $\Theta$ 、 $o$ 的定义、运算法则与运行时间计算方法）。

1. 数学基础

1.1 指数

X^A X^B = X^{A+B}

\frac{X^A}{X^B} = X^{A-B}

(X^A)^B = X^{AB}

X^N + X^N = 2X^N \neq X^{2N}

2^N + 2^N = 2^{N+1}

1.2 对数

在计算机科学中，若无特别声明，所有对数均以 2 为底。

定义： $X^A = B$ 当且仅当 $\log_X B = A$ 。

定理 1.1（换底公式）：对任意 $C > 0$ ，

\log_A B = \frac{\log_C B}{\log_C A}

定理 1.2：

\log AB = \log A + \log B

常用等式：

公式	说明
$\log A/B = \log A - \log B$
$\log(A^B) = B \log A$
$\log X < X$	对所有 $X > 0$ 成立
$\log 1 = 0,\ \log 2 = 1$
$\log 1024 = 10,\ \log 1,048,576 = 20$

1.3 级数

几何级数：

\sum_{i=0}^{N} A^i = \frac{A^{N+1} - 1}{A - 1} \quad (A \neq 1)

当 $0 < A < 1$ 且 $N \to \infty$ 时， $\displaystyle \sum_{i=0}^{\infty} A^i = \frac{1}{1 - A}$ 。

常用算术级数：

\sum_{i=1}^{N} i = \frac{N(N+1)}{2} \approx \frac{N^2}{2}

\sum_{i=1}^{N} i^2 = \frac{N(N+1)(2N+1)}{6} \approx \frac{N^3}{3}

\sum_{i=1}^{N} i^k \approx \frac{N^{k+1}}{|k+1|} \quad (k \neq -1)

调和级数：

H_N = \sum_{i=1}^{N} \frac{1}{i} \approx \ln N + \gamma

其中 $\gamma \approx 0.57721566$ （欧拉常数）。 $H_N = \Theta(\log N)$ 。

级数运算常用恒等式：

\sum_{i=1}^{N} f(N) = N f(N)

\sum_{i=n_0}^{N} f(i) = \sum_{i=1}^{N} f(i) - \sum_{i=1}^{n_0-1} f(i)

1.4 模运算

若 $N$ 整除 $A - B$ ，则称 $A$ 与 $B$ 模 $N$ 同余，记为 $A \equiv B \pmod{N}$ 。直观上即 $A$ 和 $B$ 除以 $N$ 的余数相同。

性质	示例
若 $A \equiv B \pmod{N}$ ，则 $A+C \equiv B+C \pmod{N}$	$81 \equiv 61 \equiv 1 \pmod{10}$
若 $A \equiv B \pmod{N}$ ，则 $AD \equiv BD \pmod{N}$

1.5 证明方法

算法分析中最常使用的三种证明方法：

方法	思路	结构
归纳法	证明最小情形（基准）成立，再假设 $k$ 成立来证 $k+1$ 成立	基准情形 → 归纳假设 → 归纳步骤
反证法	假设结论为假，推导出矛盾	假设 ¬P → 推导 → 矛盾 → 故 P 成立
反例法	举出一个不满足结论的具体实例	直接给出反例即可推翻命题

归纳法示例——证明斐波那契数 $F_i = F_{i-1} + F_{i-2}$ （ $F_0 = 1, F_1 = 1$ ）满足 $F_i < (5/3)^i$ ：

基准： $F_1 = 1 < 5/3$ ， $F_2 = 2 < 25/9$
归纳：假设对 $i = 1,2,\ldots,k$ 成立，则

F_{k+1} = F_k + F_{k-1} < (5/3)^k + (5/3)^{k-1} = (5/3)^{k-1} \cdot (5/3 + 1) < (5/3)^{k-1} \cdot (5/3)^2 = (5/3)^{k+1}

2. 复杂度分析

2.1 渐进记号

评估算法资源消耗时，比较的是函数的相对增长率（relative rate of growth），而非具体数值。渐进记号体系提供了一套正式框架。

定义：设 $T(N)$ 和 $f(N)$ 为定义在正整数上的函数。

记号	读法	定义	含义
$T(N) = O(f(N))$	大 O	存在 $c > 0$ 和 $n_0$ ，使得 $N \ge n_0$ 时 $T(N) \le c f(N)$	$T(N)$ 增长率 ≤ $f(N)$ （上界）
$T(N) = \Omega(g(N))$	Omega	存在 $c > 0$ 和 $n_0$ ，使得 $N \ge n_0$ 时 $T(N) \ge c g(N)$	$T(N)$ 增长率 ≥ $g(N)$ （下界）
$T(N) = \Theta(h(N))$	Theta	$T(N) = O(h(N))$ 且 $T(N) = \Omega(h(N))$	$T(N)$ 增长率 = $h(N)$ （紧界）
$T(N) = o(p(N))$	小 o	$\displaystyle \lim_{N \to \infty} \frac{T(N)}{p(N)} = 0$	$T(N)$ 增长率 < $p(N)$ （严格上界）

注意： $f(N) \le O(g(N))$ 是错误的写法——不等式已隐含在 $O$ 的定义中。同时，不要在 $O$ 中保留常数和低阶项： $O(2N^2)$ 和 $O(N^2+N)$ 都应写为 $O(N^2)$

2.2 增长率比较

极限比较法：对于两个函数 $f(N)$ 和 $g(N)$ ，计算 $\displaystyle \lim_{N \to \infty} \frac{f(N)}{g(N)}$ ：

极限值	结论
$0$	$f(N) = o(g(N))$
有限非零常数 $c$	$f(N) = \Theta(g(N))$
$\infty$	$g(N) = o(f(N))$

查表法：

函数	名称	典型场景
$c$	常数	简单语句
$\log N$	对数	二分查找
$\log^2 N$	对数的平方
$\sqrt{N}$	平方根
$N$	线性	顺序扫描
$N \log N$	线性对数	归并排序、堆排序
$N^2$	平方	冒泡排序、选择排序
$N^3$	立方	矩阵乘法（朴素）
$2^N$	指数	穷举搜索

增长率由慢到快：

c < \log N < \log^2 N < \sqrt{N} < N < N \log N < N^2 < N^3 < 2^N

值得注意的是： $\log N$ 增长极其缓慢—— $\log^k N = O(N)$ 对任意常数 $k$ 成立。

2.3 运算法则

法则 1：若 $T_1(N) = O(f(N))$ 且 $T_2(N) = O(g(N))$ ，则

\begin{aligned}T_1(N) + T_2(N) &= \max\bigl(O(f(N)),\, O(g(N))\bigr) \\T_1(N) \cdot T_2(N) &= O\bigl(f(N) \cdot g(N)\bigr)\end{aligned}

法则 2：若 $T(N)$ 是 $k$ 次多项式，则 $T(N) = \Theta(N^k)$ 。

法则 3：对任意常数 $k$ ， $\log^k N = O(N)$ 。

推论——复杂度分析中的简化原则：

原则	说明
忽略常数因子	$O(1000N) = O(N)$
忽略低阶项	$O(N^2 + N) = O(N^2)$
加法取最大	循环并列时复杂度取各段最大者
乘法取乘积	嵌套循环时复杂度取各层乘积

2.4 运行时间计算

分析运行时间的基本方法：逐语句累加运行时间，忽略常数，关注最内层循环的迭代次数。

a. 单层循环

int sum(int n) {    int total = 0;               // O(1)    for (int i = 0; i < n; i++) // n 次迭代        total += i;              // O(1) 每轮    return total;                // O(1)}

总时间： $O(1) + n \cdot O(1) + O(1) = O(N)$ 。

b. 嵌套循环

for (int i = 0; i < n; i++)         // n 次    for (int j = 0; j < n; j++)     // n 次/每轮        count++;                     // O(1)

总时间： $n \cdot n \cdot O(1) = O(N^2)$ 。

c. 依赖外层的循环

for (int i = 0; i < n; i++)         // n 次    for (int j = 0; j < i; j++)     // i 次/每轮        count++;

\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2} = O(N^2)

d. 对数时间

while (n > 1) {    n /= 2;          // 每轮将 n 减半    /* O(1) 操作 */}

循环次数为 $\lceil \log_2 n \rceil$ ，总时间 $O(\log N)$ 。

e. 递归函数

递归函数的时间复杂度通过递推关系式描述，判断复杂度的关键在于确定

递归层数 $N_{r}$
第 $i$ 层子任务数 $n_{i}$ $(n_{1} = 1), i \in [1,N_{r}]$
每层每个子任务的规模 $T_{i}$ (往往并非常数，与层级有关)

则总复杂度可以表示如下：

T(N) = \sum_{i=1}^{N_{r}} (n_{i} \cdot T_{i})

也就是将每层的总规模计算后，逐层累加。

情形 1： $T(N) = T(N-1) + O(1)$

递归深度为 $N$ ，每层一个子问题，每个子问题规模为 $O(1)$ ，因此

T(N) = N \cdot O(1)=O(N)

情形 2： $T(N) = 2T(N-1) + O(1)$

每个问题分为两个子问题，第 $i$ 层有 $2^i$ 个子问题，每个子问题规模为 $O(1)$ ，该层总工作量为 $2^i \cdot O(1)$ ，共 $N$ 层，因此累加可得

\sum_{i=1}^{N} 2^i \cdot O(1) = O(2^N)

情形 3： $T(N) = T(N/2) + O(1)$

递归深度为 $\log N$ ，每层一个子问题，每个子问题规模为 $O(1)$ ，因此

T(N) = \log N \cdot O(1)=O(\log N)

情形 4： $T(N) = 2T(N/2) + O(N)$

递归深度为 $\log N$ ，第 $i$ 层有 $2^i$ 个子问题，每个子问题规模为 $O(N/2^i)$ ，该层总工作量为 $2^i \cdot O(N/2^i) = O(N)$ ，因此

T(N) = \log N \cdot O(N)=O(N \log N)

递推式	含义	复杂度	典型算法
$T(N) = T(N-1) + O(1)$	逐次减一 + 常数时间	$O(N)$	线性递归（如阶乘）
$T(N) = 2T(N-1) + O(1)$	指数分支 + 常数时间	$O(2^N)$	斐波那契朴素递归
$T(N) = T(N/2) + O(1)$	减半 + 常数时间	$O(\log N)$	二分查找
$T(N) = 2T(N/2) + O(N)$	两分 + 线性时间合并	$O(N \log N)$	归并排序

小结

主题	核心内容
数学基础	指数恒等式、对数换底公式、几何/算术/调和级数、模运算同余性质、归纳法与反证法
渐进记号	$O$ （上界）、 $\Omega$ （下界）、 $\Theta$ （紧界）、 $o$ （严格上界）；用极限比较增长率的快慢
运算法则	加法取最大、乘法取乘积、忽略常数和低阶项、多项式取最高次
运行时间计算	逐句累加 → 关注最内层循环 → 查级数公式求和 → 递归问题检查每层工作量与分支数