第67章 算法优化

算法优化是程序设计中的核心能力，旨在通过改进算法逻辑、数据结构或实现细节，降低时间复杂度或空间复杂度，提升程序的执行效率。

67.1 算法优化的基本概念

67.1.1 优化目标

1. 时间复杂度优化：减少程序运行时间，例如把$O(n^2)$优化为$O(n\log n)$；
2. 空间复杂度优化：减少内存占用，避免内存溢出，例如$O(n)$优化为$O(1)$；
3. 可读性与可维护性：优化同时保证代码清晰易懂。

67.1.2 优化原则

1. 先保证正确性，再追求效率；
2. 针对性优化，定位程序瓶颈再改进；
3. 时间与空间往往需要权衡，存在空间换时间、时间换空间两种思路。

67.2 时间复杂度优化策略

67.2.1 更换更高效的算法与数据结构

• 排序场景：冒泡排序$O(n^2)$ → 快速/归并排序$O(n\log n)$
• 查找场景：顺序查找$O(n)$ → 二分查找$O(\log n)$（有序前提下）
• 单源最短路：Bellman-Ford $O(nm)$ → 堆优化Dijkstra $O(m\log n)$
• 频繁增删查：数组 → unordered_map/哈希表（平均$O(1)$）

67.2.2 消除重复计算、记忆化缓存

重叠子问题缓存结果，避免重复递归计算，典型如斐波那契：

// 低效递归（指数复杂度）
int fibBad(int n){
    if(n <= 2) return 1;
    return fibBad(n-1) + fibBad(n-2);
}

// 记忆化优化 O(n)
vector<int> memo;
int fibOpt(int n){
    if(n <= 2) return 1;
    if(memo[n] != 0) return memo[n];
    memo[n] = fibOpt(n-1) + fibOpt(n-2);
    return memo[n];
}

缩小循环范围：判断素数只需循环至$\sqrt{n}$，不用遍历到$n$。

67.2.3 预处理数组

前缀和、前缀最值数组，把区间查询从$O(n)$降至$O(1)$。

67.2.4 剪枝（搜索类优化）

DFS、回溯中提前舍弃不可能得到最优解的分支，减少搜索范围。

67.3 空间复杂度优化策略

67.3.1 滚动数组（动态规划专用）

仅保存上一层状态，二维DP压缩一维。示例斐波那契空间$O(1)$：

int fibSpaceOpt(int n){
    if(n <= 1) return n;
    int a = 0, b = 1, c;
    for(int i = 2; i <= n; i++){
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

67.3.2 变量复用、类型精简

能用int不用long long；复用临时变量，不重复创建数组。

67.3.3 位运算压缩布尔标记

用单个int存储32个开关状态，代替bool数组。

67.4 代码层面细节优化

1. 循环优化：将循环内固定计算提到循环外部；适度循环展开；
2. 内存访问：数组优先顺序遍历，利用缓存局部性；
3. 传参优化：大型容器用引用&传递，避免拷贝；简单函数inline；
4. 位运算替代乘除2、奇偶判断：
   • x >> 1等价x / 2；
   • x & 1判断奇偶。

67.5 经典优化案例

1. DP优化：01背包二维数组改为一维逆序遍历；
2. 字符串匹配：暴力$O(nm)$ → KMP $O(n+m)$；
3. 图算法：朴素Dijkstra $O(n^2)$ → 小根堆优化$O(m\log n)$。

67.6 真题示例（用知识/数据结构优化）

67.6.1 等差数列求和：循环 vs 公式

【GESP 八级风格·编程题】 输入 $n$（$1 \le n \le 10^9$），输出 $1+2+\dots+n$ 的值。

朴素循环（$O(n)$，$n$ 大时超时）：

long long sum = 0;
for (long long i = 1; i <= n; ++i) sum += i;   // n=10^9 时约 10 亿次，超时

公式优化（$O(1)$，一步出结果）：

long long ans = n * (n + 1) / 2;               // 等差数列求和公式

long long ans = n % 2 == 0 ? (n / 2) * (n + 1) : n * ((n + 1) / 2);

67.6.2 多次区间求和：前缀和

【GESP 八级风格·编程题】 给定长度为 $n$ 的数组和 $q$ 次询问，每次问区间 $[l,r]$ 的和。$n,q \le 10^5$。

朴素（每次 $O(n)$，总 $O(nq)$ 超时）： 每次重新累加。

前缀和优化（预处理 $O(n)$，每次询问 $O(1)$）：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q; cin >> n >> q;
    vector<long long> a(n), pre(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pre[i + 1] = pre[i] + a[i];          // pre[i+1] = 前 i 个元素和
    }
    while (q--) {
        int l, r; cin >> l >> r;              // 假设下标从 1 开始
        cout << pre[r] - pre[l - 1] << "\n";  // 区间和 = 前缀差
    }
    return 0;
}

练习题

1.（递归优化） 朴素斐波那契递归 fib(n)=fib(n-1)+fib(n-2) 的时间复杂度是？记忆化后变为？

• A. $O(n)$，$O(2^n)$
• B. $O(2^n)$，$O(n)$
• C. $O(n^2)$，$O(n)$
• D. $O(n)$，$O(n)$

2.（空间优化） 01 背包用二维 dp[i][j] 可优化为一维数组，关键技巧是？

• A. 把 j 循环改为正序
• B. 把 j 循环改为逆序（从大到小）
• C. 去掉 i 这一维即可，顺序随意
• D. 用递归替代

3.（公式优化） 求 $1+2+\dots+n$，用公式 $n(n+1)/2$ 的复杂度是？

• A. $O(n)$
• B. $O(1)$
• C. $O(n^2)$
• D. $O(\log n)$

4.（空间换时间） 把"数组里有没有出现过 x"从 $O(n)$ 查找优化到平均 $O(1)$，常用？

• A. 排序后二分
• B. 哈希表（unordered_map / 数组标记）
• C. 前缀和
• D. 并查集

5.（前缀和） 对长度为 $n$ 的数组做 $q$ 次区间求和，用前缀和预处理 + 查询的复杂度是？

• A. 预处理 $O(n)$，每次 $O(1)$
• B. 预处理 $O(n^2)$，每次 $O(1)$
• C. 预处理 $O(n)$，每次 $O(n)$
• D. 预处理 $O(1)$，每次 $O(n)$