---
title: 算法设计与分析 - 基本概念与解递归方程
abbrlink: 55cab229
date: "2025-07-04 18:44:32"
updated: "2025-07-04 18:44:32"
desc: 💡 有趣的发现： ISBN编号相同却有两个不同封面的书，可能是出版商重印了。
categories:
    - 学校学习
tags:
    - 算法
    - 记录
    - 学习
cover: https://i.ibb.co/PdngTsR/image.webp
---

## 📚 参考书籍

> **计算机算法设计与分析(第5版)**  
> ISBN编号：9787121344398

![image](https://i.ibb.co/PdngTsR/image.webp)

**💡 有趣的发现：** ISBN编号相同却有两个不同封面的书，可能是出版商重印了。

---

## 🔍 一些基本概念

### 计算复杂度

- **上界(Upper Bound)**: 算法复杂度的上界用大O表示法表示，即 $O(f(n))$，表示算法的运行时间不会超过 $f(n)$ 的常数倍。

- **确界(Tight Bound)**: 算法复杂度的确界用Θ表示法表示，即 $Θ(f(n))$，表示算法的运行时间既有上界又有下界，都是 $f(n)$ 的常数倍。

- **下界(Lower Bound)**: 算法复杂度的下界用Ω表示法表示，即 $Ω(f(n))$，表示算法的运行时间至少是 $f(n)$ 的常数倍。

> **注意**：一般而言，我们通常考虑最差情况的复杂度，也就是 $O(f(n))$。

### 验证复杂度公式

#### 极限法验证

**原理**：通过计算 $T(n)$ 与 $f(n)$ 的比值极限来确定渐进复杂度。

- 若 $\lim_{n\to\infty}\frac{T(n)}{f(n)}=0$，则 $T(n)=o(f(n))$
- 若 $\lim_{n\to\infty}\frac{T(n)}{f(n)}=\infty$，则 $T(n)=\omega(f(n))$
- 若 $\lim_{n\to\infty}\frac{T(n)}{f(n)}=c$（$c>0$ 为常数），则 $T(n)=\Theta(f(n))$

**验证方法**：对于给定的 $T(n)$ 和 $f(n)$，计算 $\lim_{n\to\infty}\frac{T(n)}{f(n)}$。

**例子**：对于 $T(n)=2n^2+3n+1$ 和 $f(n)=n^2$，计算极限
$$\lim_{n\to\infty}\frac{2n^2+3n+1}{n^2}=\lim_{n\to\infty}(2 + \frac{3}{n} +\frac{1}{n^2})=2$$

这是一个正常数，所以 $T(n)=\Theta(n^2)$。

> **提示**：一般而言，我们只需要考虑最高次项的系数，除非实在是不确定才会用到这个公式。

## 💻 解递归方程

### 主定理方法

主定理（Master Theorem）是分析递归算法时间复杂度的一个强大工具，适用于形如 $T(n) = aT(\frac{n}{b}) + f(n)$ 的递归方程，其中：

- $a \geq 1$ 是子问题的数量
- $b > 1$ 是子问题规模缩减因子
- $f(n)$ 是分解和合并的额外工作量

**主定理的三种情况**：

1. 若 $f(n) = O(n^{\log_b a-\epsilon})$ 对某个 $\epsilon > 0$：
    - 此时 $T(n) = \Theta(n^{\log_b a})$
2. 若 $f(n) = \Theta(n^{\log_b a}\log^k n)$ 对某个 $k \geq 0$：
    - 此时 $T(n) = \Theta(n^{\log_b a}\log^{k+1} n)$
3. 若 $f(n) = \Omega(n^{\log_b a+\epsilon})$ 对某个 $\epsilon > 0$，且对某个常数 $c < 1$ 和足够大的 $n$ 有 $af(\frac{n}{b}) \leq cf(n)$：
    - 此时 $T(n) = \Theta(f(n))$

**例子**：分析归并排序 $T(n) = 2T(\frac{n}{2}) + n$

- 这里 $a = 2$, $b = 2$, $f(n) = n$
- 计算 $n^{\log_b a} = n^{\log_2 2} = n^1 = n$
- 因为 $f(n) = \Theta(n^{\log_b a})$，符合情况2（$k=0$）
- 所以 $T(n) = \Theta(n\log n)$

### 递归树方法

递归树方法是一种可视化的方式来分析递归方程。

**基本步骤**：

1. 将递归方程表示为一棵树，根节点代表原问题
2. 每个内部节点表示一个子问题，边表示递归调用
3. 对每一层计算总的工作量
4. 累加所有层的工作量得到总复杂度

**例子**：分析 $T(n) = 2T(n/2) + n$

递归树：

- 第0层（根）：工作量 = $n$
- 第1层：2个子问题，每个工作量 = $n/2$，总工作量 = $2 \cdot (n/2) = n$
- 第2层：4个子问题，每个工作量 = $n/4$，总工作量 = $4 \cdot (n/4) = n$
- ...
- 第$\log_2 n$层：$n$个子问题，每个工作量 = $1$，总工作量 = $n$

总工作量 = $n + n + ... + n$ ($\log_2 n + 1$项) = $\Theta(n\log n)$

### 代入法

代入法（也称为归纳法）是通过猜测解的形式，然后使用数学归纳法证明猜测是正确的。

**基本步骤**：

1. 猜测解的形式（通常基于直觉或经验）
2. 使用归纳法证明这个猜测

**例子**：证明 $T(n) = 2T(n/2) + n$ 的解为 $T(n) = O(n\log n)$

假设 $T(n) \leq cn\log n$ 对某个常数 $c > 0$

验证：
$$T(n) = 2T(n/2) + n \leq 2c(n/2)\log(n/2) + n = cn\log(n/2) + n = cn\log n - cn\log 2 + n = cn\log n - cn + n$$

当 $c \geq 1$ 时，$T(n) \leq cn\log n$，假设成立。

> 这要没ai,写latex得累死...


---

**作者：**xingwangzhe

**本文链接：**[https://xingwangzhe.fun/posts/55cab229/](https://xingwangzhe.fun/posts/55cab229/)

本文采用[知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议](https://creativecommons.org/licenses/by-nc-sa/4.0/)进行许可。