---
tags: [算法分析与设计]
abstract: 递推式、代换法、递归树法与主方法
finished: false
上一篇: [[计算机系/算法分析与设计/04 递归与分治算法|上一篇]]
下一篇: [[计算机系/算法分析与设计/算法分析2动态规划|下一篇]]
返回目录: [[计算机系/算法分析与设计/算法分析|算法分析与设计学习指南]]
前置知识: [[计算机系/算法分析与设计/04 递归与分治算法|前置知识]]
---
# 复杂度分析专题

### 计算时间复杂度 

#### 代换法

先猜测有某个界存在，然后利用数学归纳法。

#### 递归树法

分治法就是以2为底，就是$log_2 n=lgn$

将递归式转换为树形结构，树中的节点代表在不同递归层次付出的代价，

#### 主方法



 主方法适用递归方程的形式$$T\left( n \right) =aT\left( n/b \right) +f\left( n \right) $$

a:子问题的个数

b:子问题的规模
$$
\left\{
\begin{array}{ll}
T(n)=\Theta(n^{\log_b a}), & n^{\log_b a}>f(n)\\
T(n)=\Theta(n^{\log_b a}\log n), & n^{\log_b a}=f(n)\\
T(n)=\Theta(f(n)), & n^{\log_b a}<f(n)
\end{array}
\right.
$$

紧确渐进取不等式大的那一端

如果相等则乘以个



归纳法算法

（1）主要内容

l 整数幂、多项式求值、生成排列、寻找多数元素






----


```c
for (int i = 0; i < n; i++) {
    // 循环体
}
```
## 一、循环头判断次数为什么是 n+1 次？

因为：

循环判断次数 = 循环体执行次数 + 1

多出来的那 1 次，就是**最后一次判断失败、退出循环**的那一次。



## 二、拆开看：两个 n 分别代表什么？
```C
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 循环体
    }
}
```
内层循环头：

```c
for (int j = 0; j < n; j++)
```

第一个 n：来自外层循环

- 外层循环 `for (int i = 0; i < n; i++)` 的循环体执行了多少次？
- 执行了 n 次。
- 每执行一次外层循环体，就会**重新启动一次内层循环**。
- 所以内层循环被启动了 n 次。

第二个 n+1：来自内层循环本身

- 内层循环每次被启动后，循环头会执行多少次判断？
- 是 n+1 次（前面已经解释过，因为最后一次判断失败退出）。
- 所以每次启动内层循环，循环头要执行 n+1 次。

两者相乘：

内层循环头总次数 = n × (n+1) = n(n+1)
                    ↑        ↑
              外层触发次数   每次内层的判断次数

## 三、为什么不是 n²？

因为 n² 是**循环体**的执行次数，不是**循环头**的。

| 部分 | 执行次数 | 解释 |
|---|---|---|
| 外层循环头 | n+1 | 外层自己的判断次数 |
| 外层循环体 | n | 外层循环体执行 n 次 |
| 内层循环头 | n(n+1) | 外层 n 次 × 每次内层 n+1 次判断 |
| 内层循环体 | n² | 外层 n 次 × 每次内层 n 次循环体 |

**循环体是 n²，循环头是 n(n+1)，两者相差 n。**

## 四、总结一句话

**n(n+1) 里的两个 n：**

- 第一个 n：外层循环触发内层的次数。
- 第二个 n+1：每次内层循环头的判断次数。

内层循环头总次数 = n × (n+1) = n(n+1)

而内层循环体的次数是 n × n = n²，两者差了 n 次（多出来的失败判断）。


好，我们完全用 **cost / times** 的方式，把这两种情况写成表格，你就彻底清楚它们为什么最终复杂度一样、但结构不同了。

 一、双重循环（显式嵌套）
```cpp
for (int i = 0; i < n; i++) {        // 行 1
    for (int j = 0; j < n; j++) {    // 行 2
        sum += A[i] + A[j];          // 行 3
    }
}
```

| 行号  | 代码                            | cost  | times    |
| --- | ----------------------------- | ----- | -------- |
| 1   | `for (int i = 0; i < n; i++)` | $c_1$ | $n+1$    |
| 2   | `for (int j = 0; j < n; j++)` | $c_2$ | $n(n+1)$ |
| 3   | `sum += A[i] + A[j];`         | $c_3$ | $n^2$    |
**总时间：**
$$
T(n)=c_1(n+1)+c_2 n(n+1)+c_3 n^2
$$
化简：
$$
T(n)=(c_2+c_3)n^2+(c_1+c_2)n+c_1=O(n^2)
$$
## 五、显式嵌套 vs 隐式嵌套（函数调用）

| 对比项 | 双重循环 | 函数调用 |
|---|---|---|
| 复杂度来源 | 两层循环直接叠加 | 外层循环 × 被调用函数的复杂度 |
| 隐藏性 | 复杂度是"显式"的，肉眼可见 | 复杂度是"隐式"的，需要看被调用函数才能知道 |
| 分析难度 | 简单，数嵌套层数即可 | 需要深入函数内部，分析它的复杂度 |



## 六、函数调用（隐式嵌套）

```c
for (int i = 0; i < n; i++) {        // 行 1
    doSomethingWithArray(A, n);       // 行 2
}
void doSomethingWithArray(int A[], int n) {
    for (int j = 0; j < n; j++) {    // 行 3
        sum += A[j];                  // 行 4
    }
}
```

现在我们要分别对**外层循环**和**函数内部**来标 cost 和 times。

### 外层循环

| 行号 | 代码 | cost | times |
|---|---|---|---|
| 1 | `for (int i = 0; i < n; i++)` | c₁ | n+1 |
| 2 | `doSomethingWithArray(A, n);` | C_func | n |

注意：行 2 的 cost 不再是常数，而是**函数调用的代价** C_func。

### 函数内部

| 行号 | 代码 | cost | times |
|---|---|---|---|
| 3 | `for (int j = 0; j < n; j++)` | c₃ | n+1 |
| 4 | `sum += A[j];` | c₄ | n |

**函数 doSomethingWithArray 每次调用的时间：**

C_func = c₃(n+1) + c₄n = (c₃ + c₄)n + c₃

所以：

C_func = O(n)

三、把函数调用代回外层

行 2 的总代价：

$$
C_{\text{func}} \times n = O(n) \times n = O(n^2)
$$

**总时间：**

$$
T(n)=c_1(n+1)+C_{\text{func}} \cdot n=O(n)+O(n^2)=O(n^2)
$$
## 七、对比两张表

| 对比项 | 双重循环 | 函数调用 |
|---|---|---|
| **行 2 的 cost** | c₂（常数） | C_func = O(n)（不是常数） |
| **行 2 的 times** | n(n+1)（内层总共执行 n² 次） | n（函数只被调用 n 次） |
| **行 2 的总代价** | c₂ · n² = O(n²) | O(n) · n = O(n²) |
| **复杂度来源** | times 是 n²，cost 是 O(1) | times 是 n，cost 是 O(n) |
| **最终结果** | O(n²) | O(n²) |

## 八、这告诉我们什么？

### 1. 复杂度是"乘积"

T(n) = cost × times

不管是 cost 大还是 times 大，只要乘积一样，最终复杂度就一样。

### 2. "看代码结构"的时候，要递归地看

- 看到双重循环：直接数嵌套层数，就能猜出 O(n²)。
- 看到函数调用：不能只看外层，必须打开函数，看它的 cost 是多少。
- 如果函数里还有函数调用，就要继续往下看。

### 3. 这就是为什么《算法导论》说"检查总体结构"

"总体结构"不只是看表面有几层循环，而是要看：

- 每一层的 times 是多少？
- 每一层的 cost 是多少？
- 两者相乘，才是这一层的总代价。

## 九、为什么要区分这两种情况？

因为 **"看代码结构"和"看复杂度"是两件事**。

《算法导论》里提到"检查算法的总体结构"，指的是：

> 如果你看到的是一个双重循环结构，你可以**立刻**判断出它是 O(n²)，不用去数里面具体做了什么。

但如果是函数调用：

```c
for (int i = 0; i < n; i++) {
    doSomethingWithArray(A, n);
}
```

你**不能只看这个 for 循环**就说它是 O(n)。你必须**打开那个函数**，看看里面到底是 O(1) 还是 O(n)。

如果 `doSomethingWithArray` 内部只是一个简单的赋值，那整体就是 O(n)。  
如果 `doSomethingWithArray` 内部又有一个循环遍历整个数组，那整体就是 O(n²)。

## 十、更极端的例子：函数调用链

再给你看一个更隐蔽的：

```c
for (int i = 0; i < n; i++) {
    f(A, n);
}
void f(int A[], int n) {
    for (int j = 0; j < n; j++) {
        g(A, n);
    }
}
void g(int A[], int n) {
    for (int k = 0; k < n; k++) {
        // O(1)
    }
}
```

表面上看，最外层只有一层循环。  
但实际上，它等价于**三层嵌套**，复杂度是 O(n³)。

这就是为什么《算法导论》强调：

> **"检查算法的总体结构"**

这个"总体结构"不是只看最外层，而是要**递归地看下去**，直到看清楚每个函数内部的执行代价。

## 十一、总结

| 你的问题 | 答案 |
|---|---|
| 这个 `for + O(n) 函数调用` 是不是等价于双重循环？ | **从复杂度结果看，是的，都是 O(n²)。** |
| 那为什么还要区分？ | **因为代码结构不同，分析方法不同，复杂度可能隐藏得更深。** |
| 我之前说的"不是双重循环"是什么意思？ | **是说它代码形态上不是显式嵌套，但复杂度等价。** |

所以，你说的对：**从时间复杂度上看，它就是双重循环。**  
我之前说的"不是双重循环"只是从**代码结构**角度区分，不矛盾。

## 十二、渐近记号与匿名函数

### 核心概念：一个渐近记号 = 一个匿名函数

作者首先指出：

> "一个表达式中匿名函数的数目，可以理解为等于渐近记号出现的次数。"

**什么叫"匿名函数"？**  
就是 O(f(n)) 里的那个"隐藏的"函数。比如 O(n) 其实代表"某个函数 g(n)，它满足 g(n) ≤ c · n"。

**关键规则：**

- 出现 1 次渐近记号 → 1 个匿名函数。
- 出现 k 次渐近记号 → 代表 k 个**不同的**匿名函数（即使它们长得一样）。

### 例子：求和式 ∑ᵢ₌₁ⁿ O(i)

图片里举了一个反例：

∑ᵢ₌₁ⁿ O(i)

这句话的意思是：

- 在这个求和里，**只有一个渐近记号** O(i)。
- 所以，这里只有**一个**匿名函数 f(i)。
- 这个表达式应该理解为：∑ᵢ₌₁ⁿ f(i)，其中 f(i) = O(i)。

**也就是说：**  
这是"**一个函数 f**，它在 n 项上的求和"，而不是"n 个不同的函数，各自不同"。

**它不等于：**

O(1) + O(2) + ⋯ + O(n)

为什么？因为后者里**出现了 n 个渐近记号**，代表 n 个**不同的匿名函数**，这在数学上没有一个清晰、统一的解释。

> **结论：∑ᵢ₌₁ⁿ O(i) 是一个"整体"，不能拆成 n 个 O(·) 相加。**