第 2 章 · 02 算法基础(对应 docs/basic/)

第 2 章 · 02 算法基础(对应 docs/basic/)

本节定位:对应 OI Wiki docs/basic/。难度:入门。前置依赖:本章 01 节(C++ 基础)。

⚠️ 注意:复杂度分析是算法竞赛的根基。不会分析复杂度,等于不会做题——因为你看完题目不知道能用什么算法。这一节里复杂度分析比任何具体算法都重要。

知识地图

docs/basic/ 页面地图

OI Wiki 的 docs/basic/ 目录是算法基础,覆盖从复杂度到基础算法范式。按学习顺序:

复杂度与分治

• docs/basic/complexity.md:时间复杂度与空间复杂度(大 O 记号),这是全站最重要的入门页之一。
• docs/basic/amortized-analysis.md:均摊分析(高端内容,可后置)。
• docs/basic/divide-and-conquer.md:递归 & 分治。
• docs/basic/binary-lifting.md:倍增(数据结构/图论的基础工具)。

基础算法范式

• docs/basic/enumerate.md:枚举(暴力,看似简单但有时是正解)。
• docs/basic/simulate.md:模拟(按题意一步步实现,考验代码能力)。
• docs/basic/greedy.md:贪心。
• docs/basic/binary.md:二分查找与二分答案(高频考点!)。

排序

• docs/basic/sort-intro.md:排序总览。
• docs/basic/stl-sort.md:STL sort(实际最常用)。
• 各种排序算法分页:bubble-sort.md / selection-sort.md / insertion-sort.md / merge-sort.md / quick-sort.md / heap-sort.md / bucket-sort.md / counting-sort.md / radix-sort.md / shell-sort.md / tim-sort.md / tournament-sort.md。
• docs/basic/use-of-sort.md:排序的应用(自定义排序、结构体排序)。

前缀和与差分

• docs/basic/prefix-sum.md:前缀和与差分(O(1) 区间修改/查询的高频技巧)。

复杂度是竞赛核心

看数据范围估算法,这是竞赛第一直觉。务必背下来:

1 秒内,一般认为能跑 10^8 次简单运算(常数因子小的)。

💡 学习提示:这张表是竞赛第一直觉。读题第一眼先看 n,立刻知道能用什么复杂度的算法,再往这个复杂度的算法里套。比如 n = 10^5、时限 1 秒,直接锁定 O(n \log n),那就只剩排序、二分、线段树、set/map 这几样可选——大大缩小思考范围。养成这个反射,做题速度提升一档。

主定理

docs/basic/complexity.md 里有主定理(Master Theorem)用于分析分治递归 T(n) = aT(n/b) + f(n) 的复杂度。二分是 T(n) = T(n/2) + O(1) = O(\log n);归并排序是 T(n) = 2T(n/2) + O(n) = O(n \log n)。初学阶段会用查表即可,不必死记证明。

学习建议

复杂度分析务必扎实

💡 学习提示:docs/basic/complexity.md 这页建议读 3 遍。第一遍建立概念,第二遍配合题目验证,第三遍能反向"由数据范围猜算法"。这是判断你"懂不懂竞赛"的分水岭。

二分是高频考点

docs/basic/binary.md 包括二分查找(在有序数组里找值)和二分答案(把"求最大值"转化为"判定 mid 是否可行"再二分)。二分答案在 NOIp/CSP 里几乎是必考题型。

二分边界极易错:开闭区间、l <= r 还是 l < r、mid = (l+r)/2 还是 (l+r+1)/2、l = mid 还是 r = mid。Wiki 页面有标准写法,固定一种写法练熟(推荐 l < r + mid = (l+r+1)/2 配 l = mid 这种"找最大"写法)。

贪心需要证明

docs/basic/greedy.md:贪心看似"直觉",但竞赛贪心题必须证明正确性(交换法/反证法/拟阵)。靠直觉蒙贪心策略,容易过样例但 WA。Wiki 页面有经典贪心模型(区间调度/Huffman 编码等)。

排序:会用 STL sort 即可

排序算法原理(快排/归并/堆排)要理解,但实际写题直接用 sort(docs/basic/stl-sort.md)。重点掌握自定义比较函数:

sort(a, a + n);                          // 默认升序
sort(a, a + n, greater<int>());          // 降序
sort(a, a + n, [](int x, int y){ return x > y; });  // Lambda 降序
​

计数排序(counting-sort.md)在值域小时比 sort 快,关键技巧。

前缀和差分

docs/basic/prefix-sum.md:前缀和把"区间求和"从 O(n) 降到 O(1);差分把"区间加"从 O(n) 降到 O(1)。两者是后续二维前缀和、树状数组、线段树的基础。

// 前缀和:s[i] = a[1]+...+a[i]; 区间 [l,r] 的和 = s[r]-s[l-1]
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
// 差分:d[l]+=v, d[r+1]-=v; 之后做一次前缀和还原
d[l]+=v; d[r+1]-=v;
​

二维前缀和(子矩阵求和)和二维差分是 CSP 常考内容,公式要记牢。高阶一点,树状数组、线段树本质都是"前缀和 + 高效修改"的延伸。

常见误区

⚠️ 注意:

1. 不会估算复杂度就动手:读题第一步是看数据范围,定复杂度上限,再选算法。不看范围直接写,多半 TLE。
2. 二分边界乱试:while(l <= r) / while(l < r) / l = mid + 1 / l = mid 混用导致死循环或漏解。固定一套写法。
3. 贪心不证明:感觉对就写,结果反例一堆。至少在脑子里举几个反例。
4. 多测不清空:memset 或重新初始化数组,前一组数据污染后一组。
5. 混淆 O(n \log n) 与 O(n^2):n = 10^5 时前者 0.01 秒,后者 10 秒(超时)。
6. 前缀和数组下标从 0 还是 1 不统一:推荐统一从 1 开始,这样 s[r] - s[l-1] 边界好处理;从 0 开始容易在 s[-1] 出错。
7. 模拟题代码乱:模拟题(如机器人移动、操作序列)代码长,务必先理清状态、用清晰的变量名、必要时写注释,否则调试到崩溃。
8. 递归边界忘写:递归必须有终止条件,否则栈溢出 RE。docs/basic/divide-and-conquer.md 的分治代码都要有 if(l==r) return; 这类边界。

💡 学习提示:这一节(算法基础)是后续所有章节的地基。复杂度分析、二分、贪心、前缀和差分这些"小工具",在第 3-7 章的高级算法里反复用到。这里学不扎实,后面会处处卡壳。宁可在这节多花时间,也不要急于进数据结构。

本节要点

1. docs/basic/ 覆盖:复杂度/枚举/模拟/递归分治/贪心/二分/排序/前缀和差分。
2. 复杂度分析是竞赛根基,务必能"由数据范围反推算法复杂度",背熟范围-复杂度对照表。
3. 二分(查找 + 答案)是高频考点,边界极易错,固定一套写法练熟。
4. 贪心必须证明,排序实战用 STL sort,前缀和差分是后续数据结构基础。
5. 主定理用于分治递归复杂度分析,会用即可。