全书知识地图

第一章：二分查找与大O表示法

1.1 什么是算法？

算法就是完成某个任务的一组步骤说明书。就像做菜的菜谱，告诉你第一步做什么、第二步做什么，最终得到结果。
好的算法能让你的程序快到惊人：同样的问题，差的算法要40亿步，好的算法只要32步！

1.2 二分查找

问题引入

想象你在查字典找"oxygen"这个单词。你会怎么找？

• 笨办法：从第1页翻到第2页、第3页……一页一页找过去
• 聪明办法：直接翻到中间，判断"oxygen"在前半段还是后半段，然后只在那半段里继续找
  聪明办法就是二分查找的核心思想！

猜数字游戏演示

我心里想一个1到100之间的数，你来猜，我告诉你"太大"、“太小"或"猜中了”。
笨方法（简单查找）：

猜1 -> 太小
猜2 -> 太小
猜3 -> 太小
...（最坏情况要猜100次）

聪明方法（二分查找）：

猜50 -> 太小  (排除了1-50，剩51-100)
猜75 -> 太大  (排除了75-100，剩51-74)
猜63 -> 太小  (排除了51-63，剩64-74)
猜69 -> 猜中！

只用了4步！最坏情况也只需要7步（因为 $\lceil {\log }_{2}100\rceil =7$）。

二分查找的关键前提

列表必须是有序排列的！
就像字典里的单词是按字母顺序排的，电话本里的名字是按姓名顺序排的，二分查找才能判断"在左边还是右边"。

二分查找的执行流程

对数是什么？

在理解二分查找的效率之前，先复习一下对数：
对数是指数的反运算：
$${\log }_{2}8=3\text{因为}{2}^3=8$$
$${\log }_{2}1024=10\text{因为}{2}^{10}=1024$$
通俗理解：${\log }_{2}n$ 就是"把 $n$ 连续除以2，需要除几次才能得到1"。

列表大小 $n$	简单查找（最坏）	二分查找（最坏）
100	100步	7步
1,024	1,024步	10步
4亿	4亿步	32步

---

C++ 完整实现

// 二分查找完整实现
// 在一个有序数组中查找目标值，返回其下标，找不到返回-1
#include <iostream>
#include <vector>
// 二分查找函数
// 参数：
//   arr  - 已排序的整数数组（必须有序！）
//   item - 要查找的目标值
// 返回值：
//   找到返回目标值所在的下标（从0开始）
//   找不到返回 -1
int binarySearch(const std::vector<int>& arr, int item) {
    // low 和 high 定义当前搜索范围的左右边界
    int low = 0;
    int high = (int)arr.size() - 1;
    // 当搜索范围还有元素时，持续循环
    while (low <= high) {
        // 计算中间位置
        // 注意：用 low + (high - low) / 2 而不是 (low + high) / 2
        // 是为了防止 low+high 整数溢出
        int mid = low + (high - low) / 2;
        // 取中间元素
        int guess = arr[mid];
        // 判断猜测结果
        if (guess == item) {
            return mid;        // 猜中了！返回下标
        } else if (guess > item) {
            high = mid - 1;    // 猜大了，去左半边找（缩小右边界）
        } else {
            low = mid + 1;     // 猜小了，去右半边找（扩大左边界）
        }
    }
    // 循环结束还没找到，说明目标不在列表中
    return -1;
}
int main() {
    // 测试1：目标在列表中
    std::vector<int> myList = {1, 3, 5, 7, 9};
    std::cout << "列表内容：1, 3, 5, 7, 9\n\n";
    int result1 = binarySearch(myList, 3);
    if (result1 != -1) {
        std::cout << "查找 3：找到了，下标为 " << result1 << "\n";
        // 下标1 对应的是第二个元素（下标从0开始）
    }
    // 测试2：目标不在列表中
    int result2 = binarySearch(myList, -1);
    if (result2 == -1) {
        std::cout << "查找 -1：没有找到（返回-1）\n";
    }
    // 测试3：展示二分查找的步骤效率
    // 对于240000个单词的字典，最多需要多少步？
    // log2(240000) ≈ 17.87，所以最多18步
    std::cout << "\n对于240000个单词的字典：\n";
    std::cout << "  简单查找最坏需要：240000步\n";
    std::cout << "  二分查找最坏需要：约18步\n";
    // 展示不同规模下的查找步数
    std::cout << "\n不同列表规模下的最大查找步数：\n";
    std::cout << "----\n";
    std::cout << "| 列表大小     | 简单查找（步数） | 二分查找（步数） |\n";
    std::cout << "|-|-|-|\n";
    // 计算几个典型规模的对数值
    // log2(n) = ln(n) / ln(2)
    auto log2_steps = [](long long n) -> int {
        int steps = 0;
        while (n > 1) {
            n /= 2;
            steps++;
        }
        return steps;
    };
    long long sizes[] = {100, 1024, 1000000, 1000000000LL};
    for (long long sz : sizes) {
        std::cout << "| " << sz
                  << "       | " << sz
                  << "         | " << log2_steps(sz) << "              |\n";
    }
    std::cout << "----\n";
    return 0;
}

1.3 大O表示法

为什么需要大O？

光知道"二分查找比简单查找快"还不够，我们需要知道快多少，以及随着数据量增大，快的优势会怎么变化。
大O表示法就是用来描述这件事的工具。

大O表示法描述的不是秒数，而是操作次数随数据量增长的规律。

一个反直觉的例子

NASA工程师Bob要在火箭降落时（只有10秒）搜索10亿个元素：
他错误地想：

• 简单查找100个元素要100ms
• 二分查找100个元素要7ms
• 所以二分查找只比简单查找快15倍
• 10亿个元素，二分查找约30ms，简单查找约 $30\times 15=450\text{ms}$，没问题！
  实际情况：
• 二分查找10亿元素：约30ms（${\log }_{2}10^9\approx 30$）
• 简单查找10亿元素：10亿ms = 11天！
  速度增长率完全不同！

大O的几种常见级别

速度由快到慢排列：
O(1)      恒定时间  ■
O(log n)  对数时间  ■■
O(n)      线性时间  ■■■■■
O(n log n)          ■■■■■■■■
O(n²)     平方时间  ■■■■■■■■■■■■■
O(n!)     阶乘时间  ■■■■■■■■■■■■■■■■■■■■■■■(爆炸增长)

用实际操作数对比（每秒10次操作，16个元素）：

算法时间	操作次数(n=16)	操作次数(n=1024)	示例
$O(\log n)$	4次	10次	二分查找
$O(n)$	16次	1024次	简单查找
$O(n\log n)$	64次	10240次	快速排序
$O(n^2)$	256次	1048576次	选择排序
$O(n!)$	20922789888000次	无法计算	旅行商问题

---

大O的核心理解

大O表示最坏情况。
比如简单查找一个电话本，要找的人可能第一页就找到了（最好情况），但大O说的是"万一这个人在最后一页"时需要多少步。
$$\text{简单查找}\to O(n)$$
$$\text{二分查找}\to O(\log n)$$
$$\text{快速排序}\to O(n\log n)$$
$$\text{选择排序}\to O(n^2)$$
$$\text{旅行商问题}\to O(n!)$$

1.4 旅行商问题——最坏的算法

一个销售员要走遍5个城市，找出总距离最短的路线。
暴力方法：列举所有可能的路线顺序，算每条路线的总距离，选最短的。

城市数量	路线总数（排列数）
5	$5!=120$
6	$6!=720$
7	$7!=5040$
100	$100!$（太大了，宇宙结束也算不完）

---

时间复杂度为 $O(n!)$，是已知最差的算法之一，但目前数学上还没有找到更好的精确解法。

第二章：数组、链表与选择排序

2.1 计算机内存是怎么工作的？

把计算机内存想象成一排抽屉，每个抽屉只能放一样东西，每个抽屉都有一个地址编号。

内存示意图：
+------+------+------+------+------+------+------+------+
| 0001 | 0002 | 0003 | 0004 | 0005 | 0006 | 0007 | 0008 |
+------+------+------+------+------+------+------+------+
|  13  |      |  45  |      |      |  72  |      |      |
+------+------+------+------+------+------+------+------+
  存着13        存着45                存着72

当你需要存多个数据时，有两种基本方式：数组和链表。

2.2 数组——连续的抽屉

数组的存储方式

数组要求所有元素紧挨着存放在内存中：

数组存储 [任务1, 任务2, 任务3]：
+------+------+------+------+------+
| 0001 | 0002 | 0003 | 0004 | 0005 |
+------+------+------+------+------+
| 任务1 | 任务2 | 任务3 |  (占) |  (占)|
+------+------+------+------+------+
  ^------数组的三个元素紧挨着------^

数组的问题：加新元素

如果要加第4个任务，但紧挨着的位置已经被别的数据占用了，就必须整体搬家：

搬家前（0004被占用）：
+------+------+------+------+------+
| 任务1 | 任务2 | 任务3 | [被占] |      |
+------+------+------+------+------+
找到新的连续空间，全部移过去：
+------+------+------+------+------+------+
|      |      |      | 任务1 | 任务2 | 任务3 |
+------+------+------+------+------+------+

数组的优势：随机访问

数组知道第一个元素的地址，所有元素紧挨着，所以可以直接计算任意元素的地址：
$$\text{元素地址}=\text{起始地址}+\text{下标}$$
比如数组从地址00开始，第5个元素（下标4）就在地址04，直接跳过去，不用一个个找。

2.3 链表——分散的抽屉

链表的存储方式

链表的每个元素可以存在内存任意位置，但每个元素要额外记录下一个元素在哪里（存储下一个元素的地址）：

链表存储示意：
地址0001        地址0045        地址0203
+----------+   +----------+   +----------+
| 任务1    |   | 任务2    |   | 任务3    |
| 下一个:  |-->| 下一个:  |-->| 下一个:  |--> 空(结束)
| 0045     |   | 0203     |   | null     |
+----------+   +----------+   +----------+

像寻宝游戏一样：第1个告诉你第2个在哪，第2个告诉你第3个在哪……

链表的优势：插入和删除快

添加新元素时，只需把新元素放在任意空位，然后修改上一个元素的"下一个地址"即可：

在任务2后面插入"新任务"（存在地址0789）：
修改前：
任务1(0001) --> 任务2(0045) --> 任务3(0203)
插入新任务到地址0789：
任务1(0001) --> 任务2(0045) --> 新任务(0789) --> 任务3(0203)
只需修改任务2中"下一个"的地址，从0203改为0789！

链表的缺陷：只能顺序访问

想直接跳到第10个元素？不行，必须从第1个开始，一个个跟着地址往下找：

找第3个元素的过程：
从头开始 -> 找到地址0001(任务1) -> 看它说下一个在0045
         -> 找到地址0045(任务2) -> 看它说下一个在0203
         -> 找到地址0203(任务3) -> 这就是第3个！

2.4 数组 vs 链表对比总结

---

操作	数组	链表
读取（随机访问）	$O(1)$，极快	$O(n)$，要从头找
插入	$O(n)$，要移动元素	$O(1)$，改个地址
删除	$O(n)$，要移动元素	$O(1)$，改个地址

---

选择建议：

• 需要频繁读取某个位置的元素 → 用数组
• 需要频繁插入/删除元素 → 用链表

2.5 选择排序

思路

把一堆音乐按播放次数从多到少排序，最简单的方法：

1. 从整个列表找出播放最多的，放到新列表第1位
2. 再从剩余的找出播放最多的，放到新列表第2位
3. 重复直到原列表空了

初始：[Taylor:500, Beyonce:300, Drake:420, Adele:180]
第1轮找最大(500) -> 新列表:[Taylor:500]  剩:[Beyonce:300, Drake:420, Adele:180]
第2轮找最大(420) -> 新列表:[Taylor, Drake]  剩:[Beyonce:300, Adele:180]
第3轮找最大(300) -> 新列表:[Taylor, Drake, Beyonce]  剩:[Adele:180]
第4轮找最大(180) -> 新列表:[Taylor, Drake, Beyonce, Adele]
排序完成！

时间复杂度分析

• 每轮都要检查剩余的所有元素（找最大值）→ 大约 $n$ 次操作
• 一共要找 $n$ 轮
  $$\text{总操作数}=n+(n-1)+(n-2)+\cdots +1=\frac{n(n+1)}{2}\approx \frac{n^2}{2}$$
  在大O表示法中忽略常数系数 $\frac{1}{2}$，所以：
  $$\text{选择排序时间复杂度}=O(n^2)$$

C++ 完整实现

// 选择排序完整实现
// 将数组从小到大排序（升序）
#include <iostream>
#include <vector>
// 在数组 arr 中，从下标 startIndex 开始，找出最小值的下标
// 参数：
//   arr        - 整数数组
//   startIndex - 从哪个位置开始搜索（之前的已经排好了）
// 返回值：最小值所在的下标
int findSmallestIndex(const std::vector<int>& arr, int startIndex) {
    int smallestIndex = startIndex;       // 假设第一个就是最小的
    int smallest = arr[startIndex];       // 记录当前最小值
    // 从 startIndex+1 开始往后逐个比较
    for (int i = startIndex + 1; i < (int)arr.size(); i++) {
        if (arr[i] < smallest) {
            smallest = arr[i];            // 发现更小的，更新最小值
            smallestIndex = i;            // 记住它的下标
        }
    }
    return smallestIndex;
}
// 选择排序主函数
// 每轮从未排序部分找最小值，放到已排序部分末尾
// 参数：arr - 需要排序的数组（就地修改）
void selectionSort(std::vector<int>& arr) {
    int n = (int)arr.size();
    // 外层循环：每次确定一个位置的正确元素
    // i 代表当前要填的位置（0, 1, 2, ...）
    for (int i = 0; i < n - 1; i++) {
        // 在 i 到末尾的范围内，找最小值的下标
        int minIndex = findSmallestIndex(arr, i);
        // 把找到的最小值换到位置 i
        // （用 swap 交换两个元素）
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        // 此时 arr[0..i] 都已经排好序了
    }
}
// 打印数组辅助函数
void printArray(const std::vector<int>& arr, const std::string& label) {
    std::cout << label << ": [";
    for (int i = 0; i < (int)arr.size(); i++) {
        std::cout << arr[i];
        if (i < (int)arr.size() - 1) std::cout << ", ";
    }
    std::cout << "]\n";
}
int main() {
    // 测试1：基本排序
    std::vector<int> arr1 = {5, 3, 6, 2, 10};
    printArray(arr1, "排序前");
    selectionSort(arr1);
    printArray(arr1, "排序后");
    std::cout << "\n";
    // 测试2：展示每一步过程（手动模拟）
    std::vector<int> arr2 = {64, 25, 12, 22, 11};
    std::cout << "逐步演示选择排序过程：\n";
    printArray(arr2, "初始状态");
    int n = (int)arr2.size();
    for (int i = 0; i < n - 1; i++) {
        // 找第i轮最小值
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr2[j] < arr2[minIdx]) {
                minIdx = j;
            }
        }
        // 交换
        int temp = arr2[i];
        arr2[i] = arr2[minIdx];
        arr2[minIdx] = temp;
        std::cout << "第" << (i + 1) << "轮后";
        printArray(arr2, "      ");
    }
    std::cout << "\n";
    // 展示时间复杂度对比
    std::cout << "选择排序时间复杂度分析：\n";
    std::cout << "----\n";
    std::cout << "| 数组大小n | 操作次数(约n²/2) | 大O表示 |\n";
    std::cout << "|-|-|-|\n";
    long long sizes[] = {10, 100, 1000, 10000};
    for (long long sz : sizes) {
        long long ops = sz * sz / 2;
        std::cout << "| " << sz << "        | " << ops
                  << "           | O(n²)   |\n";
    }
    std::cout << "----\n";
    return 0;
}

综合对比与总结

所有算法/数据结构一览

大O各级别直观比较

假设 $n=100$，每秒执行1000次操作：

复杂度	操作次数	大约用时	现实例子
$O(\log n)$	7次	瞬间	二分查找
$O(n)$	100次	0.1秒	简单查找
$O(n\log n)$	700次	0.7秒	快速排序
$O(n^2)$	10000次	10秒	选择排序
$O(n!)$	$10^{157}$次	宇宙年龄也不够	旅行商暴力

---

核心结论

关于二分查找：

• 必须在有序列表上使用
• 最坏情况下需要 ${\log }_{2}n$ 步
• 比简单查找快得多，数据越大优势越大
  关于大O：
• 衡量的是操作次数的增长规律，不是秒数
• 描述最坏情况
• 从快到慢：$O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n!)$
  关于数据结构：
• 数组：随机读取快 $O(1)$，插入删除慢 $O(n)$，内存连续
• 链表：随机读取慢 $O(n)$，插入删除快 $O(1)$，内存分散
  关于选择排序：
• 时间复杂度 $O(n^2)$，简单但效率不高
• 是理解更快排序算法（如快速排序 $O(n\log n)$）的基础

递归、分治与快速排序——从零理解

全章知识地图

第三章：递归

3.1 什么是递归？

递归就是一个函数在执行过程中调用它自己。
先看一个现实场景：

你在奶奶的阁楼里翻到一个上锁的箱子，奶奶说钥匙可能在另一个大盒子里。那个大盒子里还有更多小盒子，小盒子里还有盒子……
怎么找钥匙？
方法一（循环）：建一个"待检查盒子"的堆，不断从堆里拿出一个盒子检查：

建一个 待检查盒子的堆
while 堆不为空:
    取出一个盒子
    for 盒子里的每样东西:
        if 是盒子:
            放进堆里等待检查
        if 是钥匙:
            找到了！

方法二（递归）：函数检查一个盒子，如果发现了盒子就调用自己去检查那个盒子：

找钥匙(一个盒子):
    for 盒子里的每样东西:
        if 是盒子:
            找钥匙(这个盒子)   <-- 调用自己！
        if 是钥匙:
            找到了！

两种方法结果相同，但方法二更简洁清晰。递归的价值在于让代码更易读，而不是更快。

3.2 递归必须有的两个部分

递归函数如果没有停止条件，会永远运行下去！
比如一个倒计时函数，错误写法：

倒计时(3) --> 打印3 --> 倒计时(2) --> 打印2 --> 倒计时(1) --> 打印0 --> 倒计时(-1) --> ...永无止境

正确的递归函数必须包含：

关键原则：每次递归调用，问题规模必须向基础情形靠近（缩小），否则就是无限循环。

3.3 经典例子：阶乘

阶乘定义：
$$n!=n\times (n-1)\times (n-2)\times \cdots \times 2\times 1$$
$$5!=5\times 4\times 3\times 2\times 1=120$$
发现规律：
$$5!=5\times 4!$$
$$4!=4\times 3!$$
$$⋮$$
$$1!=1\text{（基础情形，直接返回1）}$$
用递归表达：
$$\text{fact}(n)=\{\begin{array}{ll}1& \text{若 }n=1\text{（基础情形）}\\ n\times \text{fact}(n-1)& \text{若 }n>1\text{（递归情形）}\end{array}$$

3.4 调用栈（Call Stack）

什么是栈？

栈是一种数据结构，就像一叠盘子：

        +---------+
        |  盘子3  |  <-- 最后放上去，最先被拿走（顶部）
        +---------+
        |  盘子2  |
        +---------+
        |  盘子1  |  <-- 最先放上去，最后被拿走（底部）
        +---------+

栈只有两个操作：

• push（压入）：把新元素放到顶部
• pop（弹出）：从顶部取出元素
  后进先出（LIFO）：最后放进去的最先取出来。

计算机的调用栈

每次调用一个函数，计算机都会在调用栈上压入一个新的栈帧，记录这次函数调用的所有变量。函数返回时，这个栈帧被弹出。
用 greet("小明") 调用过程演示：

第1步：调用 greet("小明")
+------------------+
| greet            |  <-- 当前在执行
| name = "小明"    |
+------------------+
第2步：greet 内部调用 greet2("小明")
+------------------+
| greet2           |  <-- 当前在执行
| name = "小明"    |
+------------------+
| greet            |  <-- 暂停等待，变量保留在栈中
| name = "小明"    |
+------------------+
第3步：greet2 返回，弹出，回到 greet
+------------------+
| greet            |  <-- 从暂停处继续
| name = "小明"    |
+------------------+
第4步：greet 调用 bye()
+------------------+
| bye              |  <-- 当前在执行
+------------------+
| greet            |  <-- 暂停等待
| name = "小明"    |
+------------------+
第5步：bye 返回，greet 返回，栈清空
(空)

核心思想：当你从一个函数调用另一个函数时，调用者被暂停，它的所有变量保留在栈中，等被调用的函数结束后再继续。

递归的调用栈演示

fact(3) 的执行过程：

调用 fact(3)
    |
    +-- 调用 fact(2)
            |
            +-- 调用 fact(1)
                    |
                    返回 1   (基础情形！)
            |
            接收到1，返回 2 * 1 = 2
    |
    接收到2，返回 3 * 2 = 6
最终结果：6

调用栈的变化：

          压入            压入            弹出(返回1)      弹出(返回2)
+--------+   +--------+   +--------+   +--------+   +--------+
|        |   |fact(1) |   |fact(1) |   |        |   |        |
|        |   |x=1     |   |x=1     |   |fact(2) |   |        |
|fact(2) |   |fact(2) |   |fact(2) |   |x=2     |   |fact(3) |
|x=2     |   |x=2     |   |x=2     |   |fact(3) |   |x=3     |
|fact(3) |   |fact(3) |   |fact(3) |   |x=3     |   |x=3     |
|x=3     |   |x=3     |   |x=3     |   +--------+   +--------+
+--------+   +--------+   +--------+   返回2*1=2     返回3*2=6

每个 fact 调用都有自己独立的变量 x，互不干扰。

递归的代价：栈溢出

递归每次调用都要在栈上占用内存。如果递归太深（比如递归一百万层），栈会被撑爆，这就叫栈溢出（Stack Overflow）。
解决方案：

• 改写成循环（节省内存）
• 使用尾递归优化（部分语言支持）

3.5 C++ 完整实现：递归

// 递归示例：倒计时 + 阶乘
// 演示基础情形、递归情形、调用栈的工作方式
#include <iostream>
// =============================================
// 示例1：倒计时（展示基础情形和递归情形）
// =============================================
// 参数 i：从 i 开始倒数到 0
void countdown(int i) {
    // 打印当前数字
    std::cout << i << " ";
    // 基础情形：数到0就停止，不再递归
    if (i <= 0) {
        std::cout << "\n";
        return;
    }
    // 递归情形：调用自己，但 i 减1（问题规模缩小）
    countdown(i - 1);
}
// =============================================
// 示例2：阶乘（经典递归）
// =============================================
// 计算 n! = n * (n-1) * ... * 2 * 1
// 数学定义：fact(n) = n * fact(n-1)，fact(1) = 1
// 参数 n：必须是正整数
long long factorial(int n) {
    // 基础情形：1! = 1，直接返回，不再递归
    if (n == 1) {
        return 1;
    }
    // 递归情形：n! = n * (n-1)!
    // 注意：每次调用 n 都减小，最终会到达 n==1 的基础情形
    return (long long)n * factorial(n - 1);
}
// =============================================
// 示例3：递归求数组总和（分治思路的铺垫）
// =============================================
// 思路：
//   sum([2, 4, 6]) = 2 + sum([4, 6])
//                       = 4 + sum([6])
//                           = 6 + sum([])
//                                 = 0  (基础情形)
// 参数：
//   arr   - 整数数组
//   index - 当前处理到哪个下标（从0开始）
int recursiveSum(const int arr[], int size, int index) {
    // 基础情形：下标超出数组范围，说明处理完了，返回0
    if (index >= size) {
        return 0;
    }
    // 递归情形：当前元素 + 后续所有元素的和
    // 每次 index+1，逐步向基础情形靠近
    return arr[index] + recursiveSum(arr, size, index + 1);
}
// =============================================
// 示例4：递归查找数组最大值
// =============================================
// 思路：
//   max(arr) = max(arr[0], max(arr[1:]))
// 基础情形：只有一个元素，它就是最大值
int recursiveMax(const int arr[], int size, int index) {
    // 基础情形：只剩最后一个元素
    if (index == size - 1) {
        return arr[index];
    }
    // 递归情形：比较当前元素和后续部分的最大值
    int maxOfRest = recursiveMax(arr, size, index + 1);
    return arr[index] > maxOfRest ? arr[index] : maxOfRest;
}
int main() {
    // 测试倒计时
    std::cout << "倒计时（从3开始）：";
    countdown(3);
    // 测试阶乘
    std::cout << "\n阶乘计算：\n";
    for (int i = 1; i <= 7; i++) {
        std::cout << "  " << i << "! = " << factorial(i) << "\n";
    }
    // 测试递归求和
    int arr[] = {2, 4, 6, 8, 10};
    int size = 5;
    std::cout << "\n递归求和 [2,4,6,8,10] = "
              << recursiveSum(arr, size, 0) << "\n";
    // 测试递归找最大值
    int arr2[] = {3, 7, 1, 9, 5};
    int size2 = 5;
    std::cout << "递归找最大值 [3,7,1,9,5] = "
              << recursiveMax(arr2, size2, 0) << "\n";
    return 0;
}

第四章：分治与快速排序

4.1 分治策略（Divide & Conquer，D&C）

核心思想

把一个大问题拆分成更小的同类问题，直到小到可以直接解决（基础情形），然后把结果组合起来。
两个步骤：

1. 找基础情形：最简单、能直接解决的情况是什么？
2. 缩小问题：每次递归调用，问题规模必须向基础情形靠近

土地分割例子

一块 $1680\times 640$ 米的农田，要分成尽量大的正方形，怎么做？

步骤1：在 1680×640 的土地上，
       能放下的最大正方形是 640×640
       放两个后，剩余 400×640
步骤2：对剩余的 400×640 继续同样操作
       最大正方形是 400×400
       剩余 240×400
步骤3：对 240×400 继续
       最大正方形是 240×240
       剩余 160×240
步骤4：对 160×240 继续
       最大正方形是 160×160
       剩余 80×160
步骤5：对 80×160：基础情形！
       160 = 2 × 80，可以整除
       最大正方形是 80×80，刚好填满！
结论：整块农田最大正方形边长 = 80米

这其实就是欧几里得算法（辗转相除法）的应用。

递归求数组总和

普通循环很容易，但用分治递归怎么做？

sum([2, 4, 6]) 的分治思路：
sum([2, 4, 6])
= 2 + sum([4, 6])
       = 4 + sum([6])
              = 6 + sum([])
                     = 0   <-- 基础情形：空数组和为0
              = 6 + 0 = 6
       = 4 + 6 = 10
= 2 + 10 = 12

4.2 快速排序（Quicksort）

快速排序是分治策略的典型应用，实际工程中使用最广泛的排序算法之一。

核心思路

1. 选一个基准值（pivot），比如选第一个元素
2. 分区（partition）：把数组分成两部分
   • 小于等于基准值的 → 左边
   • 大于基准值的 → 右边
3. 递归：对左右两部分分别调用快速排序
4. 合并：左部分排好序 + 基准值 + 右部分排好序 = 整体有序

三元素例子演示

对 [33, 15, 10] 排序，选 33 作为基准值：

原数组：[33, 15, 10]
选基准值 pivot = 33
小于33的：[15, 10]  ←  左子数组
大于33的：[]        ←  右子数组
递归排序左子数组 [15, 10]：
    选基准值 pivot = 15
    小于15的：[10]  ←  左子数组（只有1个元素，基础情形）
    大于15的：[]    ←  右子数组（空，基础情形）
    结果：[10] + [15] + [] = [10, 15]
合并结果：
    [10, 15] + [33] + [] = [10, 15, 33]
排序完成！

递归调用树

最坏情况 vs 最好情况

最坏情况：每次选的基准值恰好是最大（或最小）值，比如对已排序数组选第一个元素：

对已排序数组 [1,2,3,4,5] 选第一个作为基准值：
quicksort([1,2,3,4,5])
  pivot=1, 左=[], 右=[2,3,4,5]
  quicksort([2,3,4,5])
    pivot=2, 左=[], 右=[3,4,5]
    quicksort([3,4,5])
      pivot=3, 左=[], 右=[4,5]
      ...

调用栈高度 $=n$，每层处理 $n$ 个元素，总时间：
$$O(n)\times O(n)=O(n^2)$$
最好情况（也是平均情况）：每次选到中间值，数组被均匀分成两半：

quicksort([3,1,4,1,5,9,2,6])
  pivot=3（中间附近）
  左=[1,1,2], 右=[4,5,9,6]
    两边继续分...

调用栈高度 $=\log n$（每次折半），每层处理 $n$ 个元素，总时间：
$$O(n)\times O(\log n)=O(n\log n)$$

4.3 大O再审视：常数因子

两个同为 $O(n\log n)$ 的算法，哪个更快？
快速排序 vs 归并排序，时间复杂度写法都是 $O(n\log n)$，但实际上：
$$\text{真实时间}=\text{常数}\times n\log n$$
完整写法：
$$T=c\cdot n\log n$$
快速排序的常数 $c$ 更小，所以实际运行更快。
什么时候常数无关紧要？
比较 $O(\log n)$ 和 $O(n)$：
$$\text{二分查找：}1\text{s}\times \log n$$
$$\text{简单查找：}10\text{ms}\times n$$
当 $n=4\times 10^9$ 时：

• 二分查找：$1\text{s}\times 32=32\text{s}$
• 简单查找：$0.01\text{s}\times 4\times 10^9=4\times 10^7\text{s}$（约460天）
  常数再大也挡不住 $O(\log n)$ 对 $O(n)$ 的压倒性优势。
  什么时候常数有影响？
  当两个算法复杂度相同（如都是 $O(n\log n)$）时，常数小的那个胜出。这就是快速排序比归并排序在实践中更常用的原因。

---

排序算法	平均情况	最坏情况	常数因子	实践表现
选择排序	$O(n^2)$	$O(n^2)$	小	慢
归并排序	$O(n\log n)$	$O(n\log n)$	较大	稳定但略慢
快速排序	$O(n\log n)$	$O(n^2)$	很小	实践最快

---

4.4 C++ 完整实现：快速排序

// 快速排序完整实现（含详细注释）
// 演示分治策略、基准值选择、最坏/平均情况
#include <iostream>
#include <vector>
#include <cstdlib>   // rand, srand
#include <ctime>     // time
// =============================================
// 版本1：简单版快速排序（易于理解）
// 直接创建新数组存放左右部分，思路清晰
// =============================================
std::vector<int> quicksortSimple(const std::vector<int>& arr) {
    // 基础情形：数组长度 < 2，已经是"有序"的，直接返回
    if ((int)arr.size() < 2) {
        return arr;
    }
    // 选择第一个元素作为基准值
    int pivot = arr[0];
    // 分区：把元素分成小于等于基准值、大于基准值两组
    std::vector<int> less;    // 存放 <= pivot 的元素
    std::vector<int> greater; // 存放 > pivot 的元素
    // 从下标1开始（跳过基准值本身）
    for (int i = 1; i < (int)arr.size(); i++) {
        if (arr[i] <= pivot) {
            less.push_back(arr[i]);    // 放左边
        } else {
            greater.push_back(arr[i]); // 放右边
        }
    }
    // 递归排序左右子数组，再合并
    // 结果 = 排序好的左部分 + 基准值 + 排序好的右部分
    std::vector<int> sortedLess    = quicksortSimple(less);
    std::vector<int> sortedGreater = quicksortSimple(greater);
    // 拼接三部分
    std::vector<int> result;
    result.insert(result.end(), sortedLess.begin(), sortedLess.end());
    result.push_back(pivot);
    result.insert(result.end(), sortedGreater.begin(), sortedGreater.end());
    return result;
}
// =============================================
// 版本2：原地快速排序（工程常用版）
// 不需要额外数组，直接在原数组上交换元素
// =============================================
// 分区函数：把 arr[low..high] 分成两部分
// 选 arr[high] 作为基准值（随机选后交换过来）
// 返回基准值最终所在的位置（下标）
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;       // i 指向"小于等于pivot区域"的最后一个元素
    for (int j = low; j < high; j++) {
        // 如果当前元素小于等于基准值，就把它换到左边区域
        if (arr[j] <= pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    // 把基准值放到正确位置（左边都<=它，右边都>它）
    int tmp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = tmp;
    return i + 1; // 返回基准值的最终位置
}
// 原地快速排序（在 arr[low..high] 范围内排序）
void quicksortInPlace(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // 随机选基准值（避免最坏情况）
        // 把随机位置的元素换到末尾，然后 partition 会选末尾作为基准
        int randomIdx = low + rand() % (high - low + 1);
        int tmp = arr[randomIdx];
        arr[randomIdx] = arr[high];
        arr[high] = tmp;
        // 分区，获取基准值的最终位置
        int pivotPos = partition(arr, low, high);
        // 递归排序基准值左边和右边
        // 注意：基准值已经在正确位置，不需要再动它
        quicksortInPlace(arr, low, pivotPos - 1);  // 排左半部分
        quicksortInPlace(arr, pivotPos + 1, high); // 排右半部分
    }
    // 如果 low >= high，说明只有0或1个元素，基础情形，直接返回
}
// =============================================
// 辅助函数：打印数组
// =============================================
void printVec(const std::vector<int>& v, const std::string& label) {
    std::cout << label << ": [";
    for (int i = 0; i < (int)v.size(); i++) {
        std::cout << v[i];
        if (i < (int)v.size() - 1) std::cout << ", ";
    }
    std::cout << "]\n";
}
// =============================================
// 演示分治求和（递归版 sum）
// =============================================
int recursiveSumDC(const std::vector<int>& arr, int index) {
    // 基础情形：下标超出，没有元素可加，返回0
    if (index >= (int)arr.size()) {
        return 0;
    }
    // 递归情形：当前元素 + 剩余元素的和
    return arr[index] + recursiveSumDC(arr, index + 1);
}
int main() {
    srand((unsigned int)time(nullptr)); // 初始化随机数种子
    // =============================================
    // 测试简单版快速排序
    // =============================================
    std::cout << "=== 简单版快速排序（新建数组）===\n";
    std::vector<int> arr1 = {10, 5, 2, 3, 8, 7, 1};
    printVec(arr1, "排序前");
    std::vector<int> sorted1 = quicksortSimple(arr1);
    printVec(sorted1, "排序后");
    std::cout << "\n";
    // =============================================
    // 测试原地快速排序
    // =============================================
    std::cout << "=== 原地快速排序（随机基准值）===\n";
    std::vector<int> arr2 = {64, 25, 12, 22, 11, 90, 3};
    printVec(arr2, "排序前");
    quicksortInPlace(arr2, 0, (int)arr2.size() - 1);
    printVec(arr2, "排序后");
    std::cout << "\n";
    // =============================================
    // 测试递归求和（分治思路）
    // =============================================
    std::cout << "=== 分治递归求和 ===\n";
    std::vector<int> arr3 = {2, 4, 6, 8, 10};
    int total = recursiveSumDC(arr3, 0);
    printVec(arr3, "数组");
    std::cout << "递归求和结果 = " << total << "\n";
    std::cout << "\n";
    // =============================================
    // 展示不同情况下的时间复杂度
    // =============================================
    std::cout << "=== 快速排序时间复杂度总结 ===\n";
    std::cout << "----\n";
    std::cout << "| 情况     | 调用栈高度 | 每层操作 | 总时间复杂度 |\n";
    std::cout << "|-|-|-|-|\n";
    std::cout << "| 最坏情况 | O(n)      | O(n)    | O(n^2)      |\n";
    std::cout << "| 平均情况 | O(log n)  | O(n)    | O(n log n)  |\n";
    std::cout << "| 最好情况 | O(log n)  | O(n)    | O(n log n)  |\n";
    std::cout << "----\n";
    std::cout << "（使用随机基准值可以避免最坏情况，使平均情况成为常态）\n";
    return 0;
}

综合对比与总结

递归 vs 循环

---

对比项	递归	循环
代码可读性	往往更清晰	有时更繁琐
内存使用	较多（调用栈）	较少
运行速度	略慢（函数调用开销）	略快
适用场景	问题本身是递归结构	简单重复操作

---

所有排序算法对比

---

算法	时间复杂度（平均）	时间复杂度（最坏）	思路
选择排序	$O(n^2)$	$O(n^2)$	每次选最小放到前面
归并排序	$O(n\log n)$	$O(n\log n)$	分治，稳定但常数大
快速排序	$O(n\log n)$	$O(n^2)$	分治，常数小，实践最快

---

分治三要素

核心结论

关于递归：

• 递归 = 函数调用自身
• 必须有基础情形（终止条件）和递归情形（缩小问题）
• 每次函数调用在调用栈上占用内存，递归太深会栈溢出
  关于调用栈：
• 后进先出的数据结构
• 记录每个函数调用的局部变量状态
• 递归的"记忆"就存在调用栈里
  关于分治：
• 找基础情形 → 缩小问题 → 合并结果
• 二分查找、快速排序都是分治的应用
  关于快速排序：
• 平均时间复杂度 $O(n\log n)$，常数因子小，实践最快
• 关键：随机选基准值，避免 $O(n^2)$ 的最坏情况
• 最坏情况（有序数组选第一个元素为基准）：$O(n^2)$

哈希表 与 广度优先搜索 — 从零理解

第一部分：哈希表（Hash Table）

1. 为什么需要哈希表？

想象你在超市当收银员，手边有一本记录所有商品价格的册子。

• 没有排序的册子：你要从头翻到尾找 “苹果” 的价格，最坏要翻遍所有页。时间复杂度：$O(n)$
• 按字母排序的册子：你可以用二分查找，快一些。时间复杂度：$O(\log n)$
• 你有一个记性超好的同事 Maggie：你直接问她 “苹果多少钱”，她瞬间告诉你。时间复杂度：$O(1)$
  我们的目标就是用代码实现这个 “Maggie”，那就是哈希表。

2. 哈希函数（Hash Function）是什么？

哈希函数就是：输入一个字符串（或任意数据），输出一个数字（数组下标）。

"apple"  -->  哈希函数  -->  3
"milk"   -->  哈希函数  -->  0
"avocado"-->  哈希函数  -->  4

一个好的哈希函数必须满足：

1. 一致性：同样的输入，每次都返回同样的输出。
   • “apple” 今天映射到 3，明天也必须映射到 3。
2. 分散性：不同的输入，尽量映射到不同的数字。
   • 如果所有单词都映射到同一个位置，那就没有意义了。

3. 哈希表的内部结构

哈希表 = 哈希函数 + 数组
工作过程如下：
存入数据时：

用 "apple" 作为 key
         |
         v
     哈希函数
         |
         v
    输出下标 3
         |
         v
  把价格 0.67 存到数组[3]

查询数据时：

查询 "apple" 的价格
         |
         v
     哈希函数
         |
         v
    输出下标 3
         |
         v
  直接读取数组[3] = 0.67  --> 瞬间找到！

不需要从头搜索，直接定位，所以是 $O(1)$。

4. 用 C++ 实现哈希表

C++ 标准库里的 unordered_map 就是哈希表。

#include <iostream>
#include <string>
#include <unordered_map>
int main() {
    // 创建一个哈希表：key 是商品名（string），value 是价格（double）
    std::unordered_map<std::string, double> book;
    // 向哈希表中插入数据（键值对）
    book["apple"]   = 0.67;
    book["milk"]    = 1.49;
    book["avocado"] = 1.49;
    // 查询某个商品的价格
    // 用 [] 操作符，时间复杂度 O(1)（平均情况）
    std::cout << "苹果的价格: " << book["apple"] << std::endl;
    // 检查某个 key 是否存在，用 find() 更安全
    // find() 找到返回迭代器，找不到返回 end()
    if (book.find("banana") == book.end()) {
        std::cout << "香蕉不在册子里" << std::endl;
    }
    // 遍历哈希表中的所有键值对
    // 注意：unordered_map 的遍历顺序是不确定的！
    for (const auto& pair : book) {
        std::cout << pair.first << " 的价格是 " << pair.second << std::endl;
    }
    return 0;
}

5. 哈希表的三大用途

用途一：映射关系（Lookup）

比如电话簿：姓名 --> 电话号码

#include <iostream>
#include <string>
#include <unordered_map>
int main() {
    // 电话簿：姓名映射到电话号码
    std::unordered_map<std::string, std::string> phone_book;
    // 添加联系人
    phone_book["jenny"]     = "8675309";
    phone_book["emergency"] = "911";
    // 查询联系人
    std::cout << "Jenny 的电话: " << phone_book["jenny"] << std::endl;
    return 0;
}

还有 DNS 解析：网址 --> IP 地址，原理完全相同。

用途二：去重（防止重复）

比如投票系统，每人只能投一次票：

#include <iostream>
#include <string>
#include <unordered_map>
// 用哈希表记录已投票的人
// key: 姓名, value: 是否已投票（bool）
std::unordered_map<std::string, bool> voted;
// 检查某人是否已经投过票
void check_voter(const std::string& name) {
    // count() 返回 key 出现的次数，unordered_map 中只能是 0 或 1
    if (voted.count(name) > 0) {
        // 已经投过票，赶出去！
        std::cout << name << " 已经投过票了，赶出去！" << std::endl;
    } else {
        // 没有投过票，允许投票，并记录下来
        voted[name] = true;
        std::cout << name << " 可以投票！" << std::endl;
    }
}
int main() {
    check_voter("tom");   // 第一次 -> 可以投票
    check_voter("mike");  // 第一次 -> 可以投票
    check_voter("mike");  // 第二次 -> 赶出去！
    return 0;
}

如果用列表来做同样的事，每次都要从头扫描整个列表，时间是 $O(n)$。
用哈希表，每次查询是 $O(1)$，快得多！

用途三：缓存（Cache）

网站缓存的逻辑：

用户请求某个页面 URL
        |
        v
检查 URL 是否在缓存哈希表中？
   /           \
  是             否
  |              |
直接返回        服务器重新计算
缓存数据        并把结果存入缓存

#include <iostream>
#include <string>
#include <unordered_map>
// 缓存表：URL --> 页面内容
std::unordered_map<std::string, std::string> cache;
// 模拟从服务器获取数据（实际中是很慢的操作）
std::string get_data_from_server(const std::string& url) {
    return "<html>这是 " + url + " 的页面内容</html>";
}
// 获取页面，优先从缓存读取
std::string get_page(const std::string& url) {
    // 检查缓存中有没有这个 URL
    if (cache.count(url) > 0) {
        std::cout << "[缓存命中] 直接返回缓存数据" << std::endl;
        return cache[url]; // 直接返回缓存，不经过服务器
    } else {
        std::cout << "[缓存未命中] 从服务器获取数据..." << std::endl;
        std::string data = get_data_from_server(url);
        cache[url] = data; // 把结果存入缓存，下次就快了
        return data;
    }
}
int main() {
    // 第一次访问，走服务器
    std::cout << get_page("http://example.com") << std::endl;
    // 第二次访问，走缓存
    std::cout << get_page("http://example.com") << std::endl;
    return 0;
}

6. 碰撞（Collision）是什么？

在现实中，哈希函数几乎不可能保证每个不同的 key 都映射到不同的位置。
碰撞就是：两个不同的 key 被映射到了同一个数组位置。
比如，按首字母分配位置：

"apple"  --> 位置 0  (A)
"avocado"--> 位置 0  (A)  <-- 撞车了！
"banana" --> 位置 1  (B)

解决方法：在发生碰撞的位置，改用链表存储多个元素。

数组位置 0: [apple:0.67] -> [avocado:1.49] -> NULL
数组位置 1: [banana:0.30] -> NULL
数组位置 2: NULL
...

链表越长，查找就越慢。极端情况下（所有 key 全撞到一起），性能退化为 $O(n)$。

7. 负载因子（Load Factor）

$$\text{负载因子}=\frac{\text{已占用的槽位数}}{\text{数组总槽位数}}$$
例如：数组有 5 个槽，已存了 2 个元素：
$$\text{负载因子}=\frac{2}{5}=0.4$$
经验法则：当负载因子 $>0.7$ 时，需要扩容（Resize）。
扩容过程：

1. 创建一个新的、更大的数组（通常是原来的 2 倍）
2. 把所有旧数据重新用哈希函数插入新数组
   扩容虽然耗时，但均摊下来，哈希表的操作依然是 $O(1)$。

8. 性能总结

---

操作	平均情况	最坏情况
查找	$O(1)$	$O(n)$
插入	$O(1)$	$O(n)$
删除	$O(1)$	$O(n)$

---

最坏情况发生在：哈希函数太差，所有 key 全部碰撞在一起。
只要用好的哈希函数并控制负载因子，平均情况就是 $O(1)$。

第二部分：广度优先搜索（BFS，Breadth-First Search）

1. 什么是图（Graph）？

图是一种描述事物之间连接关系的数据结构。
图由两部分组成：

• 节点（Node / Vertex）：代表一个事物（人、地点、网页…）
• 边（Edge）：代表两个事物之间的连接关系
  举例：朋友欠钱关系

有向图（Directed Graph）：边有方向，箭头指向表示关系的方向。
无向图（Undirected Graph）：边没有方向，双方互为邻居。

2. 广度优先搜索解决什么问题？

BFS 能回答两类问题：

• 问题一：从 A 到 B 有没有路径？
• 问题二：从 A 到 B 的最短路径是什么？

3. BFS 的核心思想

以"在朋友网络中找芒果卖家"为例：
第一步：先搜索所有一度好友（直接朋友）
第二步：再搜索所有二度好友（朋友的朋友）
第三步：以此类推……
这就像水波扩散，从中心一圈一圈向外搜索：

        你
       /|\
      / | \
   Alice Bob Claire    <-- 第一圈（一度好友）
    |    |    |
   Peggy Anuj Thom Jonny  <-- 第二圈（二度好友）

关键原则：先加入队列的人，先被搜索。这样才能保证先搜完一度好友，再搜二度好友，找到的就是最近的卖家。

4. 队列（Queue）—— BFS 的核心工具

队列就像排队买票：先来的先服务（FIFO: First In, First Out）

结构	规则	记忆方式
队列（Queue）	先进先出（FIFO）	排队买票
栈（Stack）	后进先出（LIFO）	叠盘子

---

队列的操作：

• 入队（Enqueue）：把元素加到队尾
• 出队（Dequeue）：从队头取出元素

入队: A B C 依次入队
队列状态: [A, B, C]
            ^         ^
           队头       队尾
出队: 取出 A
队列状态: [B, C]

5. 图的代码表示

用哈希表来表示图！key 是节点，value 是它的所有邻居列表。

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
    // 用哈希表表示图
    // key: 节点名称
    // value: 该节点的所有邻居（有向图中，就是该节点指向的节点）
    std::unordered_map<std::string, std::vector<std::string>> graph;
    graph["you"]    = {"alice", "bob", "claire"};
    graph["bob"]    = {"anuj", "peggy"};
    graph["alice"]  = {"peggy"};
    graph["claire"] = {"thom", "jonny"};
    graph["anuj"]   = {};  // 没有邻居（叶节点）
    graph["peggy"]  = {};
    graph["thom"]   = {};
    graph["jonny"]  = {};
    return 0;
}

对应的图结构：

6. BFS 完整 C++ 实现

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <queue>       // 标准库队列
#include <unordered_set> // 用于记录已搜索过的节点
// 判断某人是否是芒果卖家（这里简单规定：名字最后一个字母是 'm' 就是卖家）
bool person_is_seller(const std::string& name) {
    return name.back() == 'm';
}
// BFS 主函数：从 start 节点出发，在图 graph 中搜索芒果卖家
// 返回值：true 表示找到了卖家，false 表示没找到
bool search(
    const std::string& start,
    const std::unordered_map<std::string, std::vector<std::string>>& graph
) {
    // 创建一个队列，用于存放"待搜索"的人
    std::queue<std::string> search_queue;
    // 创建一个集合，记录"已经搜索过"的人，避免重复搜索和死循环
    std::unordered_set<std::string> searched;
    // 把起点的所有邻居（直接好友）先加入队列
    for (const auto& neighbor : graph.at(start)) {
        search_queue.push(neighbor);
    }
    // 只要队列不为空，就继续搜索
    while (!search_queue.empty()) {
        // 从队头取出一个人（先进先出！）
        std::string person = search_queue.front();
        search_queue.pop();
        // 如果这个人之前没有搜索过
        if (searched.find(person) == searched.end()) {
            // 检查他/她是不是芒果卖家
            if (person_is_seller(person)) {
                std::cout << person << " 是芒果卖家！" << std::endl;
                return true; // 找到了，返回成功
            } else {
                // 不是卖家，把他/她的所有朋友加入队列（下一圈）
                if (graph.count(person) > 0) {
                    for (const auto& neighbor : graph.at(person)) {
                        search_queue.push(neighbor);
                    }
                }
                // 标记这个人为"已搜索"
                searched.insert(person);
            }
        }
        // 如果已经搜索过了，直接跳过（continue 到下一次循环）
    }
    // 队列空了还没找到，说明网络里没有芒果卖家
    std::cout << "没有找到芒果卖家" << std::endl;
    return false;
}
int main() {
    // 建立图（用哈希表表示）
    std::unordered_map<std::string, std::vector<std::string>> graph;
    graph["you"]    = {"alice", "bob", "claire"};
    graph["bob"]    = {"anuj", "peggy"};
    graph["alice"]  = {"peggy"};
    graph["claire"] = {"thom", "jonny"};
    graph["anuj"]   = {};
    graph["peggy"]  = {};
    graph["thom"]   = {};  // thom 的最后一个字母是 'm'，他是芒果卖家！
    graph["jonny"]  = {};
    // 从 "you" 开始搜索
    search("you", graph);
    return 0;
}

7. BFS 执行过程演示（逐步图解）

以上面的图为例，从 “you” 开始：
初始状态：把 you 的所有邻居加入队列

队列: [alice, bob, claire]
已搜索: {}

第1步：取出 alice，不是卖家，把 alice 的朋友（peggy）加入队列

队列: [bob, claire, peggy]
已搜索: {alice}

第2步：取出 bob，不是卖家，把 bob 的朋友（anuj, peggy）加入队列

队列: [claire, peggy, anuj, peggy]
已搜索: {alice, bob}

第3步：取出 claire，不是卖家，把 claire 的朋友（thom, jonny）加入队列

队列: [peggy, anuj, peggy, thom, jonny]
已搜索: {alice, bob, claire}

第4步：取出 peggy，不是卖家，peggy 没有邻居

队列: [anuj, peggy, thom, jonny]
已搜索: {alice, bob, claire, peggy}

第5步：取出 anuj，不是卖家

队列: [peggy, thom, jonny]
已搜索: {alice, bob, claire, peggy, anuj}

第6步：取出 peggy，已搜索过，跳过！

队列: [thom, jonny]
已搜索: {alice, bob, claire, peggy, anuj}

第7步：取出 thom，名字最后是 ‘m’，找到芒果卖家！

8. BFS 的时间复杂度

• 每条边最多被访问一次：$O(E)$，其中 $E$ 是边的数量
• 每个节点最多入队一次：$O(V)$，其中 $V$ 是节点的数量
  $$\text{BFS 总时间复杂度}=O(V+E)$$

9. 拓扑排序（Topological Sort）

如果任务之间有依赖关系，比如"吃早饭"必须在"刷牙"之后，可以用图来表示这种依赖：

BFS/拓扑排序可以给出一个合法的执行顺序：
合法顺序（其中一种）：

1. 起床
2. 洗澡
3. 刷牙
4. 吃早饭

10. 树（Tree）是特殊的图

树是一种**没有环（回路）**的有向图。

        A
       / \
      B   C
     / \   \
    D   E   F

• 每个节点有且只有一个父节点（根节点除外）
• 不会出现"从某节点出发，沿着边又回到该节点"的情况

总结对比

---

	哈希表	BFS
解决的问题	快速查找、去重、缓存	最短路径、图中可达性
核心数据结构	数组 + 哈希函数	队列 + 哈希表（记录已访问）
平均时间复杂度	$O(1)$ 查找/插入/删除	$O(V+E)$
关键概念	碰撞、负载因子、扩容	节点、边、FIFO队列

---

哈希表要点：

• 哈希表 = 哈希函数 + 数组
• 平均 $O(1)$，最坏 $O(n)$（发生大量碰撞时）
• 负载因子 $>0.7$ 时需要扩容
• 适合：映射、去重、缓存
  BFS 要点：
• 必须使用队列（FIFO），否则找不到最短路径
• 必须记录已搜索的节点，否则可能死循环
• 时间复杂度 $O(V+E)$
• 适合：最短路径、判断连通性

Dijkstra算法、贪心算法与NP完全问题 — 从零理解

第一部分：Dijkstra 算法

1. BFS 的局限性

上一章的广度优先搜索（BFS）找的是段数最少的路径。
但现实中，路段数少不代表花费少。比如：

起点 ---(6分钟)---> A ---(1分钟)---> 终点
起点 ---(2分钟)---> B ---(5分钟)---> 终点
起点 ---(2分钟)---> B ---(3分钟)---> A ---(1分钟)---> 终点

BFS 会选 “起点 -> A -> 终点”（只有2段），但实际花费 $6+1=7$ 分钟。
而 “起点 -> B -> A -> 终点”（3段），花费只有 $2+3+1=6$ 分钟，更快！
结论：当图的边有权重（时间/费用/距离）时，需要用 Dijkstra 算法来找最短路径。

2. 核心术语

• 加权图（Weighted Graph）：每条边都有一个数字（权重），代表代价
• 无权图（Unweighted Graph）：边没有权重，BFS 适用
• 有向无环图（DAG）：边有方向，且不存在环路，Dijkstra 适用

---

图的类型	适用算法
无权图	广度优先搜索（BFS）
加权图（无负权边）	Dijkstra 算法
加权图（有负权边）	Bellman-Ford 算法

---

3. Dijkstra 算法的四个步骤

1. 找到代价最小的节点（从起点出发，目前已知中最便宜能到达的节点）
2. 更新该节点所有邻居的代价（看看经过这个节点能不能让邻居更便宜）
3. 对每个节点重复步骤 1 和 2（已处理过的节点不再处理）
4. 根据父节点回溯，得出最终路径

4. 手工演示（用换钢琴的例子）

Rama 用一本书换钢琴，想花最少的钱。图如下：

         $0           $30
书 -----> 海报 -------> 吉他
  \       |  \          |
   \      |$35\    $15  | $35
$5  \     v    \        v
     ----> LP  -> 鼓组 -> 钢琴
               $20    $10

更清晰的流向：

书
├─($0)──> 海报
│          ├─($30)──> 吉他 ──($35)──> 钢琴
│          └─($35)──> 鼓组 ──($10)──> 钢琴
└─($5)──> LP
           ├─($15)──> 吉他
           └─($20)──> 鼓组

初始代价表（从"书"出发，未知的设为无穷大 $\infty$）：

节点	代价	父节点
海报	$0	书
LP	$5	书
吉他	$\infty$	-
鼓组	$\infty$	-
钢琴	$\infty$	-

---

第1轮：处理代价最小的节点 = 海报（$0）
经过海报可以到达：

• 吉他：$0+30=30$，比 $\infty$ 小，更新！
• 鼓组：$0+35=35$，比 $\infty$ 小，更新！

---

节点	代价	父节点
海报	$0	已处理
LP	$5	书
吉他	$30	海报
鼓组	$35	海报
钢琴	$\infty$	-

---

第2轮：处理代价最小的未处理节点 = LP（$5）
经过LP可以到达：

• 吉他：$5+15=20$，比 $30$ 小，更新！父节点改为 LP
• 鼓组：$5+20=25$，比 $35$ 小，更新！父节点改为 LP

---

节点	代价	父节点
LP	$5	已处理
吉他	$20	LP
鼓组	$25	LP
钢琴	$\infty$	-

---

第3轮：处理 吉他（$20）
经过吉他可以到达：

• 钢琴：$20+35=55$，比 $\infty$ 小，更新！
  第4轮：处理 鼓组（$25）
  经过鼓组可以到达：
• 钢琴：$25+10=35$，比 $55$ 小，更新！父节点改为鼓组
  最终代价表：

---

节点	最终代价	父节点
海报	$0	书
LP	$5	书
吉他	$20	LP
鼓组	$25	LP
钢琴	$35	鼓组

---

回溯路径（从钢琴往父节点回溯）：

钢琴 <-- 鼓组 <-- LP <-- 书

即：书 → LP → 鼓组 → 钢琴，总花费 $35$。

5. 为什么负权边会让 Dijkstra 失效？

Dijkstra 的核心假设：一旦某节点被处理（选为当前最小代价），就不会再找到更便宜的路径到它。
如果有负权边，这个假设就被打破了。
举例：

起点 --($0)--> 海报 --($35)--> 鼓组
                ^
海报 <--(-$7)-- LP
起点 --($5)--> LP

Dijkstra 会先处理海报（代价$0），认为不可能更便宜了。
但实际上通过 LP 再走负权边到海报，代价只有 $5+(-7)=-2$，更便宜！
结论：有负权边时，请使用 Bellman-Ford 算法（本书不展开）。

6. 完整 C++ 实现

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <limits>   // 提供 numeric_limits<double>::infinity()
#include <set>      // 用于记录已处理的节点
// 在加权图中用 Dijkstra 算法找从 start 到 finish 的最短路径
// graph[节点][邻居] = 边的权重（代价）
void dijkstra(
    const std::string& start,
    const std::string& finish,
    const std::unordered_map<std::string,
          std::unordered_map<std::string, double>>& graph
) {
    // costs 表：记录从起点到每个节点的当前最小代价
    // 初始时除了直接邻居，其余节点代价为无穷大
    std::unordered_map<std::string, double> costs;
    // parents 表：记录每个节点的父节点，用于最后回溯路径
    std::unordered_map<std::string, std::string> parents;
    // 已处理节点的集合，处理过的节点不再重复处理
    std::set<std::string> processed;
    // 初始化：先把所有节点的代价设为无穷大
    for (const auto& node : graph) {
        costs[node.first] = std::numeric_limits<double>::infinity();
        for (const auto& neighbor : node.second) {
            costs[neighbor.first] = std::numeric_limits<double>::infinity();
        }
    }
    // 起点的代价是 0
    costs[start] = 0.0;
    // 找到代价最小的未处理节点（相当于书中的 find_lowest_cost_node）
    auto find_lowest_cost_node = [&]() -> std::string {
        double lowest_cost = std::numeric_limits<double>::infinity();
        std::string lowest_node = "";
        for (const auto& pair : costs) {
            // 如果这个节点代价更小，并且还没有被处理过
            if (pair.second < lowest_cost &&
                processed.find(pair.first) == processed.end()) {
                lowest_cost = pair.second;
                lowest_node = pair.first;
            }
        }
        return lowest_node; // 没有找到时返回空字符串
    };
    // 主循环：每次取代价最小的未处理节点
    std::string node = find_lowest_cost_node();
    while (!node.empty()) {
        double cost = costs[node]; // 当前节点的代价
        // 如果当前节点在图中有邻居，就去更新邻居的代价
        if (graph.count(node)) {
            const auto& neighbors = graph.at(node);
            for (const auto& neighbor_pair : neighbors) {
                const std::string& neighbor = neighbor_pair.first;
                double edge_weight = neighbor_pair.second;
                // 经过当前节点到达邻居的新代价
                double new_cost = cost + edge_weight;
                // 如果新代价比已知代价更小，就更新
                if (new_cost < costs[neighbor]) {
                    costs[neighbor] = new_cost;
                    // 同时更新父节点（记录走哪条路更便宜）
                    parents[neighbor] = node;
                }
            }
        }
        // 标记当前节点为已处理
        processed.insert(node);
        // 找下一个代价最小的未处理节点
        node = find_lowest_cost_node();
    }
    // 打印最终结果
    std::cout << "从 " << start << " 到 " << finish << " 的最短代价: "
              << costs[finish] << std::endl;
    // 回溯路径：从终点往回找父节点
    std::vector<std::string> path;
    std::string current = finish;
    while (current != start) {
        path.push_back(current);
        if (parents.find(current) == parents.end()) {
            std::cout << "路径不存在！" << std::endl;
            return;
        }
        current = parents[current];
    }
    path.push_back(start);
    // 反转，从起点到终点输出
    std::cout << "最短路径: ";
    for (int i = (int)path.size() - 1; i >= 0; i--) {
        std::cout << path[i];
        if (i != 0) std::cout << " --> ";
    }
    std::cout << std::endl;
}
int main() {
    // 构建加权图（用哈希表嵌套哈希表表示）
    // graph[节点A][节点B] = A到B的权重
    std::unordered_map<std::string,
        std::unordered_map<std::string, double>> graph;
    // 起点的邻居
    graph["start"]["a"] = 6.0;
    graph["start"]["b"] = 2.0;
    // 节点 A 的邻居
    graph["a"]["fin"] = 1.0;
    // 节点 B 的邻居
    graph["b"]["a"]   = 3.0;
    graph["b"]["fin"] = 5.0;
    // 终点没有邻居
    graph["fin"] = {};
    // 运行 Dijkstra 算法
    dijkstra("start", "fin", graph);
    return 0;
}

输出结果：

从 start 到 fin 的最短代价: 6
最短路径: start --> b --> a --> fin

7. Dijkstra 执行过程（ASCII图）

图的结构：

                  6
  start ─────────────────> a
    │                      │
    │ 2                    │ 1
    │                      │
    └──────> b             └──────> fin
             │                       ^
             │ 3            5        │
             └──────────────> ───────┘
                   (b->fin)
             │
             │ 3
             └──> a (更新a的代价为5)

逐步更新代价表：

初始:  start=0, a=INF, b=INF, fin=INF
       (start已知邻居: a=6, b=2)
处理start后:
       a=6(父:start), b=2(父:start), fin=INF
处理b(代价2):
       经过b到a: 2+3=5 < 6, 更新! a=5(父:b)
       经过b到fin: 2+5=7 < INF, 更新! fin=7(父:b)
处理a(代价5):
       经过a到fin: 5+1=6 < 7, 更新! fin=6(父:a)
处理fin: 终点，算法结束
最终: fin=6, 路径: start->b->a->fin

第二部分：贪心算法（Greedy Algorithm）

1. 什么是贪心算法？

贪心算法的思路极其简单：

每一步都选择当前看起来最好的选项，不回头，不后悔。
技术术语：每步选择局部最优解，期待最终得到全局最优解。

2. 例子一：教室排课（贪心奏效）

你有一个教室，想安排尽可能多的课：

课程	开始	结束
美术	9:00	10:00
英语	9:30	10:30
数学	10:00	11:00
CS	10:30	11:30
音乐	11:00	12:00

---

贪心策略：每次选结束时间最早且不与已选课程冲突的课。
执行过程：

可选课程: [美术(10:00结束), 英语(10:30), 数学(11:00), CS(11:30), 音乐(12:00)]
第1步: 选结束最早的 -> 美术 (9:00-10:00)
       教室占用到 10:00
第2步: 找10:00后开始的最早结束课 -> 数学 (10:00-11:00)
       教室占用到 11:00
第3步: 找11:00后开始的最早结束课 -> 音乐 (11:00-12:00)
结果: [美术, 数学, 音乐] 共3门课，是最优解！

这个问题贪心算法恰好能找到最优解。

3. 例子二：背包问题（贪心不奏效）

背包容量 35 磅，有三件物品：

物品	重量	价值
音响	30磅	$3000
笔记本	20磅	$2000
吉他	15磅	$1500

---

贪心策略：每次选最贵的放进去。

第1步: 最贵的是音响($3000)，放入。背包剩余容量: 35-30=5磅
第2步: 笔记本20磅放不下，吉他15磅也放不下，结束。
贪心结果: 音响 = $3000
最优结果: 笔记本 + 吉他 = $2000 + $1500 = $3500  <-- 更好！

贪心算法在背包问题上不能保证最优解，只能得到近似解。
结论：贪心算法不是万能的，但在很多场景下能快速给出"足够好"的答案。

4. 例子三：集合覆盖问题（贪心近似）

你想让广播覆盖全部8个州，有5个电台可选：

电台	覆盖的州
k1	id, nv, ut
k2	wa, id, mt
k3	or, nv, ca
k4	nv, ut
k5	ca, az

---

精确算法：枚举所有 $2^5=32$ 种子集，找覆盖全部州且电台数最少的。
问题：如果有 $n$ 个电台，需要检查 $2^n$ 种组合，时间复杂度 $O(2^n)$，非常慢。
$$\text{n个电台的组合数}=2^n$$
贪心近似算法：每次选覆盖最多未覆盖州的电台。
执行过程：

需要覆盖: {mt, wa, or, id, nv, ut, ca, az}
第1步:
  k1覆盖未覆盖州: {id, nv, ut}       -> 3个
  k2覆盖未覆盖州: {wa, id, mt}       -> 3个
  k3覆盖未覆盖州: {or, nv, ca}       -> 3个
  k4覆盖未覆盖州: {nv, ut}           -> 2个
  k5覆盖未覆盖州: {ca, az}           -> 2个
  选 k1(或k2或k3，假设选k2): {wa, id, mt}
  剩余未覆盖: {or, nv, ut, ca, az}
第2步:
  k3覆盖未覆盖州: {or, nv, ca}       -> 3个 (最多)
  选 k3
  剩余未覆盖: {ut, az}
  (后续选 k1 覆盖 ut, k5 覆盖 az)
最终选择: {k2, k3, k1, k5}，共4个电台

贪心近似算法时间复杂度：$O(n^2)$，其中 $n$ 为电台数量。比精确算法的 $O(2^n)$ 快得多。

5. 集合覆盖完整 C++ 实现

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
int main() {
    // 需要覆盖的所有州
    std::unordered_set<std::string> states_needed = {
        "mt", "wa", "or", "id", "nv", "ut", "ca", "az"
    };
    // 每个电台覆盖的州（哈希表：电台名 -> 覆盖的州的集合）
    std::unordered_map<std::string, std::unordered_set<std::string>> stations;
    stations["k1"] = {"id", "nv", "ut"};
    stations["k2"] = {"wa", "id", "mt"};
    stations["k3"] = {"or", "nv", "ca"};
    stations["k4"] = {"nv", "ut"};
    stations["k5"] = {"ca", "az"};
    // 存储最终选择的电台
    std::unordered_set<std::string> final_stations;
    // 贪心循环：只要还有未覆盖的州，就继续选电台
    while (!states_needed.empty()) {
        std::string best_station = "";       // 本轮最佳电台
        std::unordered_set<std::string> states_covered; // 最佳电台覆盖的未覆盖州
        // 遍历所有电台，找出覆盖最多未覆盖州的那个
        for (const auto& pair : stations) {
            const std::string& station = pair.first;
            const std::unordered_set<std::string>& station_states = pair.second;
            // 计算该电台与"未覆盖州"的交集（即该电台能新增覆盖多少州）
            std::unordered_set<std::string> covered;
            for (const auto& s : station_states) {
                if (states_needed.count(s)) {
                    // 这个州既在该电台覆盖范围内，又还没有被覆盖
                    covered.insert(s);
                }
            }
            // 如果这个电台覆盖的新州比当前最佳电台更多，就更新
            if (covered.size() > states_covered.size()) {
                best_station  = station;
                states_covered = covered;
            }
        }
        // 把最佳电台加入结果集合
        if (!best_station.empty()) {
            final_stations.insert(best_station);
            // 从"需要覆盖"列表中移除已覆盖的州
            for (const auto& s : states_covered) {
                states_needed.erase(s);
            }
        }
    }
    // 打印最终选择的电台
    std::cout << "选择的电台: ";
    for (const auto& s : final_stations) {
        std::cout << s << " ";
    }
    std::cout << std::endl;
    return 0;
}

第三部分：NP 完全问题（NP-Complete）

1. 什么是 NP 完全问题？

某些问题，目前没有人知道如何用多项式时间的算法解决它们。
这类问题的特点：问题规模稍大，计算量就会爆炸式增长。
旅行商问题（Traveling Salesperson Problem, TSP） 就是经典例子：
一个销售员要拜访 $n$ 个城市，每个城市只去一次，最后回到出发点，求最短路线。
需要枚举所有可能的路线数：
$$\text{路线数}=n!$$
具体数字：

城市数 $n$	可能路线数 $n!$
2	$2!=2$
3	$3!=6$
4	$4!=24$
5	$5!=120$
10	$10!=3,628,800$
20	$20!\approx 2.4\times 10^{18}$

---

$$n!\text{ 增长速度远超任何多项式，属于超指数增长}$$

2. 集合覆盖问题为什么也是 NP 完全的？

$n$ 个电台的所有可能子集数量：
$$2^n$$

电台数 $n$	子集数 $2^n$	按每秒10个子集计算所需时间
5	32	3.2 秒
10	1024	约 1.7 分钟
20	1,048,576	约 1.2 天
32	4,294,967,296	约 13.6 年

---

数量爆炸，根本无法在合理时间内枚举所有可能。

3. 如何判断一个问题是否是 NP 完全的？

以下这些特征是警示信号，说明问题可能是 NP 完全的：

1. 数据量小时很快，数据量大时急剧变慢
         |
         v
2. 问题涉及"所有 X 的组合"
         |
         v
3. 问题涉及序列（如城市顺序），且很难解决
         |
         v
4. 问题涉及集合，且很难解决
         |
         v
5. 可以把问题转化为"旅行商"或"集合覆盖"问题

实际例子对比：

问题	类型	原因
A 到 B 的最短路	容易（多项式时间）	Dijkstra 可解
经过所有城市一次的最短路	NP 完全	路线数是 $n!$
在图中找最短路径	容易	BFS/Dijkstra
在图中找最大团（所有人互认识）	NP 完全	需枚举所有子集

---

4. 面对 NP 完全问题怎么办？

不要强行寻找精确算法！改用近似算法（Approximation Algorithm）：

精确算法（NP完全）:       近似算法（贪心）:
枚举所有可能           每步选局部最优
时间 O(2^n) 或 O(n!)   时间 O(n^2) 或更低
结果: 完美最优解         结果: 足够好的近似解

近似算法的评判标准：

1. 速度：是否足够快？
2. 精度：结果与最优解相差多少？

5. 旅行商问题的贪心近似

每次选离当前城市最近的未访问城市：

城市: Marin, San Francisco, Oakland, Berkeley
从 Marin 出发:
  最近未访问: SF (6英里)
  最近未访问: Oakland (9英里)
  最近未访问: Berkeley (7英里)
  返回 Marin
总距离: 约71英里（不是最短，但很接近最优）

总结

---

算法/概念	核心思想	时间复杂度	适用场景
Dijkstra	每次处理代价最小的节点，松弛邻居	$O((V+E)\log V)$	加权图最短路（无负权）
贪心算法	每步选局部最优	因题而异，通常较快	调度、近似优化
精确集合覆盖	枚举所有子集	$O(2^n)$	不可行（数据大时）
贪心集合覆盖	每次选覆盖最多未覆盖元素的集合	$O(n^2)$	NP完全问题的近似
旅行商精确	枚举所有路线	$O(n!)$	不可行（城市多时）
旅行商贪心	每次选最近未访问城市	$O(n^2)$	NP完全问题的近似

---

核心记忆点：

• BFS 找最少段数路径，Dijkstra 找最小权重路径
• Dijkstra 要求所有权重非负
• 贪心算法：每步局部最优，简单快速，但不总是全局最优
• NP 完全问题：无已知的多项式时间精确算法，用贪心近似应对
• 判断 NP 完全的标志：涉及"所有组合"、问题规模小时快大时极慢

算法拓展：10个你应该了解的算法 — 从零理解

1. 二叉搜索树（Binary Search Tree，BST）

为什么需要它？

回顾二分查找：在一个已排序数组中查找元素，时间 $O(\log n)$，很快。
但有个问题：每次新增一个用户名，都要重新排序整个数组，插入操作代价很高。
二叉搜索树解决了这个问题：插入时直接放到正确位置，不需要事后排序。

结构规则

对于每个节点：

• 左子树的所有节点值 < 当前节点值
• 右子树的所有节点值 > 当前节点值

上图的规律：

• David 左边是 Adit（字母序更小）
• David 右边是 Manning（字母序更大）
• Manning 左边是 Maggie，右边是 Mike

查找过程演示

查找 “Maggie”：

第1步: 从根节点 David 开始
       Maggie > David  --> 往右走
第2步: 到达 Manning
       Maggie < Manning --> 往左走
第3步: 到达 Maggie
       找到了！

每次都能排除一半的节点，就像二分查找一样！

性能对比

---

操作	有序数组	二叉搜索树（平均）	二叉搜索树（最坏）
查找	$O(\log n)$	$O(\log n)$	$O(n)$
插入	$O(n)$（需重排）	$O(\log n)$	$O(n)$
删除	$O(n)$	$O(\log n)$	$O(n)$
随机访问	$O(1)$	不支持	不支持

---

最坏情况发生在树严重不平衡时，比如按顺序插入所有节点：

插入顺序: A -> B -> C -> D -> E
结果（退化成链表）:
A
 \
  B
   \
    C
     \
      D
       \
        E

这时查找时间退化为 $O(n)$，跟链表一样慢。
解决方案：使用自平衡树，如红黑树（Red-Black Tree），它会在插入/删除时自动调整结构保持平衡。

常见的树结构及用途

---

数据结构	主要用途
二叉搜索树（BST）	通用有序数据存储
红黑树	C++ STL 的 map、set 内部实现
B 树	数据库索引（如 MySQL）
堆（Heap）	优先队列，Dijkstra 算法优化
伸展树（Splay Tree）	缓存、自适应访问优化

---

C++ 简单 BST 实现

#include <iostream>
#include <string>
// 定义二叉搜索树的节点结构
struct Node {
    std::string value;  // 节点存储的值
    Node* left;         // 左子节点指针
    Node* right;        // 右子节点指针
    // 构造函数：新建节点时左右子节点默认为空
    Node(const std::string& val) : value(val), left(nullptr), right(nullptr) {}
};
// 向 BST 中插入一个新值
// 规则：比当前节点小的放左边，大的放右边
Node* insert(Node* root, const std::string& val) {
    if (root == nullptr) {
        // 当前位置为空，直接在此创建新节点
        return new Node(val);
    }
    if (val < root->value) {
        // 新值比当前节点小，递归插入左子树
        root->left = insert(root->left, val);
    } else if (val > root->value) {
        // 新值比当前节点大，递归插入右子树
        root->right = insert(root->right, val);
    }
    // val == root->value 时，BST 一般不插入重复值
    return root;
}
// 在 BST 中搜索一个值
// 返回 true 表示找到，false 表示不存在
bool search(Node* root, const std::string& val) {
    if (root == nullptr) {
        // 走到了空节点，说明不存在
        return false;
    }
    if (val == root->value) {
        // 恰好等于当前节点，找到了
        return true;
    } else if (val < root->value) {
        // 比当前节点小，去左子树找
        return search(root->left, val);
    } else {
        // 比当前节点大，去右子树找
        return search(root->right, val);
    }
}
// 中序遍历（左 -> 根 -> 右），结果是升序排列
void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    std::cout << root->value << " ";
    inorder(root->right);
}
int main() {
    Node* root = nullptr;
    // 插入一些用户名
    root = insert(root, "David");
    root = insert(root, "Manning");
    root = insert(root, "Adit");
    root = insert(root, "Maggie");
    root = insert(root, "Mike");
    // 中序遍历，输出应该是字母升序
    std::cout << "中序遍历（升序）: ";
    inorder(root);
    std::cout << std::endl;
    // 搜索测试
    std::cout << "搜索 Maggie: " << (search(root, "Maggie") ? "找到" : "未找到") << std::endl;
    std::cout << "搜索 John:   " << (search(root, "John")   ? "找到" : "未找到") << std::endl;
    return 0;
}

2. 倒排索引（Inverted Index）

搜索引擎是怎么工作的？

假设有三个网页：

页面 A: "hi there"
页面 B: "hi everyone"
页面 C: "there is a way"

构建倒排索引（用哈希表实现）：

"hi"       -> [页面A, 页面B]
"there"    -> [页面A, 页面C]
"everyone" -> [页面B]
"is"       -> [页面C]
"a"        -> [页面C]
"way"      -> [页面C]

用户搜索 “hi”：直接查哈希表，瞬间得到 [页面A, 页面B]，时间 $O(1)$。
倒排索引（Inverted Index）= 从词映射到包含该词的文档列表的哈希表。
这是 Google、Elasticsearch 等搜索引擎的核心数据结构。

3. 傅里叶变换（Fourier Transform）

直觉理解

傅里叶变换的本质：把一个复杂信号分解成若干简单信号（频率分量）的叠加。
最好的比喻：

输入: 一杯混合果汁（复杂信号）
         |
         v
   傅里叶变换
         |
         v
输出: 苹果汁30% + 橙汁50% + 芒果汁20%（各个频率分量）

对于音乐：

一首歌（复杂波形）
         |
         v
   傅里叶变换
         |
         v
低音频率成分 + 中音频率成分 + 高音频率成分

主要应用

---

应用场景	原理
MP3 压缩	分解出对人耳不重要的高频部分，丢弃它们
JPG 图片压缩	去掉人眼不敏感的高频细节
Shazam 识曲	提取歌曲的频率"指纹"进行匹配
地震预测	分析地震波的频率成分
DNA 分析	寻找重复序列的周期性
均衡器（EQ）	增强低音/削减高音

---

傅里叶变换的快速计算版本叫做快速傅里叶变换（FFT），时间复杂度从 $O(n^2)$ 降低到：
$$O(n\log n)$$

4. 并行算法（Parallel Algorithms）

背景

以前 CPU 越来越快，算法慢点也没关系，等等硬件就好了。
现在 CPU 主频基本到瓶颈了，转而增加核心数（多核处理器）。
要让算法变快，必须让它能同时利用多个核心，这就是并行算法。

例子：并行快速排序

普通快速排序时间复杂度：$O(n\log n)$
并行快速排序：理论上可以做到 $O(n)$

普通排序（单核）:
[1,9,3,7,2,8,4,6,5]
           |
    排序所有元素（1个核心做所有工作）
并行排序（多核）:
[1,9,3,7,2,8,4,6,5]
         |
    分成两半，两个核心同时排序
    [1,9,3,7] 和 [2,8,4,6,5]
         |
    合并结果

并行算法的两个难点

1. 并行管理开销
把任务分配给多个核心、最后合并结果，这些操作本身也需要时间。

2个核心并不意味着速度提升 2 倍
实际提升通常远小于核心数量

2. 负载均衡

核心A: [简单任务 x5]  -> 10秒完成
核心B: [复杂任务 x5]  -> 60秒完成
核心A 完成后等待核心B，白白浪费50秒！

如何均匀分配任务是并行算法设计的核心难题。

5. MapReduce（分布式算法）

什么是分布式算法？

并行算法在一台机器的多个核心上运行。
分布式算法在多台机器上同时运行。
典型场景：

数据库有 1000 亿行数据
单台机器跑 SQL 查询：几小时甚至几天
100 台机器一起跑：可能只需几分钟

MapReduce 是最著名的分布式算法，Apache Hadoop 是其开源实现。

Map 函数

对数组的每个元素独立地施加同一个操作：

原数组: [1, 2, 3, 4, 5]
操作:   每个元素乘以2
结果:   [2, 4, 6, 8, 10]

关键点：每个元素的操作相互独立，可以分配给不同机器同时执行：

机器1: 处理 [1, 2]  -> [2, 4]
机器2: 处理 [3, 4]  -> [6, 8]
机器3: 处理 [5]     -> [10]
合并:               -> [2, 4, 6, 8, 10]

Reduce 函数

把一个数组归约成单个值：

原数组: [1, 2, 3, 4, 5]
操作:   求和
过程:   1+2=3, 3+3=6, 6+4=10, 10+5=15
结果:   15

MapReduce 整体流程

海量原始数据
      |
      v
  Map 阶段（多台机器并行处理）
      |
      v
  中间结果（分散在各机器）
      |
      v
  Reduce 阶段（汇总归约）
      |
      v
  最终答案

6. 布隆过滤器（Bloom Filter）

问题背景

Google 爬取了万亿个网页，需要判断"这个网址有没有爬过"。
如果用哈希表存所有爬过的 URL，需要极大的内存空间。
布隆过滤器是一种概率型数据结构，用极少的内存回答"是否存在"的问题，但答案可能不精确。

布隆过滤器的特性

---

回答	含义
“不存在”	100% 确定不存在（无漏报）
“存在”	很可能存在，但有小概率误报（假阳性）

---

普通哈希表:
  查询结果: 100% 准确
  内存占用: 极大（需存储所有数据）
布隆过滤器:
  查询结果: 可能误报（说存在但实际不存在）
           不会漏报（说不存在就一定不存在）
  内存占用: 极小（只存储几个比特位）

实际应用场景

---

使用方	用途
Google	网页去重爬取
Reddit	检测链接是否已发过
bit.ly	检测恶意 URL（误报无妨，宁可多拦截）
数据库	快速判断记录是否可能存在，避免不必要的磁盘查询

---

7. HyperLogLog

问题背景

Google 想统计今天有多少个不重复的搜索词。
如果精确统计，需要把所有词存下来，再去重，内存消耗极大。
HyperLogLog 是一种近似计算不重复元素数量的算法，使用极少内存。

精度与内存对比

---

方法	内存占用	精度
精确计数（哈希集合）	$O(n)$，随数据量线性增长	100% 准确
HyperLogLog	固定约 1.5 KB	误差约 2%

---

核心思想：当你不需要 100% 精确，只需要"差不多"的答案时，用概率型数据结构换取巨大的内存节省。

8. SHA 算法（安全哈希算法）

SHA 和普通哈希函数的区别

第五章讲的哈希函数：字符串 -> 数组下标（用于哈希表）
SHA（Secure Hash Algorithm）：字符串 -> 固定长度的字符串（“指纹”）

输入: "hello"
SHA256输出: "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"
输入: "hello!"  (只改了一个字符)
SHA256输出: "334d016f755cd6dc58c53a86e183882f8ec14f52fb05345887c8a5edd42c87b7"

输出完全不同，这叫做雪崩效应。

用途一：验证文件完整性

不需要传输 4GB 的大文件来验证是否相同，只需比较 SHA 哈希值：

你的文件  ─── SHA256 ──> "abc123..."
朋友文件  ─── SHA256 ──> "abc123..."
哈希值相同 = 文件内容完全一样

用途二：密码存储

网站不应该直接存储你的密码明文！

用户注册时:
  原始密码: "mypassword123"
        |
        v SHA256
  存入数据库: "ef92b778bafe771207..."  (哈希值)
用户登录时:
  输入密码: "mypassword123"
        |
        v SHA256
  计算哈希: "ef92b778bafe771207..."
        |
  与数据库对比 -> 匹配，登录成功

即使数据库被攻击者获取，攻击者得到的也只是哈希值，无法反推出原始密码（单向函数）。
$$\text{密码}\stackrel{\text{SHA}}{\to }\text{哈希值}\text{（可以）}$$
$$\text{哈希值}\stackrel{???}{\to }\text{密码}\text{（不可能）}$$

SHA 算法版本

---

版本	状态	建议
SHA-0	已有漏洞	不要使用
SHA-1	已有漏洞	不要使用
SHA-2	安全	可以使用
SHA-3	最新、安全	推荐
bcrypt	专为密码设计	密码哈希的黄金标准

---

局部敏感哈希（Simhash）

SHA 是局部不敏感的：改一个字符，哈希值天翻地覆（防止攻击者猜密码）。
有时我们需要相反的效果：两段相似的文本，哈希值也应该相似。
Simhash = 局部敏感哈希（Locality-Sensitive Hashing）

原文: "The quick brown fox"
Simhash: 10110101...
改动一词: "The fast brown fox"
Simhash: 10110111...  (只有少数位不同)

---

使用方	用途
Google	爬取时检测重复网页
教师	检测学生论文是否抄袭
Scribd	检测上传内容是否侵权

---

9. Diffie-Hellman 密钥交换

加密通信的难题

如果 A 想给 B 发送加密消息，他们需要一个共同的"密钥"。
但是：如何在不安全的网络上安全地传递密钥本身？

A 把密钥发给 B:
  发送过程: A --> [网络（可能被监听）] --> B
  如果密钥被截获，加密就没有意义了！

Diffie-Hellman 优雅地解决了这个问题。

核心思路（公钥/私钥）

每个人有两把钥匙:
  公钥（Public Key）:  可以公开给所有人
  私钥（Private Key）: 只有自己知道
加密过程:
  B 的公钥（所有人都知道）
        |
        v
  A 用 B 的公钥 加密消息
        |
        v
  加密后的消息发送给 B
        |
        v
  只有 B 用自己的 私钥 才能解密

就像一个开着盖子的箱子（公钥），任何人都能把信放进去锁上，但只有箱子主人（私钥）能打开取信。

实际应用

Diffie-Hellman 和它的继任者 RSA 是现代互联网加密的基础：

• HTTPS 网站通信
• SSH 远程登录
• 消息加密（Signal、WhatsApp 等）

10. 线性规划（Linear Programming）

什么是线性规划？

在一定约束条件下，最大化（或最小化）某个目标。

例子：工厂生产决策

工厂生产两种产品：T恤和帆布袋。

产品	需要布料	需要纽扣	利润
T恤	1米	5颗	$2
帆布袋	2米	2颗	$3

---

现有资源：布料 11 米，纽扣 20 颗。
问：生产多少件 T恤、多少个帆布袋，利润最大？
设 T恤数量为 $x$，帆布袋数量为 $y$：
目标（最大化利润）：
$$\max 2x+3y$$
约束条件：
$$x+2y\le 11\text{（布料限制）}$$
$$5x+2y\le 20\text{（纽扣限制）}$$
$$x\ge 0,y\ge 0\text{（数量不能为负）}$$
这就是一个线性规划问题，用Simplex 算法求解。

线性规划与图算法的关系

所有图算法（Dijkstra、BFS 等）都可以用线性规划来表达和求解。

线性规划（更通用的框架）
         |
         |-- 图问题（最短路、最大流...）
         |-- 生产调度问题
         |-- 资源分配问题
         |-- 投票策略问题
         |-- ...

线性规划是更底层、更通用的优化工具。

总结：10 个算法一览

---

算法/数据结构	核心思想	典型应用
二叉搜索树	左小右大，快速定位	数据库索引、有序集合
倒排索引	词 -> 文档列表的映射	搜索引擎
傅里叶变换	信号分解为频率分量	MP3/JPG压缩、Shazam
并行算法	多核同时处理	大规模排序、图像处理
MapReduce	Map分散+Reduce归约	大数据处理（Hadoop）
布隆过滤器	概率型存在查询	爬虫去重、恶意URL检测
HyperLogLog	近似统计不重复元素数	统计独立访客/搜索词
SHA 算法	单向哈希，雪崩效应	密码存储、文件校验
Simhash	局部敏感哈希	查重、版权检测
Diffie-Hellman/RSA	公私钥加密体系	HTTPS、SSH、消息加密
线性规划	约束下最优化	生产调度、资源分配

---

选择后续学习方向的建议：

对数据库感兴趣?
  --> 深入学习 B树、红黑树、倒排索引
对安全/密码学感兴趣?
  --> 深入学习 SHA、Diffie-Hellman、RSA、bcrypt
对大数据感兴趣?
  --> 深入学习 MapReduce、Hadoop、Spark、HyperLogLog
对机器学习感兴趣?
  --> 深入学习 傅里叶变换、线性规划、概率算法
对系统性能感兴趣?
  --> 深入学习 并行算法、布隆过滤器、缓存算法