第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)$。