# 简单的算法分析和优化

## 1. 为什么要分析算法？

在编写程序解决问题时，我们往往不满足于“能运行”，还希望程序 **跑得快**、**占得少**。算法分析帮助我们：

- 预测程序在更大数据规模下的表现
- 在多种解法中做出合理选择
- 发现性能瓶颈，有针对性地优化

---

## 2. 时间复杂度

### 2.1 定义

**时间复杂度** 描述算法中 **主要运算的次数**，用 **大 O 表示法** 表示。

> 大 O 表示法：只保留数量级最大的项，并忽略该项的系数。

**示例**：

| 实际运算次数 | 时间复杂度 |
| :--- | :--- |
| \(3n^3 + n^2 + 8\) | \(O(n^3)\) |
| \(4 \times 2^n + 2n^4 + 700\) | \(O(2^n)\) |
| 遍历 \(m \times n\) 数组 | \(O(mn)\) |

### 2.2 常见时间复杂度排序

\[
O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
\]

### 2.3 常见复杂度对应的数据规模（参考）

> 假设 1 秒内约可执行 \(5 \times 10^6\) 次基本运算。

| 时间复杂度 | 能承受的大致规模 | 典型算法 |
| :--- | :--- | :--- |
| \(O(1)\) | 任意 | 直接输出结果 |
| \(O(\log n)\) | 任意 | 二分查找、快速幂 |
| \(O(n)\) | 百万级（约 500 万） | 贪心、扫描、遍历 |
| \(O(n\log n)\) | 十万级（约 30~40 万） | 分治（归并排序、二分法等） |
| \(O(n^2)\) | 数千（约 2000~3000） | 枚举、简单动态规划 |
| \(O(n^3)\) | 不到 200 | 较复杂的动态规划 |
| \(O(2^n)\) | 约 24 | 搜索（指数级） |
| \(O(n!)\) | 约 10 | 全排列 |
| \(O(n^n)\) | 约 8 | 暴力破解密码 |

### 2.4 时间复杂度的分类

- **常数时间**：\(O(1)\)
- **多项式时间**：\(O(n), O(n^2), O(n^3), O(n^4), \dots\)
- **指数时间**：\(O(2^n), O(3^n), \dots\)

---

## 3. 空间复杂度

**空间复杂度** 描述算法运行时 **占用的内存空间**，同样用大 O 表示。

- 实际比赛中，数组开得过大容易导致 **内存超限（MLE）**
- 占用过大也会影响 **缓存命中率**，间接拖慢时间

---

## 4. 时间优化技巧

### 4.1 运算速度规律（相对比较）

| 运算类型 | 速度 |
| :--- | :--- |
| 位运算 | 极快 |
| 逻辑运算 | 快 |
| 整数加减乘 | 较快 |
| 整数除法 `/` | 慢（比加减乘慢几十倍） |
| 取余 `%` | 与除法相当 |
| 浮点运算 | 远慢于整型运算 |
| 函数调用 | 较慢（有入栈/出栈开销） |

### 4.2 优化原则

- **减少循环体和递归体中的运算量** —— 这是最见效的优化点
- 能用整数，不用浮点
- 能用位运算，不用算术运算
- 能用逻辑运算，不用四则运算
- 避免在循环内部反复调用函数
- 提前计算不变表达式（循环不变量外提）

---

## 5. 空间优化技巧

### 5.1 常用方法

- **压缩存储**（如位图、稀疏矩阵）
- **滚动数组** —— 只保留最近需要的状态，覆盖旧数据
- 降低数组维度（如三维降二维、二维降一维）

### 5.2 注意事项

- 空间优化即使 **不改变复杂度**，仅减小常数，也可能显著提升性能
- 空间占用影响 **缓存局部性**，优化空间常能间接优化时间

---

## 6. 优化总原则（牢记）

1. **不让程序做已做过的事** —— 利用记忆化、缓存
2. **不让程序做显然没有必要的事** —— 剪枝、提前终止
3. **不解决无用的子问题** —— 分治时只求解必要部分
4. **不对结果进行无意义的引用** —— 避免多余复制/拷贝

---

## 7. 补充：C++ `constexpr` 编译时计算

`constexpr` 是 C++11 引入的关键字，表示函数或变量可在 **编译时求值**，适用于定义数组大小、模板元编程等场景。

**C++11 示例（递归）**：
```cpp
constexpr int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}
constexpr int N = factorial(5);  // N = 120，编译时完成
```
C++14 放宽限制（允许循环）：

```cpp
constexpr int fib(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int t = a + b;
        a = b; b = t;
    }
    return a;
}
```

竞赛中合理使用 constexpr 可将部分运行期计算移至编译期，节省时间。

8. 小结
分析维度	核心指标	优化方向
时间	基本运算次数（大 O）	减少循环层级、选择更快运算
空间	内存占用（大 O）	压缩、滚动、降低维度
算法优化不仅是理论分析，更要在实践中结合数据规模、环境限制（如 1 秒时间限制）做出合理决策。

记住：好的算法 + 恰当的优化 = 高效的解决方案。

简单的算法分析和优化

1. 为什么要分析算法？

在编写程序解决问题时，我们往往不满足于“能运行”，还希望程序 跑得快、占得少。算法分析帮助我们：

预测程序在更大数据规模下的表现
在多种解法中做出合理选择
发现性能瓶颈，有针对性地优化

2. 时间复杂度

2.1 定义

时间复杂度 描述算法中 主要运算的次数，用 大 O 表示法 表示。

大 O 表示法：只保留数量级最大的项，并忽略该项的系数。

示例：

实际运算次数	时间复杂度
(3n^3 + n^2 + 8)	(O(n^3))
(4 \times 2^n + 2n^4 + 700)	(O(2^n))
遍历 (m \times n) 数组	(O(mn))

2.2 常见时间复杂度排序

[ O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) ]

2.3 常见复杂度对应的数据规模（参考）

假设 1 秒内约可执行 (5 \times 10^6) 次基本运算。

时间复杂度	能承受的大致规模	典型算法
(O(1))	任意	直接输出结果
(O(\log n))	任意	二分查找、快速幂
(O(n))	百万级（约 500 万）	贪心、扫描、遍历
(O(n\log n))	十万级（约 30~40 万）	分治（归并排序、二分法等）
(O(n^2))	数千（约 2000~3000）	枚举、简单动态规划
(O(n^3))	不到 200	较复杂的动态规划
(O(2^n))	约 24	搜索（指数级）
(O(n!))	约 10	全排列
(O(n^n))	约 8	暴力破解密码

2.4 时间复杂度的分类

常数时间：(O(1))
多项式时间：(O(n), O(n^2), O(n^3), O(n^4), \dots)
指数时间：(O(2^n), O(3^n), \dots)

3. 空间复杂度

空间复杂度 描述算法运行时 占用的内存空间，同样用大 O 表示。

实际比赛中，数组开得过大容易导致 内存超限（MLE）
占用过大也会影响 缓存命中率，间接拖慢时间

4. 时间优化技巧

4.1 运算速度规律（相对比较）

运算类型	速度
位运算	极快
逻辑运算	快
整数加减乘	较快
整数除法 `/`	慢（比加减乘慢几十倍）
取余 `%`	与除法相当
浮点运算	远慢于整型运算
函数调用	较慢（有入栈/出栈开销）

4.2 优化原则

减少循环体和递归体中的运算量 —— 这是最见效的优化点
能用整数，不用浮点
能用位运算，不用算术运算
能用逻辑运算，不用四则运算
避免在循环内部反复调用函数
提前计算不变表达式（循环不变量外提）

5. 空间优化技巧

5.1 常用方法

压缩存储（如位图、稀疏矩阵）
滚动数组 —— 只保留最近需要的状态，覆盖旧数据
降低数组维度（如三维降二维、二维降一维）

5.2 注意事项

空间优化即使 不改变复杂度，仅减小常数，也可能显著提升性能
空间占用影响 缓存局部性，优化空间常能间接优化时间

6. 优化总原则（牢记）

不让程序做已做过的事 —— 利用记忆化、缓存
不让程序做显然没有必要的事 —— 剪枝、提前终止
不解决无用的子问题 —— 分治时只求解必要部分
不对结果进行无意义的引用 —— 避免多余复制/拷贝

7. 补充：C++ `constexpr` 编译时计算

constexpr 是 C++11 引入的关键字，表示函数或变量可在 编译时求值，适用于定义数组大小、模板元编程等场景。

C++11 示例（递归）：

constexpr int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}
constexpr int N = factorial(5);  // N = 120，编译时完成

C++14 放宽限制（允许循环）：

constexpr int fib(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int t = a + b;
        a = b; b = t;
    }
    return a;
}