レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

🌸 咲夜の秘密メロディ

分類

站點統計

文章

79

分類

16

標籤

24

總字數

394,971

運行天數

0 天

最後活動

0 天前

13531 字

35 分鐘

算法学习总览与复杂度分析

2026-06-03

Algorithm

Study Notes

/

Algorithm

第 1 章算法学习总览与复杂度分析#

本章目标：建立算法学习的“总地图”，理解为什么同一问题会因为数据规模不同而需要完全不同的解法。

1.1 学习目标#

理解算法的输入、输出、有限步骤和正确性。
掌握时间复杂度、空间复杂度、最坏情况、平均情况、均摊分析。
能根据数据范围反推可接受的算法级别。
能写出简单循环、递归和分治算法的复杂度。
建立“先证明，后实现，最后测试”的训练习惯。

能力矩阵：

能力域	入门	进阶	熟练
复杂度	会看 O(n)	会估算嵌套循环	能用递推式分析分治
正确性	会跑样例	会写循环不变量	能用归纳证明算法
建模	能读懂题意	能抽象变量约束	能转化成经典模型
测试	会手测	会构造边界	会随机对拍

1.2 什么是算法#

算法是一组有限、确定、可执行的步骤，用来把输入转化为输出。

一个算法至少要回答四个问题：

输入是什么？
输出是什么？
每一步怎么做？
为什么一定得到正确答案？

例如“在数组中找最大值”：

1
best = a[0]
2
for x in a:
3
    if x > best:
4
        best = x
5
return best

这里的循环不变量是：处理到第 i 个元素后，best 等于前 i 个元素的最大值。

1.3 时间复杂度#

时间复杂度描述算法运行时间随输入规模增长的趋势。常见记号：

O(g(n)) = \{f(n) \mid \exists c > 0, n_0 > 0, \forall n \ge n_0, 0 \le f(n) \le c g(n)\}

直观理解：当 n 足够大时，f(n) 不会比 g(n) 增长得更快一个数量级。

常见增长速度：

O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

1.3.1 循环复杂度#

1
for (int i = 0; i < n; i++) {
2
    work();
3
}

执行 n 次，所以是 $O(n)$ 。

1
for (int i = 0; i < n; i++) {
2
    for (int j = 0; j < n; j++) {
3
        work();
4
    }
5
}

执行 $n^2$ 次，所以是 $O(n^2)$ 。

1
for (int i = 1; i <= n; i *= 2) {
2
    work();
3
}

i 每次翻倍，循环次数为 $\lfloor \log_2 n \rfloor + 1$ ，所以是 $O(\log n)$ 。

1.3.2 求和估算#

常见求和：

\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = O(n^2)

\sum_{i=1}^{n} \log i = O(n\log n)

\sum_{k=0}^{\log n} 2^k = 2^{\log n + 1}-1 = O(n)

1.4 空间复杂度#

空间复杂度关注额外使用的内存。

原数组输入不一定算额外空间。
新开一个长度为 n 的数组是 $O(n)$ 。
递归调用栈也算空间。
图的邻接表通常是 $O(n+m)$ 。

例如归并排序需要辅助数组，因此空间复杂度是 $O(n)$ ；快速排序平均递归深度是 $O(\log n)$ ，最坏是 $O(n)$ 。

1.5 数据范围反推复杂度#

数据规模	常见可接受复杂度	典型算法
$n \le 10$	$O(n!)$ 、 $O(2^n)$	全排列、状态压缩
$n \le 20$	$O(n2^n)$	TSP、子集 DP
$n \le 100$	$O(n^3)$	Floyd、区间 DP
$n \le 1000$	$O(n^2)$	普通 DP、二重枚举
$n \le 10^5$	$O(n\log n)$	排序、堆、线段树
$n \le 10^6$	$O(n)$	前缀和、线性筛
$n \ge 10^9$	$O(\log n)$ 或 $O(1)$	二分、数学公式

这张表不是绝对的。实际还要考虑常数、语言、内存、测试机速度。

1.6 递归式与主定理#

分治算法经常写成递归式：

T(n) = aT\left(\frac{n}{b}\right) + f(n)

含义：把规模 n 的问题分成 a 个规模为 $n/b$ 的子问题，再花 $f(n)$ 合并。

主定理提供快速判断：

如果 $f(n) = O(n^{\log_b a - \epsilon})$ ，则 $T(n)=\Theta(n^{\log_b a})$ 。
如果 $f(n) = \Theta(n^{\log_b a}\log^k n)$ ，则 $T(n)=\Theta(n^{\log_b a}\log^{k+1}n)$ 。
如果 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 且满足正则条件，则 $T(n)=\Theta(f(n))$ 。

归并排序：

T(n)=2T(n/2)+O(n)=O(n\log n)

二分查找：

T(n)=T(n/2)+O(1)=O(\log n)

1.7 正确性证明#

算法不能只靠样例通过。常见证明方式：

1.7.1 循环不变量#

循环不变量是每轮循环前后都成立的命题。

证明步骤：

初始化：第一次循环前成立。
保持：如果某轮前成立，则该轮后仍成立。
终止：循环结束时，不变量推出答案正确。

1.7.2 数学归纳法#

适合递归和 DP。

证明 $P(n)$ ：

基础情况成立。
假设 $P(1), P(2), \ldots, P(n-1)$ 成立。
证明 $P(n)$ 成立。

1.7.3 交换论证#

适合贪心。证明任意最优解都可以通过交换变成包含贪心选择的最优解。

1.8 易错点#

只看样例，不看数据范围。
把 $O(n^2)$ 写成“能过”却忽略 $n=10^5$ 。
忘记递归栈空间。
把平均复杂度当成最坏复杂度。
用哈希时忘记最坏情况下可能退化。
证明里只描述做法，没有说明为什么不会漏解。

1.9 练习#

分析双重循环中 $j < i$ 的复杂度。
写出归并排序的递归式并求解。
对 $n=10^5$ ，判断 $O(n^2)$ 是否可行，并说明理由。
为“数组求最大值”写循环不变量证明。
为一个二分查找模板写出循环不变量。

ACM/OI 扩展：复杂度、模板风格与竞赛工作流#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. OI/ACM 代码骨架#

竞赛代码首先追求稳定和可调试。模板应短、熟、少依赖。建议把所有全局常量、类型别名、调试宏固定下来，减少现场思考成本。

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
const int INF = 0x3f3f3f3f;
5
const ll LINF = (1LL << 62);
6

7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
    int T = 1;
11
    // cin >> T;
12
    while (T--) {
13
        // solve();
14
    }
15
    return 0;
16
}

要点：

long long 用于计数、路径长度、组合数中间结果。
const int N 要按最大数据范围多开 5 到 10。
多组数据要清空图、数组、标记和全局答案。

常见坑：

忘记关闭同步导致输入慢。
多组数据沿用上一组的全局状态。
用 int 存储 $10^5 imes 10^5$ 级别的答案。

训练题型：

把已有题解统一改成固定代码骨架。
为模板添加本地调试宏 dbg(x)。

2. 常见复杂度估算表#

OI/ACM 中读到数据范围后，第一反应应是复杂度上限。

数据范围	首选方向	常见算法
$n le 20$	指数级	状压 DP、Meet-in-the-middle
$n le 500$	三次方	Floyd、区间 DP、费用流小数据
$n le 5000$	平方级	LIS、普通 DP、二分图匹配
$n le 2 imes10^5$	线性或 $nlog n$	排序、树状数组、线段树、Dijkstra
$n le 10^6$	线性	前缀和、双指针、筛法
$n le 10^9$	对数或数学	二分、快速幂、数论公式

要点：

复杂度判断只给方向，常数仍然重要。
图论题要同时看点数 n 和边数 m。
DP 要看状态数和每个状态转移次数。

3. 递归式速查#

T(n)=T(n/2)+O(1)=O(\log n)

T(n)=2T(n/2)+O(n)=O(n\log n)

T(n)=2T(n/2)+O(1)=O(n)

T(n)=T(n-1)+O(n)=O(n^2)

要点：

二分、快速幂通常是第一类。
归并排序是第二类。
线段树建树是第三类。
朴素递归如果没有记忆化，常常指数爆炸。

4. 对拍最小框架#

当贪心或复杂 DP 不确定时，先写暴力解，再随机生成小数据对拍。

1
for (int tc = 1; tc <= 10000; ++tc) {
2
    auto data = gen(tc);
3
    auto a = brute(data);
4
    auto b = solve(data);
5
    if (a != b) {
6
        cerr << "Wrong on seed " << tc << "\n";
7
        print(data);
8
        cerr << a << " " << b << "\n";
9
        break;
10
    }
11
}

要点：

暴力解只需要正确，不需要快。
随机数据要覆盖极小值、重复值、有序、逆序。
反例一旦出现，应保存为固定测试。

常见坑：

生成器没有覆盖关键边界。
brute 自己也写错却没有手测。

5. 复杂度证明写法#

题解中常用“每个元素最多入栈一次出栈一次”证明线性复杂度。对于树状数组、线段树，要说明每次操作访问 $O(\log n)$ 个节点。

要点：

写复杂度时分清预处理和单次查询。
如果使用排序，总复杂度至少有 $O(n\log n)$ 。
空间复杂度要包含图边、DP 表和递归栈。

训练题型：

任选一个单调栈题，写出线性复杂度证明。
任选一个线段树题，写出建树、修改、查询复杂度。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

ACM/OI 题型识别速查#

看到“第 k 小 / 排名 / 逆序对”#

优先考虑排序、离散化、树状数组、线段树、主席树、整体二分。

静态区间第 k 小：主席树。
动态区间第 k 小：树套树或整体二分。
逆序对：离散化 + 树状数组。

看到“路径 / 连通 / 最短 / 环”#

优先建图。点是什么、边是什么、边权是什么，是图论题的核心。

无权最短路：BFS。
非负权最短路：Dijkstra。
负边或差分约束：Bellman-Ford/SPFA。
连通性动态合并：并查集。

看到“区间修改 / 区间查询”#

优先考虑差分、树状数组、线段树、分块。

只离线区间加最后查询：差分。
单点改 + 前缀/区间和：树状数组。
区间改 + 区间查询：线段树。
操作复杂但可接受根号：分块。

看到“子序列 / 最优值 / 方案数”#

优先考虑 DP。先写状态含义，再看能否优化。

状态数量决定复杂度。
转移枚举过多时考虑前缀最值、单调队列、斜率优化。
计数 DP 注意取模和重复计数。

看到“字符串匹配 / 多模式 / 回文”#

优先考虑 KMP/Z、Trie、AC 自动机、Manacher、Hash、后缀数组。

单模式匹配：KMP/Z。
多模式匹配：AC 自动机。
回文半径：Manacher。
子串快速比较：Hash 或后缀数组。

赛前模板检查#

模板必须满足“能默写、能解释、能测试”。

每个模板至少有一个最小输入。
每个模板知道 0-index/1-index 版本。
每个模板知道不适用条件。

高频模板训练卡#

这一组训练卡用于把“01_算法学习总览与复杂度分析”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：复杂度估算#

题目信号：题面出现复杂度估算相关约束或需要解释算法为何能过。
优先模板：先写出复杂度估算的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道复杂度估算题写出暴力、优化和复杂度说明。

卡 2：循环不变量证明#

题目信号：题面出现循环不变量证明相关约束或需要解释算法为何能过。
优先模板：先写出循环不变量证明的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道循环不变量证明题写出暴力、优化和复杂度说明。

卡 3：递归树分析#

题目信号：题面出现递归树分析相关约束或需要解释算法为何能过。
优先模板：先写出递归树分析的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道递归树分析题写出暴力、优化和复杂度说明。

卡 4：主定理#

题目信号：题面出现主定理相关约束或需要解释算法为何能过。
优先模板：先写出主定理的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道主定理题写出暴力、优化和复杂度说明。

卡 5：均摊分析#

题目信号：题面出现均摊分析相关约束或需要解释算法为何能过。
优先模板：先写出均摊分析的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道均摊分析题写出暴力、优化和复杂度说明。

卡 6：随机对拍#

题目信号：题面出现随机对拍相关约束或需要解释算法为何能过。
优先模板：先写出随机对拍的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道随机对拍题写出暴力、优化和复杂度说明。

卡 7：暴力基线#

题目信号：题面出现暴力基线相关约束或需要解释算法为何能过。
优先模板：先写出暴力基线的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道暴力基线题写出暴力、优化和复杂度说明。

卡 8：边界构造#

题目信号：题面出现边界构造相关约束或需要解释算法为何能过。
优先模板：先写出边界构造的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道边界构造题写出暴力、优化和复杂度说明。

卡 9：多组数据清空#

题目信号：题面出现多组数据清空相关约束或需要解释算法为何能过。
优先模板：先写出多组数据清空的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道多组数据清空题写出暴力、优化和复杂度说明。

卡 10：long long 判断#

题目信号：题面出现 long long 判断相关约束或需要解释算法为何能过。
优先模板：先写出 long long 判断的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道 long long 判断题写出暴力、优化和复杂度说明。

卡 11：读题建模#

题目信号：题面出现读题建模相关约束或需要解释算法为何能过。
优先模板：先写出读题建模的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道读题建模题写出暴力、优化和复杂度说明。

卡 12：数据范围反推#

题目信号：题面出现数据范围反推相关约束或需要解释算法为何能过。
优先模板：先写出数据范围反推的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道数据范围反推题写出暴力、优化和复杂度说明。

卡 13：离线与在线判断#

题目信号：题面出现离线与在线判断相关约束或需要解释算法为何能过。
优先模板：先写出离线与在线判断的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道离线与在线判断题写出暴力、优化和复杂度说明。

卡 14：预处理换查询#

题目信号：题面出现预处理换查询相关约束或需要解释算法为何能过。
优先模板：先写出预处理换查询的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道预处理换查询题写出暴力、优化和复杂度说明。

卡 15：空间换时间#

题目信号：题面出现空间换时间相关约束或需要解释算法为何能过。
优先模板：先写出空间换时间的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道空间换时间题写出暴力、优化和复杂度说明。

卡 16：单调性识别#

题目信号：题面出现单调性识别相关约束或需要解释算法为何能过。
优先模板：先写出单调性识别的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道单调性识别题写出暴力、优化和复杂度说明。

卡 17：最优子结构识别#

题目信号：题面出现最优子结构识别相关约束或需要解释算法为何能过。
优先模板：先写出最优子结构识别的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道最优子结构识别题写出暴力、优化和复杂度说明。

卡 18：图模型识别#

题目信号：题面出现图模型识别相关约束或需要解释算法为何能过。
优先模板：先写出图模型识别的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道图模型识别题写出暴力、优化和复杂度说明。

卡 19：区间模型识别#

题目信号：题面出现区间模型识别相关约束或需要解释算法为何能过。
优先模板：先写出区间模型识别的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道区间模型识别题写出暴力、优化和复杂度说明。

卡 20：字符串模型识别#

题目信号：题面出现字符串模型识别相关约束或需要解释算法为何能过。
优先模板：先写出字符串模型识别的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道字符串模型识别题写出暴力、优化和复杂度说明。

卡 21：数学模型识别#

题目信号：题面出现数学模型识别相关约束或需要解释算法为何能过。
优先模板：先写出数学模型识别的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道数学模型识别题写出暴力、优化和复杂度说明。

卡 22：模板可信度检查#

题目信号：题面出现模板可信度检查相关约束或需要解释算法为何能过。
优先模板：先写出模板可信度检查的最小模型，再决定是否上模板。
核心不变量：所有估算都围绕输入规模 n、边数 m、值域 V、询问数 q 展开。
复杂度目标：目标复杂度必须由数据范围倒推，不能只凭感觉。
不适用场景：样例很小但隐藏数据很大时不能按样例复杂度写。
实现检查：检查变量范围、数组大小、递归深度、预处理是否重复。
边界样例：n=0/1、最大 n、全相等、严格递增、严格递减。
训练题型：把一道模板可信度检查题写出暴力、优化和复杂度说明。

本章赛前默写任务#

01_算法学习总览与复杂度分析：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：复杂度估算#

识别信号：题面出现与“复杂度估算”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“复杂度估算”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：循环不变量#

识别信号：题面出现与“循环不变量”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“循环不变量”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：数学归纳证明#

识别信号：题面出现与“数学归纳证明”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“数学归纳证明”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：递归树#

识别信号：题面出现与“递归树”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“递归树”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：主定理#

识别信号：题面出现与“主定理”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“主定理”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：均摊分析#

识别信号：题面出现与“均摊分析”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“均摊分析”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：数据范围反推#

识别信号：题面出现与“数据范围反推”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“数据范围反推”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：暴力基线#

识别信号：题面出现与“暴力基线”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“暴力基线”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：随机对拍#

识别信号：题面出现与“随机对拍”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“随机对拍”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：边界构造#

识别信号：题面出现与“边界构造”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“边界构造”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：空间复杂度#

识别信号：题面出现与“空间复杂度”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“空间复杂度”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：多组数据清空#

识别信号：题面出现与“多组数据清空”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“多组数据清空”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：long long 溢出#

识别信号：题面出现与“long long 溢出”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“long long 溢出”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：离线处理#

识别信号：题面出现与“离线处理”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“离线处理”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：预处理优化#

识别信号：题面出现与“预处理优化”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“预处理优化”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：模型识别#

识别信号：题面出现与“模型识别”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“模型识别”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：复杂度估算#

识别信号：题面出现与“复杂度估算”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“复杂度估算”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：循环不变量#

识别信号：题面出现与“循环不变量”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“循环不变量”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：数学归纳证明#

识别信号：题面出现与“数学归纳证明”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“数学归纳证明”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

如果這篇文章對你有幫助，歡迎分享給更多人！

算法学习总览与复杂度分析

https://lemusakuya.com/posts/study-notes/algorithm/01_算法学习总览与复杂度分析/

作者

レム・咲く夜

發布於

2026-06-03

許可協議

部分資訊可能已經過時

相關文章智能推薦

Algorithm 《算法》学习总览与学习路线

2

数学算法与组合计数

Algorithm 《算法》学习笔记：10_数学算法与组合计数

3

字符串算法

Algorithm 《算法》学习笔记：09_字符串算法

4

树与图论基础

Algorithm 《算法》学习笔记：07_树与图论基础

5

基础数据结构与语言工具

Algorithm 《算法》学习笔记：02_基础数据结构与语言工具

隨機文章隨機推薦

1

模型解释部署压缩工程实战

Neural Networks 2026-06-03

2

数字图像处理（Digital Image Processing）完全学习手册

Digital Image Processing 2026-06-03

3

Final Exam

MCU Development 2026-06-14

4

图像复原与重建

Digital Image Processing 2026-04-27

5

AD Rush

Android Development 2026-06-14

ぬくぬくうちにゃ💤

第 1 章 算法学习总览与复杂度分析#

1.1 学习目标#

1.2 什么是算法#

1.3 时间复杂度#

1.3.1 循环复杂度#

1.3.2 求和估算#

1.4 空间复杂度#

1.5 数据范围反推复杂度#

1.6 递归式与主定理#

1.7 正确性证明#

1.7.1 循环不变量#

1.7.2 数学归纳法#

1.7.3 交换论证#

1.8 易错点#

1.9 练习#

ACM/OI 扩展：复杂度、模板风格与竞赛工作流#

1. OI/ACM 代码骨架#

2. 常见复杂度估算表#

3. 递归式速查#

4. 对拍最小框架#

5. 复杂度证明写法#

本章模板背诵清单#

ACM/OI 题型识别速查#

看到“第 k 小 / 排名 / 逆序对”#

看到“路径 / 连通 / 最短 / 环”#

看到“区间修改 / 区间查询”#

看到“子序列 / 最优值 / 方案数”#

看到“字符串匹配 / 多模式 / 回文”#

赛前模板检查#

高频模板训练卡#

卡 1：复杂度估算#

卡 2：循环不变量证明#

卡 3：递归树分析#

卡 4：主定理#

卡 5：均摊分析#

卡 6：随机对拍#

卡 7：暴力基线#

卡 8：边界构造#

卡 9：多组数据清空#

卡 10：long long 判断#

卡 11：读题建模#

卡 12：数据范围反推#

卡 13：离线与在线判断#

卡 14：预处理换查询#

卡 15：空间换时间#

卡 16：单调性识别#

卡 17：最优子结构识别#

卡 18：图模型识别#

卡 19：区间模型识别#

卡 20：字符串模型识别#

卡 21：数学模型识别#

卡 22：模板可信度检查#

本章赛前默写任务#

01_算法学习总览与复杂度分析：详细训练清单#

训练点 1：复杂度估算#

训练点 2：循环不变量#

训练点 3：数学归纳证明#

训练点 4：递归树#

训练点 5：主定理#

训练点 6：均摊分析#

训练点 7：数据范围反推#

训练点 8：暴力基线#

训练点 9：随机对拍#

训练点 10：边界构造#

训练点 11：空间复杂度#

训练点 12：多组数据清空#

训练点 13：long long 溢出#

训练点 14：离线处理#

训练点 15：预处理优化#

训练点 16：模型识别#

训练点 17：复杂度估算#

训练点 18：循环不变量#

训练点 19：数学归纳证明#

目錄

第 1 章算法学习总览与复杂度分析#