CC++ & Algorithm

算法优化策略

较难4
语言版本：C++Python
概述：用生活中的小窍门（比如抄近路、整理书包）来改进算法，让程序跑得更快、用得更省。

算法优化小技巧：让程序像装了加速器

你有没有遇到过这种情况：写好的程序运行很慢，甚至卡住不动？就像你收拾书包时，如果东西乱塞，找笔都要翻半天；如果按顺序放好，一下子就拿到了。算法优化就是给程序装上“加速器”，用更聪明的方法让程序跑得更快、用更少的内存。今天我们就来学两个最实用的优化策略：减少重复计算和换用高效数据结构。这两个方法就像生活中的“抄近路”和“整理书包”，简单又有效。

策略一：减少重复计算 —— 抄近路，一次搞定

生活例子：你每天上学都要经过一条路，如果发现有近路，就能少走冤枉路。同样，在程序里，如果某段计算重复出现很多次，我们可以只算一次，把结果存起来，下次直接拿来用。

具体做法：用一个变量或数组把中间结果记下来，避免重复计算。最常见的例子就是前缀和。

前缀和（Prefix Sum）：适用于需要多次求数组中某一段的总和。比如你有一个零花钱记录数组 money，想知道从第2天到第5天一共花了多少钱。如果每次重新把这几天的钱加起来，一次需要 O(n) 时间，问 n 次就是 O(n²)。但如果我们提前计算出前缀和数组 prefix[i] 表示前 i 天的总钱数，那么区间 [l, r] 的总和就是 prefix[r] - prefix[l-1]，一次查询变成 O(1) 时间，快得像开火箭！

代码示例（保留原代码并补充注释）：

#include <iostream>
using namespace std;
int main() {
    // 某周每天的零花钱（单位：元）
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);    // 数组长度

    // 1. 先计算前缀和数组
    int prefix[n + 1] = {0};                 // prefix[i] 表示前i个数的和，prefix[0]=0
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];  // 累加
    }

    // 2. 查询区间 [2, 5] 的和（下标从1开始，对应arr[1]~arr[4]）
    int l = 2, r = 5;
    int sum = prefix[r] - prefix[l - 1];     // 一次减法搞定
    cout << "区间和: " << sum << endl;       // 输出 4+1+5+9 = 19

    // 3. 再来一次查询 [3, 6] 的和
    l = 3; r = 6;
    sum = prefix[r] - prefix[l - 1];
    cout << "区间和: " << sum << endl;       // 输出 1+5+9+2 = 17

    return 0;
}

这个技巧不仅用于求和，还可以用于求区间的最大值、最小值、乘积等等（通过类似的“预计算”思想）。比如你每天记录的考试成绩，想知道某段时间的平均分，也可以用前缀和先算总分再除以个数。

策略二：换用高效数据结构 —— 整理书包，找东西更快

生活例子：你有一个装满零食的书包，如果东西乱堆，要找一包薯片可能要把所有零食翻一遍（O(n)）；如果按类别分好（薯片放左边，饼干放右边），找起来就快多了。程序里也一样，选择合适的数据结构能让查找、插入、删除变得飞快。

常见的高效数据结构：

  • 二分查找（Binary Search）：要求数据已经排好序。比如你有一本按拼音排序的通讯录，找“张三”不必从第一页翻起，直接翻到中间，比大小，再决定往前翻还是往后翻，很快就能找到。每次查找需要 O(log n) 时间。
  • 哈希表（Hash Table 或 unordered_map）：像是把每件物品贴上一个独一无二的标签，想找什么东西，直接按标签找，一步到位（平均 O(1)）。比如你有一个存储“学号 -> 姓名”的哈希表，输入学号瞬间就能知道名字。

代码示例：用二分查找快速找数

#include <iostream>
#include <algorithm>  // 用于 sort 和 binary_search
using namespace std;

int main() {
    // 同学们的身高（厘米），乱序
    int heights[] = {150, 175, 162, 180, 155, 168};
    int n = sizeof(heights) / sizeof(heights[0]);

    // 先排序（必须排序才能二分）
    sort(heights, heights + n);
    // 排序后：150 155 162 168 175 180

    // 查询 168 是否在数组中
    int target = 168;
    bool found = binary_search(heights, heights + n, target);
    if (found)
        cout << "找到了！" << endl;
    else
        cout << "没找到" << endl;

    return 0;
}

注意：二分查找的前提是数据已经有序，如果忘了排序，结果会完全错误。而哈希表虽然更快速，但需要额外的内存空间（空间换时间），并且不能直接用于求区间和之类的场景。

完整示例：用前缀和解决多次求和问题

假设学校要统计每个班级某次考试的总分，每个班有50个学生，全校有20个班，而且老师会反复问“3班到5班的总分是多少？”、“7班到10班的总分是多少？”……如果每次都把每个班重新加一遍，老师问10次就要算10遍，很慢。用前缀和优化后，先算好每个班的累计总分，每次回答只需要一个减法。

完整可运行代码（保留原代码并扩展为多次查询）：

#include <iostream>
using namespace std;

int main() {
    // 全校20个班的平均分（实际是总分，这里简化用整数）
    int class_scores[] = {85, 92, 78, 90, 88, 76, 95, 82, 89, 91,
                          87, 84, 93, 79, 86, 94, 81, 83, 80, 77};
    int n = sizeof(class_scores) / sizeof(class_scores[0]);

    // 计算前缀和，prefix[i]表示前i个班的总分
    int prefix[n + 1] = {0};
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + class_scores[i - 1];
    }

    // 多次查询区间和（下标从1开始）
    int queries[][2] = {{3, 5}, {7, 10}, {1, 20}};  // 3次查询
    int q = 3;
    for (int i = 0; i < q; i++) {
        int l = queries[i][0], r = queries[i][1];
        int sum = prefix[r] - prefix[l - 1];
        cout << "班级" << l << "到班级" << r << "的总分: " << sum << endl;
    }

    return 0;
}

输出：

班级3到班级5的总分: 78+90+88 = 256
班级7到班级10的总分: 95+82+89+91 = 357
班级1到班级20的总分: 所有班和

? 新手最容易犯的错误

  1. 前缀和数组大小没开对：比如数组有 n 个元素，前缀和数组至少需要 n+1 个位置（prefix[0] 到 prefix[n]）。很多人开成 n 个，导致下标越界。
  2. 忘记初始化 prefix[0] = 0：否则前缀和累加时会从垃圾值开始，结果完全错误。
  3. 下标理解错误：通常我们让数组从下标0开始，但前缀和习惯用下标1到n表示前i个。转换时要小心：prefix[i] 对应原数组的第0到第i-1个元素，首尾边界容易搞混。
  4. 二分查找前忘记排序：二分查找只能用在有序数组上。如果忘了排序，即使数组里真的有目标值也可能找不到，或者得到错误结果。
  5. 哈希表使用不当：C++ 中 unordered_map 的 key 必须支持哈希（如 int、string等），自定义类型需要自己提供哈希函数。另外，哈希表查找很快，但遍历所有元素时比 vector 慢。

? 相关知识点指引

学完这两个优化策略，你可以继续探索：

  • 时间复杂度分析：学会用大O表示法衡量算法的快慢（O(1)、O(log n)、O(n) 等）。
  • 空间换时间：很多优化都需要额外内存，比如前缀和、哈希表、记忆化搜索（如动态规划）。
  • 动态规划：把大问题分解成小问题，并记录子问题的结果来避免重复计算（比如斐波那契数列的递归优化）。
  • 更多高效数据结构：set（红黑树，O(log n) 插入/删除/查找）、priority_queue（堆，优先处理最大或最小元素）、vector 动态数组等。
  • 常用算法优化技巧：滑动窗口、双指针、分治、倍增（如快速幂、ST表）等。

记住：优化不是让代码变得复杂，而是让代码更聪明。多动手，多思考，你的程序也能像装了加速器一样飞速运行！

例题精讲

1单选题

在算法优化中，常用“空间换时间”的策略。以下哪个做法最典型地体现了这一策略？

A使用递归代替迭代
B使用哈希表存储中间结果以避免重复计算
C减少循环中的条件判断语句
D将浮点运算替换为整数运算
2判断题

在深度优先搜索中，剪枝优化是指通过提前终止不符合条件的搜索分支来减少搜索空间，从而提高算法效率。

3填空题
以下函数用于在有序数组中查找目标值的下标，请将___处的代码补充完整，以优化平均时间复杂度（使用二分查找）。

int binarySearch(int arr[], int l, int r, int target) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) ___;
        else ___;
    }
    return -1;
}
4单选题

在动态规划问题中，当状态转移只依赖于前一行或前几行的数据时，可以使用“滚动数组”进行空间优化。这种优化的核心思想是？

A将二维数组降为一维数组，重复利用空间
B将递归改为迭代以减少函数调用开销
C使用贪心策略选择局部最优解
D将时间复杂度从O(n^2)降低到O(n)
5填空题
以下代码用于计算数组前i个元素的和并多次查询区间和，请将___处的代码补充完整，以实现预处理优化（前缀和）。

int prefixSum[100005];
void preprocess(int arr[], int n) {
    prefixSum[0] = 0;
    for (int i = 1; i <= n; ++i) {
        ___;
    }
}
int rangeSum(int l, int r) { // 1-indexed
    return ___;
}