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

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

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

1. 数学基础

1.1 指数

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

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

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

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

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 A B = \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} (A \neq 1)

当 $0 < A < 1$ 且 $N \to \infty$ 时， $\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) (2 N + 1)}{6} \approx \frac{N^{3}}{3}

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

调和级数：

H_{N} = \sum_{i = 1}^{N} \frac{1}{i} \approx \ln N + γ

其中 $γ \approx 0.57721566$ （欧拉常数）。 $H_{N} = Θ (\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 (\mod N)$ 。直观上即 $A$ 和 $B$ 除以 $N$ 的余数相同。

性质	示例
若 $A \equiv B (\mod N)$ ，则 $A + C \equiv B + C (\mod N)$	$81 \equiv 61 \equiv 1 (\mod 10)$
若 $A \equiv B (\mod N)$ ，则 $A D \equiv B D (\mod 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, \dots, 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 \geq n_{0}$ 时 $T (N) \leq c f (N)$	$T (N)$ 增长率 ≤ $f (N)$ （上界）
$T (N) = Ω (g (N))$	Omega	存在 $c > 0$ 和 $n_{0}$ ，使得 $N \geq n_{0}$ 时 $T (N) \geq c g (N)$	$T (N)$ 增长率 ≥ $g (N)$ （下界）
$T (N) = Θ (h (N))$	Theta	$T (N) = O (h (N))$ 且 $T (N) = Ω (h (N))$	$T (N)$ 增长率 = $h (N)$ （紧界）
$T (N) = o (p (N))$	小 o	$lim_{N \to \infty} \frac{T (N)}{p (N)} = 0$	$T (N)$ 增长率 < $p (N)$ （严格上界）

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

2.2 增长率比较

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

极限值	结论
$0$	$f (N) = o (g (N))$
有限非零常数 $c$	$f (N) = Θ (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 (O (f (N)), O (g (N))) \\ T_{1} (N) \cdot T_{2} (N) & = O (f (N) \cdot g (N)) \end{aligned}

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

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

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

原则	说明
忽略常数因子	$O (1000 N) = 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) 操作 */
}

循环次数为 $⌈ \log_{2} n ⌉$ ，总时间 $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) = 2 T (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) = 2 T (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) = 2 T (N - 1) + O (1)$	指数分支 + 常数时间	$O (2^{N})$	斐波那契朴素递归
$T (N) = T (N / 2) + O (1)$	减半 + 常数时间	$O (\log N)$	二分查找
$T (N) = 2 T (N / 2) + O (N)$	两分 + 线性时间合并	$O (N \log N)$	归并排序

小结

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

1.1 - 算法分析的数学基础

1. 数学基础 ​

1.1 指数 ​

1.2 对数 ​

1.3 级数 ​

1.4 模运算 ​

1.5 证明方法 ​

2. 复杂度分析 ​

2.1 渐进记号 ​

2.2 增长率比较 ​

2.3 运算法则 ​

2.4 运行时间计算 ​

a. 单层循环 ​

b. 嵌套循环 ​

c. 依赖外层的循环 ​

d. 对数时间 ​

e. 递归函数 ​

小结 ​