第9章算法优化

🎯 本章学习目标

通过本章的学习，你将能够：

理解优化思想：明白同一问题有多种解法，效率差距可达天壤之别
掌握打表预处理：会用筛法、前缀和等空间换时间的技巧
掌握记忆化搜索：能把朴素递归改写成记忆化版本
掌握快速幂：能手写快速幂模板，理解倍增思想
理解单调队列（📚 拓展 · 超纲）：知道滑动窗口最大值的单调队列解法
掌握排序后处理：会用排序+双指针优化两数之和等问题
掌握贪心选择：理解贪心适用条件，会活动安排等经典问题
学会数据结构选型：知道不同场景下数组/哈希/堆/并查集的选择
会用数学公式优化：能用等差/等比求和、约瑟夫递推等替代模拟
培养优化思维：能分析朴素算法瓶颈，选择合适的优化方向

🗺️ 本章知识图谱

算法优化
├── 优化思想
│   ├── 同一问题多种解法
│   │   ├── 斐波那契进化链：O(2ⁿ)→O(n)→O(log n)
│   │   ├── 求和：循环O(n)→公式O(1)
│   │   └── 查找：顺序O(n)→二分O(log n)
│   └── 图论算法选型
│       ├── MST：稠密图Prim，稀疏图Kruskal
│       └── 最短路：Dijkstra / Floyd / Bellman-Ford
├── 七板斧优化方法
│   ├── 打表/预处理：空间换时间
│   │   ├── 埃氏筛法
│   │   └── 前缀和
│   ├── 记忆化搜索：给递归装缓存
│   ├── 去冗余计算：快速幂/倍增
│   ├── 单调队列：滑动窗口最值
│   ├── 排序后处理：排序+双指针
│   ├── 贪心选择：局部最优→全局最优
│   └── 数据结构选型
│       ├── 哈希表：查找O(1)
│       ├── 堆：取最值O(log n)
│       └── 并查集：连通性≈O(1)
├── 数学优化
│   ├── 等差数列求和：O(1)
│   ├── 等比数列求和：O(log n)（+快速幂）
│   ├── 约瑟夫递推：O(n)
│   ├── 周期问题：取模映射
│   └── 消元法：减少循环层数
└── 答题策略
    ├── 编程题：先朴素拿分，再逐步优化
    └── 选择题：看数据规模+前提条件

一、📋 考纲原文与考点全景

据 CCF 官方八级考纲，算法优化部分要求：

掌握算法优化的思想与方法。理解不同算法求解同一问题的效率差异；掌握打表/预处理、记忆化搜索、去除冗余计算、单调栈与队列、排序后处理、贪心选择、合理选择数据结构等常用优化手段；能够运用等差数列、等比数列求和公式及数学推导，将模拟/枚举类算法优化为公式算法。

考点	难度	选择/判断	编程题
同一问题多解法复杂度对比（斐波那契/求和/查找）	⭐⭐	🔥极高	高
打表、预处理、前缀和（空间换时间）	⭐⭐	高	🔥极高
记忆化搜索	⭐⭐	高	高
快速幂、单调队列、排序+双指针	⭐⭐⭐	中	高
数据结构选型（哈希/堆/并查集）	⭐⭐⭐	高	中
等差/等比求和公式 O(1) 优化	⭐⭐	🔥极高	高
公式法替代模拟（约瑟夫、周期问题）	⭐⭐⭐	中	高

🔥 高频考点：八级选择题特别爱考"给出程序，判断优化前后的时间复杂度"；编程题则常把"朴素做法超时、优化做法 AC"作为区分度——会不会优化，直接决定你是 60 分还是 90 分。

二、同一问题，多种解法：横向对比中的优化思维 🧠

算法优化的第一课，不是学新算法，而是建立一个信念：一个问题永远不止一种解法，解法之间的效率差距可以大到离谱。

初级阶段的目标是"能做对"——程序跑出正确答案就万事大吉；而八级要求的思维转变是"做得快"：在动笔写代码之前，先估算数据规模下朴素做法会不会超时、有没有重复计算可以消除、能不能用一个公式代替一段循环。请记住第8期学过的"1 秒法则"：现代评测机 1 秒大约能执行 10⁸ 次简单运算。如果朴素做法的运算量达到 10¹⁰，它不是"慢一点"，而是注定超时，此时优化不是锦上添花，而是唯一的活路。

1.1 斐波那契：一条完整的优化进化链 🐇

求斐波那契数列第 n 项 F(n)（F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)），是检验优化思想的最佳标本：

解法	时间复杂度	空间复杂度	n=40 的感受
朴素递归	O(2ⁿ)	O(n) 栈	要算上亿次，肉眼可见地卡
记忆化搜索	O(n)	O(n)	瞬间出结果
递推（迭代）	O(n)	O(1)	瞬间出结果
矩阵快速幂 / 通项公式	O(log n)	O(1)	n=10⁹ 也不怕

朴素写法（两语言对照）：

cpp

// C++：朴素递归，O(2^n)，大量重复计算
long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // fib(n-2) 被反复计算
}

⚠️ 易错点：朴素递归慢的根源不是"递归"本身，而是重复计算——F(5) 会被算 5 次，F(10) 会被算 55 次，F(n) 的调用次数本身就是斐波那契数！

优化写法：矩阵快速幂 O(log n)（📚 拓展 · 超纲）

利用恒等式 $\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}^n$ ，配合第5章学过的倍增/快速幂思想，把 n 次转移压成 log n 次矩阵乘法：

cpp

// C++：矩阵快速幂求斐波那契，O(log n)
typedef long long ll;
void mul(ll a[2][2], ll b[2][2], ll c[2][2]) {
    ll t[2][2] = {0};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                t[i][j] += a[i][k] * b[k][j];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) c[i][j] = t[i][j];
}
ll fib(ll n) {
    ll res[2][2] = { {1,0},{0,1} };       // 单位矩阵（相当于 1）
    ll base[2][2] = { {1,1},{1,0} };      // 转移矩阵
    while (n) {                          // 快速幂框架
        if (n & 1) mul(res, base, res);
        mul(base, base, base);
        n >>= 1;
    }
    return res[0][1];                    // res = base^n，右上角即 F(n)
}

🔥 高频考点：O(2ⁿ) → O(n) → O(log n) 这条进化链，选择题常考"哪种写法能处理 n=10⁹"（答案：矩阵快速幂/通项公式），判断题常考"记忆化搜索把时间复杂度从 O(2ⁿ) 降到了 O(n²)"（❌，是降到 O(n)）。

1.2 求和：循环累加 O(n) → 公式 O(1)

求 1+2+…+n：

cpp

// C++ 朴素：循环累加 O(n)
long long s = 0;
for (int i = 1; i <= n; i++) s += i;

// C++ 优化：等差求和公式 O(1)
long long s = 1LL * n * (n + 1) / 2;

n=10⁹ 时，循环要跑 10 亿次，公式只算一次乘除——这就是数学的力量。

1.3 查找：顺序查找 O(n) → 二分查找 O(log n)

在有序数组中找 x：

cpp

// C++ 朴素：顺序查找 O(n)
int findNaive(int a[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (a[i] == x) return i;
    return -1;
}

// C++ 优化：二分查找 O(log n)（前提：数组有序）
int binarySearch(int a[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;   // 防溢出写法
        if (a[mid] == x) return mid;
        if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

⚠️ 易错点：二分查找的前提是数据有序！在无序数组上二分，结果毫无意义。n=10⁶ 时 O(n) 与 O(log n) ≈ 20 次比较，差距约 5 万倍。另外注意取中点要用 l + (r-l)/2 而非 (l+r)/2——两数相加在极端情况下可能溢出 int 范围，这是笔试读代码题里的经典细节。

1.4 图论算法选型：没有"最好"，只有"最合适"

第7期学过的图论算法，选型本身就是优化：

问题	算法	时间复杂度	适用场景
最小生成树	Prim（邻接矩阵）	O(n²)	稠密图、点数少
最小生成树	Kruskal（并查集）	O(m log m)	稀疏图、边数少
单源最短路	Dijkstra（堆优化）	O(m log n)	边权非负
单源最短路	Bellman-Ford / SPFA	O(nm)	有负权边/判负环
全源最短路	Floyd	O(n³)	n 很小、一次求所有点对

🔥 高频考点："边权为负的图能不能用 Dijkstra？"——不能（贪心选最小距离的前提被破坏）；"n=100 的稠密图求全源最短路用什么？"——Floyd，代码最短、常数最小。

三、算法优化的一般方法："七板斧" 🛠️

2.1 打表 / 预处理：空间换时间 📦

思想：把会被反复用到的结果提前算好存起来，用空间换时间。

典型场景：Q 次询问"x 是不是质数"。朴素做法每次试除，总复杂度 O(Q·√x)；埃氏筛预处理后每次询问 O(1)：

cpp

// C++ 朴素：每次询问试除 O(√x)
bool isPrimeNaive(int x) {
    if (x < 2) return false;
    for (int i = 2; 1LL * i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

// C++ 优化：埃氏筛预处理 O(N log log N)，询问 O(1)
const int MAXN = 1000005;
bool notPrime[MAXN];
void sieve() {
    notPrime[0] = notPrime[1] = true;
    for (int i = 2; 1LL * i * i < MAXN; i++)
        if (!notPrime[i])
            for (int j = i * i; j < MAXN; j += i)
                notPrime[j] = true;
}
// 询问：!notPrime[x] 即为质数

同族利器——前缀和：区间和询问从 O(n) 降到 O(1)：

cpp

// C++：前缀和预处理 O(n)，每次区间询问 O(1)
long long pre[1000005];
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
// 区间 [l, r] 的和：
long long s = pre[r] - pre[l - 1];

对比	预处理	单次询问	Q 次询问总复杂度
朴素（每次现算）	无	O(n)	O(Q·n)
前缀和/筛法	O(n)	O(1)	O(n + Q)

2.2 记忆化搜索：给递归装个"缓存" 🧾

思想：递归函数算过的状态存起来，第二次遇到直接返回。以"走台阶（每次1或2级）"为例：

cpp

// C++ 朴素：裸递归 O(2^n)
long long waysNaive(int n) {
    if (n <= 1) return 1;
    return waysNaive(n - 1) + waysNaive(n - 2);
}

// C++ 优化：记忆化搜索 O(n)
long long memo[1005];
long long ways(int n) {
    if (n <= 1) return 1;
    if (memo[n]) return memo[n];          // 算过就直接取
    return memo[n] = ways(n - 1) + ways(n - 2);
}

💡 记忆化搜索与递推（DP）时间复杂度相同，区别只是自顶向下 vs 自底向上；它只算"用得到的状态"，在状态稀疏时甚至比递推更省。

2.3 去掉冗余计算：快速幂 ⚡

求 aᵇ mod m，朴素连乘做 b 次乘法；注意到 aᵇ = (a^(b/2))²，把指数折半：

cpp

// C++ 朴素：连乘 O(b)
long long powNaive(long long a, long long b, long long mod) {
    long long res = 1;
    for (long long i = 0; i < b; i++) res = res * a % mod;
    return res;
}

// C++ 优化：快速幂 O(log b)
long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;  // 指数该位为1，乘进答案
        a = a * a % mod;                 // 底数平方
        b >>= 1;                         // 指数右移一位
    }
    return res;
}

b=10⁹ 时，O(b) 必死，O(log b) ≈ 30 次循环轻松 AC。

2.4 单调队列入门：滑动窗口最大值 🪟（📚 拓展 · 超纲）

问题：长度为 n 的数组，求所有长度为 k 的滑动窗口的最大值。朴素做法每个窗口扫一遍 O(nk)；用单调双端队列维护"候选最大值"，每个元素至多入队出队一次，O(n)：

cpp

// C++ 优化：单调队列 O(n)
#include <deque>
deque<int> dq;                       // 存下标，队首→队尾对应值严格递减
for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // 队首过期
    while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();  // 保递减
    dq.push_back(i);
    if (i >= k - 1) cout << a[dq.front()] << " ";               // 队首即窗口最大
}

🔥 高频考点：单调队列里存的是下标不是值（要判断过期）；队列内对应的值保持单调递减求最大值、单调递增求最小值。

2.5 排序后处理：两数之和 🔢

问题：数组中是否存在两个数之和等于 target。朴素双重循环 O(n²)；先排序，再双指针 O(n log n)：

cpp

// C++ 朴素：双重循环 O(n^2)
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] + a[j] == target) { /* 找到 */ }

// C++ 优化：排序 + 双指针 O(n log n)
sort(a, a + n);
int l = 0, r = n - 1;
while (l < r) {
    int s = a[l] + a[r];
    if (s == target) { /* 找到 */ break; }
    else if (s < target) l++;   // 和太小，左指针右移
    else r--;                   // 和太大，右指针左移
}

排序后处理的同族应用还有：双指针去重、排序后贪心、排序后二分——"先排序"往往是 O(n²) → O(n log n) 的第一步。

2.6 贪心选择：活动安排问题 📅

问题：n 个活动各有开始/结束时间，同一时刻只能参加一个，最多能参加几个？朴素枚举/DP 是 O(n²) 起步；按结束时间排序后贪心——结束越早越先选，给后面留更多时间——O(n log n)：

cpp

// C++ 优化：贪心 O(n log n)
struct Act { int s, e; };
sort(acts, acts + n, [](const Act& x, const Act& y) {
    return x.e < y.e;                     // 按结束时间升序
});
int cnt = 0, lastEnd = -1;
for (int i = 0; i < n; i++)
    if (acts[i].s >= lastEnd) {           // 与上一个选中活动不冲突
        cnt++;
        lastEnd = acts[i].e;
    }

⚠️ 易错点：贪心不是万能的！它能用的前提是问题具备贪心选择性质（局部最优能推出全局最优）。0/1 背包用贪心选单位价值最高的物品就是错的——考试判断题常设此陷阱。

2.7 数据结构选型：选对"容器"，复杂度天差地别 🗂️

同一个操作，用不同数据结构，复杂度可能跨数量级：

需求	数组	哈希表	堆（优先队列）	并查集
按值查找/判存在	O(n)	O(1)	O(n)	—
取最值	O(n) 排序 O(n log n)	O(n)	O(log n)	—
插入/删除	O(n)	O(1)	O(log n)	—
合并集合/判连通	O(n) DFS	—	—	≈O(1)

并查集模板（连通性问题的标配，Kruskal 算法的核心）：

cpp

// C++：并查集（路径压缩）
int fa[100005];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = find(y); }

🔥 高频考点："统计不同元素个数"用哈希集合 O(n)，不要双重循环 O(n²)；"动态维护前 k 大"用堆；"朋友关系是否连通、修道路连通所有城市"用并查集。

2.8 优化手法速查总表

考前最后再过一遍这张表，考场上对号入座：

症状（朴素做法）	诊断	优化药方	复杂度变化
递归反复算同一状态	重复计算	记忆化搜索 / 递推	O(2ⁿ)→O(n)
多次询问，每次现算	重复劳动	打表、筛法、前缀和预处理	O(Qn)→O(n+Q)
循环里每次从头找最值/求和	冗余扫描	单调队列、堆、前缀和	O(nk)→O(n)
双重循环找配对	枚举无序	排序 + 双指针 / 哈希表	O(n²)→O(n log n)
每步都做选择且无后效性	可贪心	排序后贪心选择	O(n²)→O(n log n)
连乘/连加次数巨大	可折半	快速幂 / 倍增	O(n)→O(log n)
按值查找/判存在很慢	容器选错	数组换哈希表	O(n)→O(1)
连通性判断反复 DFS	容器选错	并查集	O(n)→≈O(1)
有规律的累加/计数	可建模	等差/等比公式、数学递推	O(n)→O(1)

⚠️ 易错点：所有优化都有前提——二分要求有序、贪心要求贪心选择性质、记忆化要求子问题重叠、公式法要求结果仍在数值范围内（注意取模与溢出）。不看前提乱用优化，比不优化更危险。

四、用数学知识优化算法 🔢

编程的尽头是数学。当一段循环所做的事情恰好是某个有公式的数列求和、某个有周期的规律、某个可以消元的方程组时，数学就能让成百上千次循环蒸发为一行表达式。八级考纲明确要求掌握两类数列求和公式，并能把"模拟/枚举"升级为"公式计算"。

3.1 等差数列求和：O(n) → O(1)

公式： $S_n = \dfrac{n(a_1+a_n)}{2} = na_1 + \dfrac{n(n-1)}{2}d$

求 1 到 100 所有奇数之和（1+3+5+…+99，共 50 项）：

cpp

// C++ 朴素：循环 O(n)
long long s = 0;
for (int i = 1; i <= 99; i += 2) s += i;

// C++ 优化：公式 O(1)：n=50 项，首项1，末项99
long long s = 50LL * (1 + 99) / 2;   // = 2500

3.2 等比数列求和：O(n) → O(1)

公式（q≠1）： $S_n = \dfrac{a_1(1-q^n)}{1-q} = \dfrac{a_1(q^n-1)}{q-1}$

经典例子：1+2+4+…+2ⁿ⁻¹ = 2ⁿ−1（国王赏麦故事）。求 $1+3+3^2+\cdots+3^{n-1}$ ：

cpp

// C++ 朴素：循环累加 O(n)
long long s = 0, t = 1;
for (int i = 0; i < n; i++) { s += t; t *= 3; }

// C++ 优化：等比公式 + 快速幂 O(log n)
long long s = (qpow(3, n, MOD) - 1 + MOD) % MOD
              * qpow(2, MOD - 2, MOD) % MOD;  // (3^n-1)/(3-1)，除法取模用逆元

⚠️ 易错点：整数场景等比公式可直接整除；若答案要取模，"除以 (q−1)"要换成乘逆元（费马小定理：q−1 的逆元为 (q−1)^(MOD−2)），这是八级编程题的隐蔽失分点。

3.3 公式法替代模拟：约瑟夫问题 🎯

问题：n 个人围成圈编号 0~n−1，从 0 号开始报数，数到 k−1 的人出局，求最后幸存者编号。

朴素模拟用列表删除，每次删除 O(n)，总计 O(n²)，n=10⁶ 时超时。数学递推：设 J(n) 为 n 个人时的幸存者编号，则

J(1)=0,\qquad J(n)=(J(n-1)+k)\bmod n

cpp

// C++ 优化：数学递推 O(n)
int josephus(int n, int k) {
    int pos = 0;                        // J(1) = 0
    for (int i = 2; i <= n; i++)
        pos = (pos + k) % i;            // J(i) = (J(i-1)+k) mod i
    return pos;
}

周期问题同理：斐波那契数列的个位以 60 为周期（Pisano 周期 mod 10），求 F(n) 的个位无需算到 n，只需 n % 60：

周期思想在考试中十分常见：星期几的推算、循环小数的循环节、棋盘/灯阵按固定规律翻转，本质都是"先打一个周期的表，再用取模把大下标映射回一个周期内"。它把看似无穷的递推，压缩成有限张查找表——这正是打表法与数学规律的完美结合。

3.4 数学推导缩小枚举范围：百钱买百鸡 🐔

公鸡 5 文/只、母鸡 3 文/只、小鸡 1 文 3 只，100 文买 100 只，各买多少？朴素三重枚举 O(n³)。

推导：设公鸡 x、母鸡 y、小鸡 z：

\begin{cases} x+y+z=100\\ 5x+3y+\dfrac{z}{3}=100 \end{cases}

第二式乘 3 减第一式： $14x+8y=200$ ，即 $7x+4y=100$ ，得 $y=(100-7x)/4$ 。只需枚举 x 一个变量，O(n³) → O(n)：

cpp

// C++ 优化：数学推导后单重循环 O(n)
for (int x = 0; 7 * x <= 100; x++) {
    int rem = 100 - 7 * x;
    if (rem % 4 != 0) continue;        // y 必须是整数
    int y = rem / 4;
    int z = 100 - x - y;
    if (z >= 0 && z % 3 == 0)          // 小鸡数必须为 3 的倍数
        cout << x << " " << y << " " << z << endl;
}

💡 通用套路：遇到多重循环枚举，先列方程、用约束消元——每消掉一个变量，复杂度就降一个数量级。

五、综合例题 ✏️

例题1（单选题）

下列求斐波那契第 n 项的方法中，能够在 n=10⁹ 时 1 秒内出结果的是（　）

A. 朴素递归 fib(n)=fib(n-1)+fib(n-2)
B. 记忆化搜索
C. 一维数组递推
D. 矩阵快速幂

🔑 点击查看答案与解析

答案： D

A 为 O(2ⁿ)，B、C 为 O(n) 且需要 O(n) 空间，n=10⁹ 都无法完成；矩阵快速幂为 O(log n)，约 30 次矩阵乘法即可。通项公式法（比内公式）在理论上也是 O(1)，但大数下浮点精度不足，竞赛中以矩阵快速幂为准。

例题2（判断题）

"打表预处理是用空间换时间，因此只要内存允许，对任何题目都应该先预处理，预处理不会带来任何坏处。"

🔑 点击查看答案与解析

答案： 错误 ❌

预处理有价值的前提是结果会被多次/反复使用。若只询问一次，预处理 O(N) 反而比直接计算 O(√x) 更慢；此外预处理占用内存，N 过大时可能 MLE。优化要结合数据范围与询问次数，没有"永远最优"的手段。

例题3（编程题）：区间和询问

题目：给定 n 个整数组成的数组 a，以及 Q 次询问，每次给出 l、r，求 a[l]+…+a[r]（下标从 1 开始）。

输入：第一行 n、Q；第二行 n 个整数；接下来 Q 行每行两个整数 l、r。 数据范围：n, Q ≤ 10⁵，|aᵢ| ≤ 10⁴。

🔑 点击查看答案与解析

**解析：**朴素每次循环累加 O(Q·n) = 10¹⁰ 次运算，超时；前缀和预处理 O(n)，每次询问 O(1)，总计 O(n+Q)。

cpp

#include <iostream>
using namespace std;
long long pre[100005];
int main() {
    ios::sync_with_stdio(false);
    int n, Q;
    cin >> n >> Q;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    while (Q--) {
        int l, r; cin >> l >> r;
        cout << pre[r] - pre[l - 1] << "\n";
    }
    return 0;
}

例题4（编程题）：约瑟夫报数

题目：n 个小朋友围成一圈编号 1~n，从 1 号开始报数，报到 m 的小朋友出列，下一个人重新从 1 开始报数。求最后剩下的小朋友编号。1 ≤ n ≤ 10⁶，1 ≤ m ≤ 1000。

🔑 点击查看答案与解析

**解析：**n 达 10⁶，链表/数组模拟删除 O(n²) 必然超时。用约瑟夫递推 J(1)=0，J(i)=(J(i−1)+m) mod i（0 基编号），最终答案 +1 转回 1 基：

cpp

#include <iostream>
using namespace std;
int main() {
    long long n, m;
    cin >> n >> m;
    long long pos = 0;                  // J(1) = 0
    for (long long i = 2; i <= n; i++)
        pos = (pos + m) % i;
    cout << pos + 1 << endl;            // 转回 1 基编号
    return 0;
}

六、📝 实战练习

练习题 1（单选题）

题目： 下列求斐波那契数列第 n 项的方法中，能够处理 n = 10⁹ 并在 1 秒内出结果的是（）

A. 朴素递归 fib(n) = fib(n-1) + fib(n-2)
B. 记忆化搜索
C. 一维数组递推
D. 矩阵快速幂

🔑 点击查看答案与解析

答案： D **解析：**A 为 O(2ⁿ)，B、C 为 O(n) 且需要 O(n) 空间，n=10⁹ 都无法完成；矩阵快速幂为 O(log n)，约 30 次矩阵乘法即可。通项公式法（比内公式）在理论上也是 O(1)，但大数下浮点精度不足，竞赛中以矩阵快速幂为准。

练习题 2（单选题）

题目： 给定长度为 n 的数组，有 Q 次询问，每次查询区间 [l, r] 的和。n 和 Q 均为 10⁵ 量级，最优的解法时间复杂度是（）

A. O(Q·n)
B. O(n + Q)
C. O(n log n + Q log n)
D. O(n² + Q)

🔑 点击查看答案与解析

答案： B **解析：**朴素每次循环累加 O(Q·n) = 10¹⁰ 次运算，必然超时；前缀和预处理 O(n)，每次询问 O(1)，总计 O(n+Q) = 2×10⁵，轻松通过。 🍎 这就像老师要多次问"第3到第8个同学的身高和是多少"，提前算好"前缀身高和"，每次一问一答，不用每次重新量。

练习题 3（单选题）

题目： 关于贪心算法，下列说法正确的是（）

A. 贪心算法总能得到全局最优解
B. 0/1 背包问题用贪心算法（按单位价值排序）可以得到最优解
C. 活动安排问题（选择最多不冲突活动）按结束时间排序后贪心选择是正确的
D. 只要问题可以分解成子问题，就一定能用贪心算法

🔑 点击查看答案与解析

答案： C **解析：**A 错，贪心只有在满足贪心选择性质时才得到全局最优；B 错，0/1 背包用贪心是经典反例（可能装不满）；C 对，活动安排按结束时间排序贪心是经典正确用法；D 错，"一定"太绝对，要看具体问题。 ⚠️ 贪心不是万能的，考试判断题常设陷阱。

练习题 4（单选题）

题目： 要高效判断两个节点是否在同一个连通分量中（即判连通），最合适的数据结构是（）

A. 数组
B. 哈希表
C. 链表
D. 并查集

🔑 点击查看答案与解析

答案： D **解析：**并查集（路径压缩+按秩合并）的查找操作近似 O(1)，专门用于处理连通性/集合合并问题。哈希表适合判存在但不适合判连通；数组和链表判断连通需要遍历，效率低。

练习题 5（判断题）

题目： 打表预处理是用空间换时间，因此只要内存允许，对任何题目都应该先做预处理，预处理不会带来任何坏处。（）

🔑 点击查看答案与解析

答案： 错误 ❌ 解析：预处理有价值的前提是结果会被多次/反复使用。若只询问一次，预处理 O(N) 反而比直接计算 O(√x) 更慢；此外预处理占用内存，N 过大时可能 MLE。优化要结合数据范围与询问次数，没有"永远最优"的手段。

练习题 6（判断题）

题目： 快速幂算法的时间复杂度是 O(log b)，其中 b 是指数。当 b = 10⁹ 时，只需约 30 次循环。（）

🔑 点击查看答案与解析

答案： 正确 ✅ **解析：**快速幂每次把指数折半（b >>= 1），共循环 log₂b 次，每次做常数次乘法和取模，故时间复杂度 O(log b)。当 b=10⁹ 时，只需约 30 次循环。

练习题 7（程序阅读题）

题目： 阅读以下代码，回答问题。

cpp

int countDivisors(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            total++;
        }
    }
    return total;
}

（1）这段代码的时间复杂度是？
A. O(n)
B. O(n log n)
C. O(n²)
D. O(√n)

（2）这段代码实际上计算的是什么？请简述一种进一步优化的思路。

🔑 点击查看答案与解析

解析：
时间复杂度：O(n log n) 外层 n 次，对于每个 i，内层枚举 i 的倍数，有 n/i 次。总次数 = n/1 + n/2 + n/3 + ... + n/n = n × (1 + 1/2 + 1/3 + ... + 1/n) = n × H(n) 调和级数 H(n) ≈ ln n + γ（欧拉常数），故总复杂度 O(n log n)。
优化思路：这个函数实际求的是 1~n 中所有数的约数个数之和。也可以理解为：对每个 d（约数），计算 1~n 中有多少个数是 d 的倍数，即 n/d 个。所以答案 = Σ(n/d)，d 从 1 到 n，和上面一致。要优化到 O(√n)：利用整除分块（数论分块），n/d 的值在很多区间内相同，如 d ∈ [l, r] 时 n/d = k，可一块一块地加，共约 2√n 个块。

练习题 8（编程题）

题目： 约瑟夫报数问题：n 个人围成一圈，编号为 1 ~ n。从 1 号开始报数，报到 m 的人出列，下一个人重新从 1 开始报数。求最后剩下的人的编号。

输入：两个整数 n, m（1 ≤ n ≤ 10⁶，1 ≤ m ≤ 1000）
输出：一个整数，最后剩下的人的编号

样例输入：

5 3

样例输出：

🔑 点击查看答案与解析

**解析：**n 达 10⁶，链表/数组模拟删除 O(n²) 必然超时。用约瑟夫递推公式：
J(1) = 0，J(i) = (J(i−1) + m) mod i（0 基编号），最终答案 +1 转回 1 基。
cpp
#include <iostream>
using namespace std;
int main() {
    long long n, m;
    cin >> n >> m;
    long long pos = 0;                  // J(1) = 0
    for (long long i = 2; i <= n; i++)
        pos = (pos + m) % i;
    cout << pos + 1 << endl;            // 转回 1 基编号
    return 0;
}
时间复杂度 O(n)，空间 O(1)，n=10⁶ 也能轻松通过。 🍎 这就像"每次有人出局后，把圈子重新编号"——递推公式直接告诉你最后剩下的人在新编号里的位置，不用真的模拟出列过程。

练习题 9（单选题）

题目： 给定一个含 n 个顶点、m 条边的带权无向图，求最小生成树。下列说法正确的是？

A. 任何情况下 Kruskal 算法都比 Prim 算法快
B. 当图是稠密图（m 接近 n²）时，Prim（邻接矩阵）更合适
C. 当图是稀疏图（m 接近 n）时，Prim（邻接矩阵）更合适
D. Kruskal 算法不需要排序，所以更快

🔑 点击查看答案与解析

答案： B

解析： 最小生成树两大算法选型对比：

算法	数据结构	时间复杂度	适用场景
Prim（邻接矩阵）	二维数组	O(n²)	稠密图（m 大、n 小）
Prim（堆优化）	优先队列+邻接表	O(m log n)	稀疏图
Kruskal	并查集+排序边	O(m log m)	稀疏图（m 小、n 大）

A 错误："任何情况下都快"太绝对。稠密图中 Prim(O(n²)) 反而比 Kruskal(O(m log m)=O(n² log n)) 更快
B 正确 ✅：稠密图 m ≈ n²，Prim 邻接矩阵版 O(n²) 优于 Kruskal 的 O(n² log n)
C 错误：稀疏图应该用 Kruskal 或堆优化 Prim，邻接矩阵版 Prim 的 O(n²) 会浪费大量时间扫不存在的边
D 错误：Kruskal 需要先对所有边按权值排序（O(m log m)），这是它的主要时间开销

💡 选型口诀：稠密用 Prim（邻接矩阵），稀疏用 Kruskal。就像路少的时候数路边（Kruskal 数边），路多的时候数路口（Prim 数点）。

练习题 10（判断题）

题目： "两数之和"问题（在数组中找两个数之和等于 target），用排序 + 双指针的方法可以把时间复杂度从 O(n²) 降到 O(n)。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 排序 + 双指针的时间复杂度是 O(n log n)，不是 O(n)。

分解来看：

排序：O(n log n) —— 这是瓶颈
双指针扫描：O(n) —— 左右指针各移动最多 n 次

总复杂度 = O(n log n) + O(n) = O(n log n)

虽然没有降到 O(n)，但从 O(n²) 降到 O(n log n) 已经是巨大的提升了：

n = 10⁴ 时：O(n²) = 10⁸（接近1秒上限），O(n log n) ≈ 10⁴ × 14 ≈ 1.4×10⁵（飞快）
n = 10⁵ 时：O(n²) = 10¹⁰（严重超时），O(n log n) ≈ 10⁵ × 17 ≈ 1.7×10⁶（轻松通过）

🔥 常见陷阱：不要因为"双指针是线性扫描"就以为整体是 O(n)——别忘了前面排序的代价！排序往往是排序后处理类算法的复杂度瓶颈。

七、📊 考点总结表

考点	重要程度	出题形式	易错点
斐波那契优化链	⭐⭐⭐	选择、判断	记忆化搜索是O(n)不是O(n²)；矩阵快速幂O(log n)
前缀和/打表预处理	⭐⭐⭐	选择、编程	只问一次时预处理反而更慢；注意下标从1开始
记忆化搜索	⭐⭐⭐	选择、编程	忘记初始化记忆数组；边界条件处理不当
快速幂	⭐⭐⭐	选择、编程	忘记取模导致溢出；初始值设为0（应为1）
排序+双指针	⭐⭐	选择、编程	双指针移动条件判断错误；需先排序
贪心算法	⭐⭐⭐	选择、判断	误以为所有问题都能用贪心；0/1背包用贪心是错的
数据结构选型	⭐⭐⭐	选择	哈希表vs堆vs并查集适用场景混淆
等差/等比求和公式	⭐⭐⭐	选择、编程	等比求和取模时除法要换成乘逆元
约瑟夫递推	⭐⭐	选择、编程	0基/1基编号转换错误；递推初始条件记错
数学消元优化	⭐⭐	编程	变量关系推导错误；忘记检验约束条件

⭐ 必背速记卡

┌─────────────────────────────────────────┐
│  1. 优化核心思想：                      │
│     消除重复计算，减少枚举范围，        │
│     用对数据结构，数学公式替代模拟       │
├─────────────────────────────────────────┤
│  2. 斐波那契进化链：                    │
│     朴素递归O(2ⁿ) → 记忆化/递推O(n)     │
│     → 矩阵快速幂O(log n)                │
├─────────────────────────────────────────┤
│  3. 打表/前缀和：空间换时间             │
│     Q次询问从O(Qn)降到O(n+Q)            │
│     前提：结果会被反复使用              │
├─────────────────────────────────────────┤
│  4. 记忆化搜索=递归+缓存               │
│     算过的状态存起来，下次直接返回       │
│     与DP时间相同，区别：自顶向下vs自底向上│
├─────────────────────────────────────────┤
│  5. 快速幂模板：                        │
│     res=1; while(b){if(b&1)res=res*a%m;│
│     a=a*a%m; b>>=1;}                    │
│     时间O(log b)                        │
├─────────────────────────────────────────┤
│  6. 单调队列存下标（要判断过期），       │
│     递减求最大值，递增求最小值           │
├─────────────────────────────────────────┤
│  7. 排序+双指针：两数之和等配对问题      │
│     O(n²) → O(n log n)                  │
│     前提：排序不影响答案正确性           │
├─────────────────────────────────────────┤
│  8. 贪心不是万能的！                    │
│     需满足贪心选择性质+最优子结构        │
│     0/1背包用贪心是错的                 │
├─────────────────────────────────────────┤
│  9. 数据结构选型：                      │
│     判存在→哈希表O(1)                   │
│     取最值→堆O(log n)                   │
│     判连通→并查集≈O(1)                  │
├─────────────────────────────────────────┤
│ 10. 等差数列求和：n(a₁+aₙ)/2 → O(1)     │
│     等比数列求和：a₁(qⁿ-1)/(q-1)        │
│     取模时除法换乘逆元                   │
├─────────────────────────────────────────┤
│ 11. 约瑟夫递推：J(1)=0,                 │
│     J(n)=(J(n-1)+m) mod n（0基）        │
│     从O(n²)模拟降到O(n)递推             │
├─────────────────────────────────────────┤
│ 12. 周期问题：先找周期T，再n%T映射       │
│     斐波那契个位周期=60                 │
├─────────────────────────────────────────┤
│ 13. 编程题优化三步走：                  │
│     先写朴素拿分→找瓶颈→小步替换验证    │
├─────────────────────────────────────────┤
│ 14. 优化都有前提：                      │
│     二分要有序、贪心要性质、             │
│     记忆化要有重叠子问题                 │
└─────────────────────────────────────────┘

考场优化题答题策略 🎯

八级编程题采用 IOI 赛制、可多次提交，遇到"会做但可能超时"的题，建议按三步走：

先写朴素版拿部分分：确认逻辑正确、小数据能过，先提交保住基础分，绝不在空白代码上硬想最优解；
对着复杂度表找瓶颈：用第8章的方法估算朴素版复杂度，对照本章"症状—药方"总表定位优化点；
小步替换、随时验证：每次只替换一个模块（如先加前缀和，再换快速幂），保证每一步都可回退、可验证。

选择题/判断题中的优化题，则务必看清三个要素：数据规模（n 有多大）、询问次数（Q 有多少）、前提条件（是否有序、是否有负权）——复杂度数字本身不难，难的是把题目场景和优化前提对应起来。

八、🏁 全书回顾：九章旅程

至此，本书九章已全部学完，让我们一起回看这段旅程：

章	主题	对应考纲知识块
第1章	总览：考纲全景与备考规划	——
第2章	计数原理	加法原理、乘法原理
第3章	排列与组合	排列、组合
第4章	杨辉三角	杨辉三角的定义与实现
第5章	倍增法	倍增的概念
第6章	代数与平面几何	一元/二元一次方程、基本图形面积
第7章	图论算法及综合应用	最小生成树（Kruskal/Prim）、最短路（Dijkstra/Floyd）
第8章	算法的时间和空间效率分析	复杂度一般分析方法、各类算法复杂度
第9章	算法优化	算法差异分析、一般优化方法、数学知识优化

九章内容，从考纲全景到组合数学，从倍增思想到图论算法，从复杂度分析到本章的算法优化——八级考纲的每一块版图，我们都已走遍。

九、考完八级之后：通往信息学竞赛的进阶路径 🚀

GESP 八级是 GESP 认证的最高级，但它不是终点，而是信息学竞赛之路的起点站。通过八级，意味着你已经具备了挑战权威赛事的知识储备：

阶段	赛事/认证	定位	与 GESP 八级的衔接
①	CSP-J（入门级）	中国计算机学会主办，初中组信奥预选赛	八级内容可全覆盖，建议作为赛后第一站热身
②	CSP-S（提高级）	高中组信奥预选赛，含金量高	需补充：更难的 DP、图论进阶、数据结构（线段树/树状数组）
③	NOIP（全国青少年信息学奥林匹克联赛）	省赛区竞赛，升学认可度高	CSP-S 取得成绩后的自然延伸
④	省选 / NOI（全国赛）	各省选拔 → 全国总决赛	省队水平，需系统学习高级算法与大量集训
⑤	IOI（国际信息学奥林匹克）	中学生信奥全球最高舞台	国家集训队佼佼者代表中国出征

十、🎓 全书寄语

亲爱的考生：

九章内容，从第1章的考纲全景图开始，到本章的算法优化收尾。你已经知道 O(2ⁿ) 与 O(log n) 之间隔着多么巨大的鸿沟——而这恰恰像极了学习本身：朴素的努力很珍贵，但找到好方法的努力，才能指数级地成长。

GESP 八级是 CCF 编程能力等级认证的最高峰。当你走出考场、拿到那张八级证书时，请记得：它证明的不只是你会写代码，而是你已经拥有了用计算机的视角拆解问题、用数学的头脑简化问题、用工程师的严谨解决问题的思维方式。

山高路远，道阻且长。CSP-J/S 的赛场在等你，NOIP 的领奖台在等你，更远的地方，IOI 的赛场灯火通明。

GESP 八级全书至此学完，而你的信息学竞赛之路，才刚刚开始。

向着更高的舞台，出发吧！🚩

第9章 算法优化 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、📋 考纲原文与考点全景 ​

二、同一问题，多种解法：横向对比中的优化思维 🧠 ​

1.1 斐波那契：一条完整的优化进化链 🐇 ​

1.2 求和：循环累加 O(n) → 公式 O(1) ​

1.3 查找：顺序查找 O(n) → 二分查找 O(log n) ​

1.4 图论算法选型：没有"最好"，只有"最合适" ​

三、算法优化的一般方法："七板斧" 🛠️ ​

2.1 打表 / 预处理：空间换时间 📦 ​

2.2 记忆化搜索：给递归装个"缓存" 🧾 ​

2.3 去掉冗余计算：快速幂 ⚡ ​

2.4 单调队列入门：滑动窗口最大值 🪟（📚 拓展 · 超纲） ​

2.5 排序后处理：两数之和 🔢 ​

2.6 贪心选择：活动安排问题 📅 ​

2.7 数据结构选型：选对"容器"，复杂度天差地别 🗂️ ​

2.8 优化手法速查总表 ​

四、用数学知识优化算法 🔢 ​

3.1 等差数列求和：O(n) → O(1) ​

3.2 等比数列求和：O(n) → O(1) ​

3.3 公式法替代模拟：约瑟夫问题 🎯 ​

3.4 数学推导缩小枚举范围：百钱买百鸡 🐔 ​

五、综合例题 ✏️ ​

例题1（单选题） ​

例题2（判断题） ​

例题3（编程题）：区间和询问 ​

例题4（编程题）：约瑟夫报数 ​

六、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（单选题） ​

练习题 4（单选题） ​

练习题 5（判断题） ​

练习题 6（判断题） ​

练习题 7（程序阅读题） ​

练习题 8（编程题） ​

练习题 9（单选题） ​

练习题 10（判断题） ​

七、📊 考点总结表 ​

⭐ 必背速记卡 ​

考场优化题答题策略 🎯 ​

八、🏁 全书回顾：九章旅程 ​

九、考完八级之后：通往信息学竞赛的进阶路径 🚀 ​

十、🎓 全书寄语 ​

第9章算法优化

🎯 本章学习目标

🗺️ 本章知识图谱

一、📋 考纲原文与考点全景

二、同一问题，多种解法：横向对比中的优化思维 🧠

1.1 斐波那契：一条完整的优化进化链 🐇

1.2 求和：循环累加 O(n) → 公式 O(1)

1.3 查找：顺序查找 O(n) → 二分查找 O(log n)

1.4 图论算法选型：没有"最好"，只有"最合适"

三、算法优化的一般方法："七板斧" 🛠️

2.1 打表 / 预处理：空间换时间 📦

2.2 记忆化搜索：给递归装个"缓存" 🧾

2.3 去掉冗余计算：快速幂 ⚡

2.4 单调队列入门：滑动窗口最大值 🪟（📚 拓展 · 超纲）

2.5 排序后处理：两数之和 🔢

2.6 贪心选择：活动安排问题 📅

2.7 数据结构选型：选对"容器"，复杂度天差地别 🗂️

2.8 优化手法速查总表

四、用数学知识优化算法 🔢

3.1 等差数列求和：O(n) → O(1)

3.2 等比数列求和：O(n) → O(1)

3.3 公式法替代模拟：约瑟夫问题 🎯

3.4 数学推导缩小枚举范围：百钱买百鸡 🐔

五、综合例题 ✏️

例题1（单选题）

例题2（判断题）

例题3（编程题）：区间和询问

例题4（编程题）：约瑟夫报数

六、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（单选题）

练习题 4（单选题）

练习题 5（判断题）

练习题 6（判断题）

练习题 7（程序阅读题）

练习题 8（编程题）

练习题 9（单选题）

练习题 10（判断题）

七、📊 考点总结表

⭐ 必背速记卡

考场优化题答题策略 🎯

八、🏁 全书回顾：九章旅程

九、考完八级之后：通往信息学竞赛的进阶路径 🚀

十、🎓 全书寄语