什么是算法？怎么判断一个算法的好坏？在深入学习具体算法之前，先建立起这两个最基本的认识。
算法是解决某类问题的一套明确的步骤。它必须满足三个条件：每一步都足够具体（不能模糊），步骤有限（不能无限执行），最终有结果（不能没有输出）。
你每天都在用算法：查字典时从中间翻开缩小范围，这是二分查找；整理扑克牌时把新摸的牌插到合适位置，这是插入排序；导航时选最短路，这是最短路径算法。
在竞赛中，算法的核心问题只有两个：能不能做到，以及快不快、省不省内存。
问题：给你一个 1 到 n 的整数，求它们的总和。
这个问题有两种做法，效率天壤之别：
| 1 | int sum = 0; |
| 2 | for (int i = 1; i <= n; i++) |
| 3 | sum += i; // 执行 n 次加法 |
| 1 | int sum = n * (n + 1) / 2; // 执行 1 次乘法、1 次加法、1 次除法 |
当 n = 10 时，两种方法都很快，看不出差别。但当 n = 1,000,000,000（十亿）时，方法一需要执行十亿次加法——耗时约几秒；方法二仍然只需要 3 次运算，瞬间出结果。
这就是算法好坏的核心体现：随着问题规模增大，不同算法的速度差距会急剧拉开。
我们用时间复杂度来描述算法的速度，写作 O(...)（读作"大O"）。它表示随着数据规模 n 增大，算法所需操作次数的增长趋势。
注意：时间复杂度不是精确的运行时间，而是一种量级估算——我们只关心最主要的增长因素，忽略常数和低阶项。
O(1) 最理想（常数时间），O(n²) 增长最快。怎么计算时间复杂度？只需要数"代码里最深层的循环大约执行了多少次"：
| 1 | // O(1)：没有循环，操作次数固定 |
| 2 | int sum = n * (n + 1) / 2; |
| 3 | |
| 4 | // O(n)：一层循环，执行 n 次 |
| 5 | for (int i = 0; i < n; i++) { ... } |
| 6 | |
| 7 | // O(n²)：两层嵌套循环，执行 n×n 次 |
| 8 | for (int i = 0; i < n; i++) |
| 9 | for (int j = 0; j < n; j++) { ... } |
| 10 | |
| 11 | // O(log n)：每次把范围缩小一半（如二分查找） |
| 12 | while (lo <= hi) { |
| 13 | int mid = (lo + hi) / 2; |
| 14 | if (...) lo = mid + 1; else hi = mid - 1; |
| 15 | } // 每次范围减半，最多执行 log₂n 次 |
除了速度，算法还需要内存。空间复杂度描述算法需要多少额外内存，同样用 O(...) 表示。
| 复杂度 | 名称 | 典型场景 | n=10⁶ 时的操作次数 |
|---|---|---|---|
| O(1) | 常数时间 | 数组下标访问、数学公式 | 1 次 |
| O(log n) | 对数时间 | 二分查找、倍增 | 约 20 次 |
| O(√n) | 平方根时间 | 质数判断、分块 | 约 1000 次 |
| O(n) | 线性时间 | 一次遍历、前缀和 | 100 万次 |
| O(n log n) | 线性对数 | sort、归并排序 | 约 2000 万次 |
| O(n²) | 平方时间 | 冒泡排序、暴力枚举对 | 1 万亿次 ❌ |
| O(2ⁿ) | 指数时间 | 枚举所有子集（n 很小时） | 远超宇宙原子数 ❌ |
竞赛中，题目通常会给出数据范围（如 1 ≤ n ≤ 10⁵）。拿到题目后，先看数据范围，就能大致判断需要哪个量级的算法：
本算法文档共 18 个模块，按难度和依赖关系由浅入深排列。建议按顺序学习，每个模块都配有原理讲解、代码实现和执行过程图示。