元素同属一个范围，但无序、无关联。
例：购物车里的商品
元素首尾相接，严格的一对一顺序。
例：排队、链表、数组
一对多的层级关系，严谨的分支体系。
例：公司组织架构、文件系统
多对多的网状关系，任意节点皆可相连。
例：互联网、神经网络、交通图
int n = 10000;
x = n + 1; // 无论n多大，这行只执行一次
* **$O(n)$ 线性阶**：一层循环。
for(int i=0; i
* **$O(n^2)$ 平方阶**：双层嵌套循环。
for(int i=0; i
* **$O(\log n)$ 对数阶**：每次循环，数据量都砍半（如二分查找）。
while(n > 1) {
n = n / 2; // 1024 -> 512 -> 256 ... 10次就到了
}
===== 第三部分：五大常用算法思想详解 =====
这是算法的灵魂，掌握这些思想比背诵代码更重要。
==== 1. 穷举法 (Brute Force) ====
* **别名**：暴力破解法。
* **核心**：列出所有可能的情况，逐一验证。
* **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。
* **缺点**：效率极低。
* **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。
==== 2. 分治法 (Divide and Conquer) ====
* **核心口诀**：**分而治之，各个击破**。
* **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。
* **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。
大问题 (排序 8 个数)
↓ 拆分 (Divide)
子问题 A
子问题 B
↓ 递归解决 (Conquer)
A1A2
|
B1B2
↑ 合并结果 (Merge)
==== 3. 动态规划 (Dynamic Programming, DP) ====
* **核心**：**历史记录**。通过空间换时间。
* **原理**：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是**重叠**的。为了避免重复计算，DP 会把每个子问题的结果**存进一张表**里。
* **案例：斐波那契数列** (1, 1, 2, 3, 5, 8...)
* 求第 5 个数：$F(5) = F(4) + F(3)$
* 求 $F(4)$ 时需要算 $F(3) + F(2)$。
* **注意**：$F(3)$ 被计算了两次！如果是递归，$n$ 很大时重复计算量是指数级的。
* **DP做法**：算完 $F(3)$ 就把它记在本子上，下次直接看本子。
普通递归 (傻算)
f(5) 需要算 f(4) 和 f(3)
f(4) 需要算 f(3) 和 f(2)
f(3) 被重复计算了！
动态规划 (记账)
算过 f(3) 吗？
算过 -> 直接查表
没算 -> 算出并填表
f(1)
f(2)
f(3)
...
==== 4. 贪心算法 (Greedy) ====
* **核心**：**活在当下**。
* **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。
* **案例：找零钱**
* 问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。
* 贪心策略：优先用面值最大的。
* 步骤：
* 66 < 100，跳过。
* 66 >= 50，**给一张 50**。剩 16。
* 16 < 20，跳过。
* 16 >= 10，**给一张 10**。剩 6。
* 6 >= 5，**给一张 5**。剩 1。
* **给一张 1**。结束。
* **局限**：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。
==== 5. 回溯法 (Backtracking) ====
* **核心**：**试错与回退**。
* **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。
* **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。
* **典型应用**：走迷宫、八皇后问题、数独。
X 死路
√ 通路
先试上方(红)，走不通 -> 回溯 -> 改走右方(绿)
===== 总结：如何选择算法？ =====
| 场景特点 | 推荐策略 | 核心思想 |
| 问题可拆分，子问题独立 | **分治法** | 大事化小 |
| 问题可拆分，子问题重叠 | **动态规划** | 拒绝健忘，查表 |
| 需要快速找到一个可行解 | **贪心算法** | 目光短浅，先拿再说 |
| 需要遍历所有解或路径 | **回溯法** | 不撞南墙不回头 |
| 没有任何规律 | **穷举法** | 暴力出奇迹 |