admin 的博客
课程总结要求
admin SU @ 2026-10-10 1:02:01

如何写好一篇算法总结

零、为什么要写算法总结？

学算法的过程中，有一个很常见的困境：上课听懂了，例题看懂了，自己一写就卡住；过两个星期再看，连基本思路都忘了。

这不是你记忆力差，而是你缺少了一个关键的步骤——把知识"翻译"成自己的语言。

上课的板书是老师的语言，题解是别人的语言，讲义是教练的语言。只有你自己从头到尾写过一遍总结，用你自己的逻辑重新组织过一遍，这个算法才真正属于你。

算法总结不完全等同于题解，它本质上是一次你和自己的对话：

"我到底学会了什么？"
"这个东西为什么能这样算？"
"我当初是怎么被它坑的？"

下面，我们把这四个问题拆解成总结的四个组成部分。

一、总结的四个组成部分

一篇好的算法总结，至少应该包含下面四个模块。我们用前缀和作为例子，逐一说明每个模块应该怎么写。

模块 1：问题定义与暴力解法

写作目标：让一个完全没学过这个算法的人，读完这一段之后，能知道"这个算法是用来干什么的"以及"如果不学这个算法，我会怎么做"。

你需要写清楚三件事：

这个问题长什么样？——用一句话定义问题类型，最好配上具体的输入输出样例。
暴力做法怎么做？——哪怕暴力会超时，也要写出来。因为暴力是理解优化动机的起点。
暴力做法的时间复杂度是多少？——这是后续优化效果的量尺。

以前缀和为例的示范：

前缀和用来解决静态数组的区间求和问题：给定一个长度为 $N$ 的数组 $a$ ，有 $Q$ 次询问，每次询问给定两个下标 $l, r$ ，求 $a\_l + a\_{l+1} + \dots + a\_r$ 。

暴力做法：对于每次询问，用一个 $for$ 循环从 $l$ 累加到 $r$ 。每次询问耗时 $O(r-l+1)$ ，最坏 $O(N)$ 。 $Q$ 次询问的总复杂度是 $O(NQ)$ 。

当 $N = 10^5$ ， $Q = 10^5$ 时， $NQ = 10^{10}$ ，远超一秒的承受范围——所以需要优化。

要点提醒：

暴力做法一定要有代码片段，哪怕只有三四行。代码比文字更直观。
时间复杂度分析不要跳步。比如"每次询问 $O(N)$ ， $Q$ 次就是 $O(NQ)$ "——标注出 $N$ 和 $Q$ 分别是什么。
如果题目有特殊条件（比如"数组元素都是正数"），这里就要说清楚，因为这些条件可能影响后续的优化方向。

模块 2：算法思维模式

写作目标：回答一个问题——"正常人怎么能想到这个算法？"

这是四个模块中最难写、但也最有价值的部分。没有人天生就能想出优美的算法，每个算法背后都有一条可以追溯的思维线索。

你需要在这部分做的是：把这个"线索"还原出来。

一般来说，可以从以下几个角度切入（选一到两个即可，不需要全部覆盖）：

角度 A：从"重复计算"中发现浪费

以前缀和为例：

暴力做法的瓶颈在于：每次询问都重新算一遍区间和。比如询问 $(1, 5)$ 要从头加到尾，询问 $(1, 6)$ 又要从头加到尾——中间 $a\_1$ 到 $a\_5$ 被算了两次。

你很快就会发现：如果你已经知道了 $a\_1 + \dots + a\_5$ ，那么 $a\_1 + \dots + a\_6$ 只需要在它的基础上加一个 $a\_6$ 。

这个想法推而广之，就是前缀和的核心。

这种方法的关键词是 "重复计算"、"冗余"、"已经被算过的信息"。

角度 B：从更简单的技巧演化而来

前缀和可以被看作**"递推"思想的直接应用**。如果你学过递推（比如用数组 $fib[i]$ 存储斐波那契数），你对"用一个数组把前面算过的结果存起来"这种操作应该不陌生。

前缀和数组 $pre[i]$ 定义了一个递推关系： $pre[i] = pre[i-1] + a[i]$ ，其中 $pre[0] = 0$ 。

如果暴力是"每次沿着马路走一遍"，前缀和就是在路边每隔一段放一个"路标"，上面写着"从起点到这里一共走了多远"。你想知道两个路标之间的距离，只需要拿两个路标上的数字相减就行。

这种方法的关键词是 "从 XX 演化而来"、"本质上就是 XX 的扩展"。

角度 C：想象发明人是怎么想的（合理脑补）

想象你面对一百万个数字。每次有人问你"第 12345 个到第 67890 个的累加和是多少"，你就从头加一遍。加到第十次的时候，你崩溃了。

然后你灵光一闪：我为什么不先把"从第 1 个加到第 k 个"的答案全都提前算好，存到一个数组里？之后任何区间 $[l, r]$ 的和，只需要用"前 r 个的和"减去"前 l-1 个的和"就行了。

这就是**预计算（precomputation）**思想——把反复要用到的中间结果提前算好存起来，用空间换时间。

这种方法的关键词是 "换位思考"、"如果是你会怎么想"。虽然不一定是历史上真实的发明过程，但对于理解算法非常有帮助。

角度 D：从题目关键信息与性质中找到破局线索

前缀和能成立，有一个隐藏前提：数组是静态的——元素不会在中途被修改。如果没有这个性质，每次修改都要重建前缀和数组，前缀和就不再适用了。

另外，区间求和满足可减性： $sum[l, r] = sum[1, r] - sum[1, l-1]$ 。不是所有运算都能这样拆——比如区间最大值就不行（你不能用"前缀最大值"相减得到区间最大值）。

在思考算法时，先圈出题目中的关键条件——静态还是动态？运算是否可逆/可减？数据是否有单调性？——这些性质往往直接决定了你能用哪一类算法。

这种方法的关键词是 "题目条件"、"运算性质"、"约束决定算法"。

角度 E：用自己的语言解释核心公式、性质或不变量

前缀和的核心公式只有一行： $pre[i] = pre[i-1] + a[i]$ 。看上去很简单，但你需要用自己的话解释清楚： $pre[i]$ 代表什么？ $pre[i-1]$ 为什么可以加 $a[i]$ ？ $pre[0]$ 为什么是 0？

更一般地说，任何算法都有关键的数学性质或不变量。比如快速幂依赖指数的二进制分解，并查集依赖路径压缩不改变连通性，差分数组依赖"相邻差的累加能还原原数组"。不要只把公式抄一遍——用自然语言翻译一遍，说明它为什么是对的、为什么不会出错。

这种方法的关键词是 "公式翻译"、"性质解释"、"为什么对"。

总结一下这个模块的写作要点：

写法	适合什么类型的算法
从重复计算中发现浪费	各种优化类算法（前缀和、记忆化搜索、DP）
从更简单的技巧演化而来	有明确前置知识的算法（KMP $\leftarrow$ 暴力匹配，并查集 $\leftarrow$ 链表）
脑补发明人的思路	几乎所有算法，尤其是名字自带思想的那种（贪心、分治）
从题目关键信息与性质中找到破局线索	有特殊约束或运算性质的算法（前缀和要求可减性、线段树要求区间可合并）
用自己的语言解释核心公式/性质/不变量	所有算法，尤其是公式多或依赖不变量的（数论、DP 状态转移、图论性质）

模块 3：实现原理与踩坑记录

写作目标：把算法从思想落实到代码，同时标记出容易出错的地方。

3.1 核心实现

以前缀和为例：

步骤一：构建前缀和数组

int a[N], pre[N];  // a 是原数组，pre 是前缀和数组
pre[0] = 0;                     // 哨兵：前 0 个元素的和是 0
for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + a[i]; // 递推
}

这一步耗时 $O(N)$ ，只需做一次。

步骤二：查询区间和

int sum = pre[r] - pre[l - 1];  // O(1) 查询！

$Q$ 次询问的总复杂度降为 $O(N + Q)$ 。

复杂度闭环：写完优化实现后，应该回头和模块 1 里的暴力复杂度做一次对比——暴力是 $O(NQ)$ ，优化后是 $O(N+Q)$ 。这个"从 XX 降到 XX"的闭环能直观展示优化效果，也帮助你衡量自己到底节省了多少时间。

关键代码行一定要配注释。不要默认读者能一眼看懂 pre[r] - pre[l-1] 为什么是对的——解释一句"前 r 个的和减去前 l-1 个的和，剩下的正好是 $[l, r]$ 的区间和"。

3.2 踩坑记录

这里列出你实际写代码时遇到过的、或者容易遇到的坑。每个坑配上一个错误代码 + 为什么错 + 正确写法的三段式说明。

坑 1：下标从 0 还是从 1 开始？

// 错误示范（下标记混乱）
pre[i] = pre[i - 1] + a[i];  // 当 i=0 时，pre[-1] 越界！

正确做法：统一使用 1-based 下标（即 $a[1]$ 是第一个元素），并在 $pre[0]$ 设一个哨兵值 0。这样 $pre[l-1]$ 在 $l=1$ 时访问 $pre[0]$ ，合法且有明确含义。

坑 2：数据类型溢出

int pre[N];  // 如果数组元素很大或 N 很大，前缀和可能超出 int 范围

正确做法：根据数据范围判断是否需要 long long。经验法则——当 $N \ge 10^5$ 且元素值 $\ge 10^4$ 时，前缀和大概率会爆 int。

坑 3：忘记 $pre[0] = 0$

for (int i = 1; i <= n; i++)
    pre[i] = pre[i - 1] + a[i];
// 忘了初始化 pre[0]，pre[1] 会拿到一个随机值

全局数组默认初始化为 0，但局部数组不会。如果你把 pre 声明在 main 函数内部，必须手动初始化 pre[0] = 0，或者直接声明为全局变量。

写作要点：

每个坑至少要有一个代码反例。光说"别这样"不如把错的那一行贴出来。
解释"为什么会错"的时候不要一笔带过，要说明底层原因（越界、溢出、未初始化等）。

模块 4：我与这个算法的故事

写作目标：让总结有自己的"个人色彩"。这一部分不用写得很长，但一定要真实。

你可以从以下角度选一两个写：

被什么题卡过？——当时怎么想的，为什么卡住了，最后怎么发现的。
代码上遇到过什么麻烦？——调了多久，最后发现是什么问题。
有没有"啊哈时刻"？——哪个瞬间突然觉得这个算法真妙。
有没有在奇怪的场景下用上过它？——比如在某个看起来不相关的题目里突然发现能用。

示范：

我第一次真正"认识"前缀和，是在一道叫"区间和"的模板题上。我写完暴力，信心满满地提交——TLE（超时）。我当时的反应是："不就加几个数吗，这也能超时？"

后来学会前缀和之后，我才明白暴力有多蠢——同样的加法重复了几万次。从那以后，我养成了一个习惯：先看有没有重复计算，再看能不能预计算。

代码上最惨的一次翻车是：我声明了 int pre[100005]，结果有一组数据的答案超过了 $2^{31}$ ，WA 了半小时没找到原因。最后改成 long long pre[100005] 瞬间 AC。从此以后，凡是前缀和，我条件反射地写 long long。

写作要点：

不要编故事。编的故事读起来很假，而且对你自己复习没有帮助。
如果暂时没有"被卡过"的经历，可以先空着，等以后遇到了再补。一份好的算法总结是持续更新的。

二、完整示范：一篇前缀和的算法总结

下面是把上面四个模块组合在一起的完整范例。你可以把它当作模板，替换成你要总结的算法。

前缀和算法总结

问题类型：静态数组的区间求和。给定长度为 $N$ 的数组， $Q$ 次询问 $[l, r]$ 的和。

暴力做法：

int sum = 0;
for (int i = l; i <= r; i++)
    sum += a[i];

单次询问最坏 $O(N)$ ， $Q$ 次总复杂度 $O(NQ)$ ，在 $N$ 和 $Q$ 均为 $10^5$ 的规模下无法通过。

思维来源：

暴力每次询问都要重新遍历一遍区间。如果你已经算过 $a\_1+\dots+a\_5$ ，再算 $a\_1+\dots+a\_6$ 时前面的部分就重复了。推而广之——如果提前算出"前 $i$ 个元素的和"，任何区间 $[l, r]$ 的和就可以用"前 $r$ 个的和"减去"前 $l-1$ 个的和"在 $O(1)$ 时间内得到。

本质上，这是递推 + 预计算的组合：用递推把前缀和数组构建出来（ $O(N)$ ），之后用预计算的结果快速回答每个查询（ $O(1)$ ）。思想核心是用空间换时间——多开一个 pre[N] 数组，把查询从 $O(NQ)$ 降到 $O(N+Q)$ 。

实现：

#include <iostream>
using namespace std;

const int N = 100005;
long long a[N], pre[N];  // long long 防溢出

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    pre[0] = 0;
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + a[i];

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << endl;
    }
    return 0;
}

踩坑清单：

坑	原因	解决
下标越界 `pre[-1]`	使用 0-based 下标，`l-1` 在 `l=0` 时越界	统一使用 1-based 下标，`pre[0]=0` 作为哨兵
结果溢出	`int` 存不下大范围的前缀和	使用 `long long`
局部数组忘记初始化	局部 `pre[0]` 拿到随机值	手动写 `pre[0] = 0`，或将数组声明为全局
查询时写成 `pre[r] - pre[l]`	没理解边界， $[l,r]$ 应该减去 $l-1$	画图验证： $[1,3]=pre[3]-pre[0]$ ，所以是 $pre[r]-pre[l-1]$

个人故事：

我第一次写前缀和，在模板题上 TLE，当时完全不能理解"为什么加几个数也会超时"。学完前缀和之后回头看暴力做法，才意识到 $10^5 \times 10^5 = 10^{10}$ 这个量级有多可怕。

另一次调试花了半小时：代码逻辑全对，但有一半的测试点 WA。逐行检查也没发现问题，最后把 int 全改成 long long 就 AC 了。从那以后，我写前缀和完全不用 int——long long 是一种肌肉记忆。

三、写总结的实用建议

3.1 什么时候写？

最佳时机：刚学完一个算法的当天或第二天。这时候你对"不懂的地方"最敏感，写出来的总结最有温度。
不推荐的时机：考前突击。那时候你只想背模板，没有心思写有深度的总结。

3.2 写多长？

对于简单算法（如前缀和、二分），200~400 字的核心内容就够了，加上代码和踩坑记录，总长度在 500~800 字。
对于中等复杂度的算法（如 DP、最短路），可能要到 800~1500 字。
不求字数多，但求每个模块都覆盖到。

3.3 用什么工具？

Markdown 是最推荐的格式。语法简单，支持代码块，方便分类和搜索。
文件名建议用 {序号}_{算法名}.md 的格式，比如 1_前缀和.md，2_二分查找.md。
可以在每篇总结末尾加上标签（如 #区间查询 #预计算 #O(1)查询），方便日后按场景查找。

3.4 写完之后的检查清单

在保存之前，自查下面几个问题：

[ ] 如果我半年后忘干净了，读完这篇总结能否回忆起核心思路？
[ ] 暴力做法是否配了代码？
[ ] 算法为什么有效——有没有用我自己的逻辑解释清楚？
[ ] 踩坑记录是否包含了具体的错误代码和修复方法？
[ ] 是否有一个我个人的真实经历（哪怕就两句话）？

结语

一篇好的算法总结，不追求文笔优美，不追求面面俱到。它只需要做到一件事：让你自己以后能快速捡起来。

如果你写完一篇总结后，觉得"这个东西好像还挺简单的嘛"，那说明你已经真正理解了。反过来，如果你写的时候磕磕巴巴，总是不知道怎么解释某一步——恭喜你，你发现了自己的知识盲区，这正是写总结最大的价值。

目前还没有评论...

课程总结要求