算法学习

License Deploy Status Last Commit

目的

用Rust实现《算法导论》第3版中的所有伪代码，同时对一些例题进行解答。谨(仅)为中文开发者提供。

阅读

本书用mdBook，阅读方法可参考这里。内容从《算法导论》第一部分第2章(这是正式开始介绍算法的地方)开始提供。

其它

`mdBook`相关

mdbook-katex

采用Lucas Zanini提供的mdbook-katex插件，许可证同样是MIT。

算法基础

介绍算法基础内容。

插入排序

主问题重现

我们在下面用形式化语言¹ (已加之修改)给出主问题的一个重现:

输入

$n$ 个数的数组 $< a_{1}, a_{2}, \dots, a_{n} >$

输出

输入数组的升序排列 $< a_{1}^{'}, a_{2}^{'}, \dots, a_{n}^{'} >$ ，满足 $a_{1}^{'} \leq a_{2}^{'} \leq \dots \leq a_{n}^{'}$

主问题思考

在《算法导论》中，我们先引入了插入排序，这并不特别简单(不如冒泡)但可以让我们进行较高级的初步学习。

来看下面实现:

实现1

pub fn realize<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

可以发现: 插入排序的核心逻辑是通过逐步比较和移动元素来维护一个有序的子序列。具体地:

有序部分逐步扩张：将数组分为已排序部分(初始仅含第一个元素)和未排序部分，每次从未排序部分取出第一个元素，将其插入到已排序部分的正确位置，直到所有元素有序。
原地插入：插入操作通过依次向后移动元素实现，无需额外空间。

注: 这里我们采用了泛型，使得任何实现了Ord trait的数组切片(理论上Vec也会自动转换)均可进行插入排序

在《算法导论》中，其实是不是通过swap，而是将操作值保存，直到最后再进行赋值，这样可以减少中间的连续交换导致的空间和时间损耗。代价是需要更高的数学水平，同时需要更多的trait(像接下来的实现)。

实现2

pub fn realize2<T: Ord + Copy>(arr: &mut [T]) {
    for i in 1..arr.len() {
        // 保存当前元素的值
        let key = arr[i];
        // 找到合适的插入位置
        let mut j = i;
        while j > 0 && key < arr[j - 1] {
            // 向后移动元素而不是交换
            arr[j] = arr[j - 1];
            j -= 1;
        }
        // 将保存的值插入到正确位置
        arr[j] = key;
    }
}

(注: 需要Copy)

也可以使用Clone:

pub fn realize2_clone<T: Ord + Clone>(arr: &mut [T]) {
    for i in 1..arr.len() {
        // 保存当前元素的值
        let key = arr[i].clone();
        // 找到合适的插入位置
        let mut j = i;
        while j > 0 && key < arr[j - 1] {
            // 向后移动元素而不是交换
            arr[j] = arr[j - 1].clone();
            j -= 1;
        }
        // 将保存的值插入到正确位置
        arr[j] = key;
    }
}

练习与回答

尝试将实现1改为降序排列(满足 $a_{1}^{'} \geq a_{2}^{'} \geq \dots \geq a_{n}^{'}$ )。

实现3

// 对应练习 1
pub fn realize3<T: Ord>(arr: &mut [T]) {
    for i in 0..arr.len() - 1 {
        let mut j = i;
        while j > 0 && arr[j] > arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

注: 可以发现: 在插入排序中，只需修改比较条件即可改变排序方向

所以我们也有实现4这种可以设置排序规则的:

实现4

// 实现以`compare`来控制排序规则的插入排序
pub fn realize4<T, F>(arr: &mut [T], compare: F)
where
    F: Fn(&T, &T) -> bool,
{
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && compare(&arr[j], &arr[j - 1]) {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

上面这种比较，对于学习过其他语言的读者来说，应该不成问题。这个比较很显然的允许我们操作一些更特殊的类型，比如说结构体:

#[derive(Debug)]
struct Person {
    name: String,
    age: u32,
}

fn main() {
    // 创建可变的结构体数组
    let mut people = vec![
        Person { name: "Alice".to_string(), age: 30 },
        Person { name: "Bob".to_string(), age: 25 },
        Person { name: "Charlie".to_string(), age: 35 },
    ];
    
    // 按年龄升序排序
    realize4(&mut people, |a, b| a.age < b.age);
    println!("按年龄排序: {:?}", people);
    
    // 按名字字典序排序
    realize4(&mut people, |a, b| a.name < b.name);
    println!("按名字排序: {:?}", people);
}

我们再来看别的例题，继续深化学习:

考虑以下查找问题:

输入: $n$ 个数的数组 $< a_{1}, a_{2}, \dots, a_{n} >$ 和一个值 $v$

输出: 下标 $i$ 使得 $v = A [i]$ ，或者当 $v$ 不在 $A$ 出现时，返回特殊值 $N I L$ ²

尝试给出一个线性查找³的例子。

观察来看，这道题目适合Option可以用Option::None来解决NIL。

实现5

pub fn realize5<T: PartialEq>(arr: &[T], v: T) -> Option<usize> {
    for i in 0..arr.len() {
        if v == arr[i] {
            return Some(i);
        }
    }
    None
}

这里用 PartialEq 而非 Eq 以支持部分(宽松)相等，而无需反射(自反)

本处"形式化语言"并非指是一种由严格定义的符号组成的字符串集合，而是描述一类算法对于输入/输出关系的控制，以自然语言化，较精准化，弱数学化提供算法行为。 ↩
NIL是算法描述中表示“空”或“终止”的通用符号。并且与NULL等空指针中区分。在一些结构(如链表)，NIL是一类特殊哨兵值(后见)，在标准库实现中，NIL就有所存在。 ↩
线性查找(Linear Search)，也称为顺序查找，是一种简单直观的搜索算法。它的核心思想是逐个遍历数据集中的元素，直到找到目标值或遍历完所有元素。 ↩

循环不变式

循环不变式(Loop Invariant) 是非常基础的一个概念，它是计算机科学中用于证明循环正确性的一种重要逻辑工具。是指在循环的每次迭代前后都保持为真的性质或条件，帮助验证循环的行为是否符合预期。

定义

循环不变式是在循环开始前、每次迭代后以及循环结束后均成立的逻辑断言。它反映了循环中变量的内在关系，与循环的终止条件共同保证程序的正确性。

性质

循环不变式有以下三条必须要满足的性质，这三条需要我们通过数学方法证明:

初始化(Initialization):循环开始前，不变式因变量初始值而成立。
保持(Maintenance):若某次迭代前不变式成立，则执行循环体后仍成立。
终止(Termination):循环结束时，不变式+终止条件共同推出目标结果。

这个定义非常漂亮，但还有更好理解的版本(《算法导论》原始版本的修改):

初始化: 循环开始前，不变式成立。
保持: 在某次迭代开始之前它成立，则迭代之后仍成立。
终止: 循环结束后，不变式提供一个性质来证明算法正确性。

解释

上面的这些内容比较抽象，但我们以代码为例就可以看出它们在讲什么:

// 典型: 数组求和
fn sum(arr: &[usize]) -> usize {
    let mut total = 0;
    let mut i = 0;
    while i < arr.len() {
        total += arr[i];
        i += 1;
    }
    total
}

让我们分析这个函数是否满足循环不变式，并进行证明。给定的循环不变式有两个:

total = arr + arr + ... + arr[i-1]
i <= arr.len()

证明

我们需要证明:

初始化: 在循环开始前，不变式成立。
保持: 如果在某次迭代前不变式成立，那么在下一次迭代前仍然成立。
终止: 循环终止时，不变式能推出算法的正确性。

1. 初始化

在循环开始前:

total = 0
i = 0
total = arr + ... + arr[i-1] 是空和(因为 i-1 = -1)，空和为 0，所以 total = 因为 i-1 = -10 满足。
i = 0 <= arr.len() 也成立。

2. 保持

假设在某次迭代前:

total = arr + ... + arr[i-1]
i <= arr.len()

执行循环体:

total += arr[i] ⇒ total = arr + ... + arr[i]
i += 1 ⇒ i 变为 i+1

此时:

total = arr + ... + arr[(i+1)-1] (因为 i 是更新后的值)，所以不变式仍然成立。
i <= arr.len(): 因为循环条件是 i < arr.len()，所以更新后的 i 满足 i <= arr.len()。

3. 终止

循环终止时:

i == arr.len() (因为循环条件是 i < arr.len()，且 i 每次增加 1)
此时 total = arr + ... + arr[i-1] = arr + ... + arr[arr.len()-1]，即整个数组的和。

因此，循环终止时 total 的值确实是数组所有元素的和，算法正确。

体会

可以发现，循环不变式是循环中始终保持为真的逻辑断言，它的三个特征都保证了它在循环前循环中循环后始终为真。

在设计算法时，循环不变式应满足以下要求:

2. 足够强，能证明正确性

不变式不能太弱，否则无法保证算法的正确性。

例如:如果不变式仅仅是 i <= arr.len()，它不能直接证明 total 是正确的和。

3. 可验证

不变式必须能在循环的初始化、保持、终止三个阶段被严格证明。

可以发现: 这些证明与数学归纳法类似，但不同于归纳法，它可以终止，且必须证明终止阶段。

总的来说，设置循环不变式的步骤是:

明确算法目标。
设计一个与目标相关的不变式。
验证初始化、保持、终止。

循环不变式是算法正确性的重要工具，合理使用它可以提高代码的可读性和可靠性。

深化

我们以上一期习题来尝试给出循环不变式并证明。

pub fn realize5<T: PartialEq>(arr: &[T], v: T) -> Option<usize> {
    for i in 0..arr.len() {
        if v == arr[i] {
            return Some(i);
        }
    }
    None
}

对于上一个代码，我们尝试给出这样的一个不变式:

在每次循环开始时，v 不在arr[0..i]中，并且 i < arr.len()

证明

初始化

循环开始时，i = 0，arr[0..i] 是空数组(arr[0..0] 不包含任何元素，你需要注意a..b的左闭右开原则)。

不变式成立: v 不在空数组中且i < arr.len()。

保持

假设在某次循环开始时，v 不在 arr[0..i] 中。

执行循环体:

检查 arr[i] == v:
- 如果 arr[i] == v，则直接返回 Some(i) (此时 v 首次出现在 arr[i]，同样注意左闭右开原则，虽然 v 出现在 arr[i] 中，但并不出现在 arr[0..i]，所以是符合循环不变式的)。
- 如果 arr[i] != v，则 v 仍然不在 arr[0..i+1] 中 (因为 v不在arr[0..i]且arr[i] != v)。
循环结束时，i增加 1，不变式仍然成立。

终止

循环结束后有两种情况:

提前返回 Some(i):
- 此时 v 出现在 arr[i]，符合不变式。
循环全部执行完毕并返回 None:
- 此时 i = arr.len() - 1，且 v 不在 arr[0..arr.len()] 中。
- 由于循环已经检查了所有元素，但 v 仍然未被找到，因此 v 不在整个数组中，返回 None 是正确的。

练习与回答

考虑为上一期的主问题实现，给出一个循环不变式并证明。

设计

我们需要为 外层循环 和 内层循环 分别设计循环不变式。

外层循环的不变式

在每次外层循环开始时，arr[0..i] 是已排序的。(即前 i 个元素已经排好序)

内层循环的不变式

在每次内层循环开始时，arr[j..i] 的所有元素都大于 arr[j-1]，并且 arr[0..i] 除了 arr[j] 外仍然有序。(即 arr[j] 正在被插入到正确的位置，其余部分仍然有序)

证明

外层循环不变式的证明

初始化:
- 当 i = 1 时，arr[0..1] 只有 1 个元素，自然是有序的。
- 成立。
保持:
- 假设 arr[0..i] 是有序的。
- 内层循环会将 arr[i] 插入到 arr[0..i] 的正确位置，使得 arr[0..i+1] 有序。
- 成立。
终止:
- 当 i == arr.len() 时，arr[0..arr.len()] 是整个数组，并且已经有序。
- 成立。

内层循环不变式的证明

初始化:
- 内层循环开始时，j = i，arr[j..i] 是空区间(j == i)，所以 arr[j..i] 的所有元素(无)都大于 arr[j-1]。
- arr[0..i] 除了 arr[j] 外有序(因为外层循环不变式保证 arr[0..i] 有序)。
- 成立。
保持:
- 如果 arr[j] < arr[j-1]，则交换它们，此时:
- arr[j] 的新值是原来的 arr[j-1]，而 arr[j-1] 的新值是原来的 arr[j]。
- 由于 arr[0..i] 原本有序(除了 arr[j])，交换后 arr[j-1] 仍然比左边的元素大(否则不会继续循环)。
- 成立。
终止:
- 内层循环终止时，j == 0 或 arr[j] >= arr[j-1]。
- 此时 arr[j] 已经插入到正确的位置，arr[0..i+1] 有序。
- 成立。

代码的正确性

外层循环保证每次迭代后 arr[0..i] 有序。
内层循环保证 arr[j] 被正确插入到 arr[0..i] 的合适位置。
最终，整个数组 arr 被排序。

注: 上面的内容与《算法导论》有所不同，但尽量减少了术语的使用，理解难度更低。使得你能看懂代码，就基本能看懂证明。

分析算法

分析算法(Algorithm Analysis) 是计算机科学中研究算法效率与资源消耗的学科，旨在评估算法在不同输入规模下的性能表现，为选择和优化算法提供理论依据。其核心目标是回答两个关键问题:

时间效率：算法执行需要多少时间？
空间效率：算法运行需要多少内存或其他资源？

RAM模型

《算法导论》介绍了一种 RAM模型(Random Access Machine，随机存取机)。它是计算机科学中用于分析算法时间复杂度的一种抽象计算模型。它简化了真实计算机的复杂性，假设所有基本操作(如算术运算、内存访问等)均可在常数时间内完成，从而聚焦于算法本身的逻辑效率。

核心特点

随机访问内存
- 假设内存是“扁平化”的，访问任意地址的数据耗时相同(与硬盘的顺序访问不同)。
- 例如，读取 A[i] 和 A[j] 的时间相同，无论 i 和 j 的距离多远。
基本操作耗时恒定
- 算术运算(+, -, *, /)
- 逻辑比较(>, ==, &&)
- 内存读写(赋值、访问变量)
- 控制流(if, for, return等)

以上操作均视为常数时间操作。

单处理器、无并发
- 假设程序按顺序执行，不考虑多线程、缓存或并行计算的影响。
无限内存(理想化)
- 忽略物理内存限制，但实际分析中仍需考虑空间复杂度。

为什么使用RAM模型？

简化分析：屏蔽硬件差异(如CPU速度、缓存层次)，专注于算法的渐进复杂度。
通用性：适用于大多数传统算法(排序、搜索、动态规划等)。
理论基准：与图灵机等价，但更贴近编程实践。

用RAM模型进行严格的算法分析是较难的，需要的数学技巧和工具很多。如:

pub fn realize<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

我们以 $c_{i}$ 表示每个操作的代价。

pub fn realize<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {                     // 代价: c_1
        let mut j = i;                          // 代价: c_2
        while j > 0 && arr[j] < arr[j - 1] {    // 代价: c_3
            arr.swap(j, j - 1);                 // 代价: c_4
            j -= 1;                             // 代价: c_5
        }
    }
}

注: 下面要使用求和知识，可参见附录。

每个代价在循环条件都有不同次数的消耗，通过数学分析可以得到:

// 先给定 n = arr.len()
pub fn realize<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {                     // 次数: n - 1
        let mut j = i;                          // 次数: n - 1
        // 考虑到下面的评估次数受到数组的实际影响，我们简单表达:
        // 设 t_i 为本次内循环中while条件的评估次数
        // 要注意: 内循环的评估次数并不代表消耗次数，因为其要受到外循环的影响
        while j > 0 && arr[j] < arr[j - 1] {    // 次数: \sum_{i=1}^{n-1} t_i
            arr.swap(j, j - 1);                 // 次数: \sum_{i=1}^{n-1} (t_i - 1)
            j -= 1;                             // 次数: \sum_{i=1}^{n-1} (t_i - 1)
        }
        // 注: t_i在最优情况下为1(数组已排序)，在最坏情况下为i+1(数组恰为倒序排序)
    }
}

每一步操作的实际消耗是代价乘上对应的次数，我们用 $T$ 代表一个算法(或操作)的运行时间，同时对这种形式我们加之 n 等参数使表示更为精准( $t_{i}$ 对于输入情况的解释非常复杂)，那么有: $T (n) = c_{1} (n - 1) + c_{2} (n - 1) + c_{3} (i = 1 \sum n - 1 t_{i}) + c_{4} (i = 1 \sum n - 1 (t_{i} - 1)) + c_{5} (i = 1 \sum n - 1 (t_{i} - 1))$ 接着我们代入t_i最值，于是有:

最优情况: $T (n) = c_{1} (n - 1) + c_{2} (n - 1) + c_{3} (n - 1) = (c_{1} + c_{2} + c_{3}) n + (c_{1} + c_{2} + c_{3})$ 观察后可以发现， $c_{i}$ 属于基本操作，所以 $(c_{1} + c_{2} + c_{3})$ 是常数，不难得 $T (n)$ 是关于 $n$ 的线性函数¹。

最坏情况:

最坏情况下，注意到 $i = 1 \sum n - 1 t_{i} = i = 1 \sum n - 1 (i + 1) = \frac{n ( n + 1 )}{2} - 1$ 和 $i = 1 \sum n - 1 (t_{i} - 1) = i = 1 \sum n - 1 i = \frac{n ( n - 1 )}{2}$ 同样我们代入变形: $T (n) = \frac{c _{3} + c _{4} + c _{5}}{2} n^{2} + (c_{1} + c_{2} + \frac{c _{3} - c _{4} - c _{5}}{2}) n - (c_{1} + c_{2} + c_{3} - \frac{c _{4} + c _{5}}{2})$ 很显然，这是一个二次函数。

在分析插入排序时，我们既研究了最佳情况，其中输入数组已排好序，又研究了最坏情况，其中输入数组已反向排好序。然而，在本书的余下部分中，我们往往集中于只求最坏情况运行时间，即对规模为n的任何输入，算法的最长运行时间。下面给出这样做的三点理由:

一个算法的最坏情况运行时间给出了任何输入的运行时间的一个上界。知道了这个界，就能确保该算法绝不需要更长的时间。我们不必对运行时间做某种复杂的猜测并可以期望它不会变得更坏。
对某些算法，最坏情况经常出现。例如，当在数据库中检索一条特定信息时，若该信息不在数据库中出现，则检索算法的最坏情况会经常出现。在某些应用中，对缺失信息的检索可能是频繁的。
“平均情况”往往与最坏情况大致一样差。假令输入为一半排序一半逆序，分析之后同样是一个二次函数。

在某些情况下，平均情况与最坏情况还是有较大差别的(事实上，对于大部分算法，我们并不明确什么是平均情况，有时候需要大量的概率分析来进行评估)，同时对于随机情况的出现也并不明确，我们将在后面的内容探讨这些。但首先我们要对这些算法的增长情况进行简单描述:

增长量级

对于像上面这个二次函数，数据较大时，常数项和一次项对增长率的影响不大，所以我们忽略这些内容之后只剩下最重要的 $n^{2}$ 。我们记插入排序的一般时间复杂度(抽象运行时间)为 $Θ (n^{3})$ 。 $Θ$ ²一般用来指代平均情况，它的值介于最坏情况和最优情况之间。这通常意味着存在输入使得运行时间达到且所有输入的最坏时间不超过。相当于在最坏情况下，运行时间恰好是 $Θ$ 所描述的。在很多课本中我们使用 $O$ 来描述，这其实没有 $Θ$ 精准， $O$ 代表着运行时间的上界，但不一定存在一个输入能达到这个上界， $Θ$ 则必然存在。关于 $Θ$ 的严格定义将在后面讲到。

增长量级其实是一类数学问题，量化了函数在无穷远处的增长行为。

在后面的内容中，我们非形式化的使用 $Θ$ 。

练习与回答

用 $Θ$ 记号表示函数 $f (n) = \frac{n ^{3}}{1000} - 100 n^{2} - 100 n + 3$ 。

在这里我们不采用严格的数学证明。

记住最高阶项决定一切，忽视系数和低次项直接得到答案—— $Θ (n^{3})$ 。

考虑排序存储在数组A中的n个数: 首先找出A中的最小元素并将其与A[1]中的元素进行交换。接着，找出A中的次最小元素并将其与A[2]中的元素进行交换。对A中前n-1个元素按该方式继续。该算法称为选择排序算法。
1. 写出其Rust代码。
2. 该算法维持的循环不变式是什么？
3. 为什么只需要对前n-1个元素，而不是对所有n个元素运行？
4. 用 $Θ$ 记号给出选择排序的最好情况与最坏情况运行时间。

1. Rust代码

fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n - 1 { // 只需遍历前 n-1 个元素
        let mut min_index = i;
        for j in i + 1..n { // 在剩余部分中寻找最小元素
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        if min_index != i { // 交换当前元素与最小元素
            arr.swap(i, min_index);
        }
    }
}

2. 循环不变式

在每次外层循环开始时，子数组A[0..i]已经是有序的，并且其中的所有元素 ≤ 子数组A[i..n]中的元素。

3. 为什么只需对前`n-1`个元素运行

数学原因

当对前n-1个元素排序后，最后一个元素A[n-1]必然是剩余子数组A[n-1..n]的最小也是唯一的元素，因此整个数组已经有序。

算法效率

减少一次不必要的遍历，但时间复杂度不变。

4. 时间复杂度分析

$i = 0 \sum n - 2 (n - 1 - i) = \frac{n ( n + 1 )}{2} = Θ (n^{2})$ 选择排序的时间复杂度在所有情况下均为 $Θ (n^{2})$ 。

再次考虑线性查找问题(参见这里)。用 $Θ$ 记号给出线性查找的平均情况和最坏情况运行时间。

最坏情况比较简单: $T_{worst} (n) = Θ (n)$ 平均情况要分析:

假设目标元素一定存在于数组中，且出现在每个位置的概率均等即( $P (v = A [i]) = \frac{1}{n}$ )。

比较次数的期望值: $E = k = 1 \sum n (第 k 次找到的概率 \times k) = k = 1 \sum n (\frac{1}{n} \times k) = \frac{1}{n} \cdot \frac{n ( n + 1 )}{2} = \frac{n + 1}{2}$ 则 $T_{avg} (n) = Θ (n)$

这里的线性函数并不是高等数学中的严格定义。《算法导论》中，使用的是初等数学中的宽松定义(即形如 $f (x) = k x + b$ 的一次函数)。对于高等数学来说，上面的函数既不满足齐次性，又不满足叠加性(当 $(c_{1} + c_{2} + c_{3})$ 为0时，原函数变化成零函数，满足线性要求，但显然不为0)。由于 $b = c_{1} + c_{2} + c_{3} \neq = 0$ 所以该函数更准确的叫仿射函数。 ↩
希腊语中的第8个字母，读作 theta。 ↩

分治法

我们可以选择使用的算法设计技术有很多。插入排序使用了增量方法。本节我们考查另一种称为“分治法”的设计方法。分治算法通过递归拆分问题，显著降低时间复杂度，是算法设计中的重要范式。

许多有用的算法在结构上是递归¹的: 为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想: 将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治法通过下面的这些步骤解决问题:

分解(Divide): 将原问题划分为多个规模较小的子问题(通常与原问题结构相同)。
解决(Conquer): 递归地解决子问题。若子问题规模足够小，则直接求解²。
合并(Combine): 将子问题的解合并为原问题的解。

可以看出分治主张 “分而治之” 的哲学，形式上一般通过递归来解决问题，它的子问题是独立、不重叠的。

我们将用分治法来设计一个排序算法，该算法的最坏情况运行时间比插入排序要少得多。

归并排序

我们来看一个很早就接触过的主问题:

输入

$n$ 个数的数组 $< a_{1}, a_{2}, \dots, a_{n} >$

输出

输入数组的升序排列 $< a_{1}^{'}, a_{2}^{'}, \dots, a_{n}^{'} >$ ，满足 $a_{1}^{'} \leq a_{2}^{'} \leq \dots \leq a_{n}^{'}$

对于这个问题，我们进行分割将数组分割成两个n/2的子数组(实际上，n/2会被截断小数部分，所以当n为奇数时，右半部分(right)会多出一个元素³)，然后对这两个子数组重复上面分割。不可分割时，需进行排序，然后合并已排序的数组。这是一个先自上而下分解问题，再**逐步回升(自底向上)**解决问题的过程。

实现1

pub fn realize<T: Ord + Clone>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return; // 基本情况: 数组长度为0或1时直接返回
    }

    let mid = arr.len() / 2;
    let mut left = arr[..mid].to_vec(); // 分割左半部分
    let mut right = arr[mid..].to_vec(); // 分割右半部分

    // 递归排序左右子数组
    merge_sort(&mut left);
    merge_sort(&mut right);

    // 合并排序后的左右子数组
    merge(arr, &left, &right);
}

// 合并两个有序数组的辅助函数
fn merge<T: Ord + Clone>(arr: &mut [T], left: &[T], right: &[T]) {
    let (mut i, mut j, mut k) = (0, 0, 0);

    // 比较左右子数组的元素，按顺序合并到原数组
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }

    // 处理剩余元素(左子数组或右子数组可能未完全合并)
    while i < left.len() {
        arr[k] = left[i].clone();
        i += 1;
        k += 1;
    }
    while j < right.len() {
        arr[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

在合并两个有序数组中，由于两个数组都已排序，所以我们就要从中观察两个数字的首项，找到较小的项加入新数组，这个过程中保证了新数组有序。其中一个子数组全部排完后，直接将剩下的有序数组放入新数组。我们来观察一组输入:

1 2 4
3 7 8

它的变化过程是这样的:

1.
left: 2 4
right: 3 7 8
new: 1
2.
left: 4
right: 3 7 8
new: 1 2
3.
left: 4
right: 7 8
new: 1 2 3
4.
left: 
right: 7 8
new: 1 2 3 4
5. (将剩下数组放入)
left:
right:
new: 1 2 3 4 7 8

当然，这只是一种思维方式。实际的实现中，我们通常不改变左右数组，而是简单的通过一个索引来从中获取数据并模拟扔出数据的过程。这个过程需要遍历两个数组的所有元素，所以它是 $Θ (n)$ ⁴的。

《算法导论》中，将左右数组的最后一项设为 $\infty$ ，只需要遍历到 $\infty$ 就意味着其中一个数组已经遍历完，不需要像实现一一样检查剩余元素。这里用于简化边界条件的 $\infty$ 便是哨兵值。

哨兵(Sentinel) 是一种用于简化算法边界条件的编程技巧。它通常是一个特殊的值或节点，用于标记数据结构的边界，从而避免在循环或递归中频繁检查边界条件，提升代码的简洁性和效率。

在Rust我们做不到使用 $\infty$ ，哪怕用Default::default也会导致数据冲突(如数字0)，所以我们不采用哨兵值。如果你认为你的数据里不会产生0或-1这样的值，那加上哨兵值也是可取的。

练习与回答

试给出归并排序的循环不变式并证明。

循环不变式

在MERGE(辅助函数)过程的while i < left.len() && j < right.len()循环的每次迭代开始时，子数组 A[p..k-1](即arr) 包含 L[1..i-1] 和 R[1..j-1] (即 left 和 right)中的 k-p 个最小元素，并且 A[p..k-1] 是有序的。进而，L[i] 和 R[j] 是各自数组中未被复制回 A 的最小元素。

证明

初始化

在循环开始之前，k = p，因此A[p..k-1]是空的，即不包含任何元素。i = 1和j = 1，所以L[1..i-1]和R[1..j-1]也是空的。因此，A[p..k-1]包含0个最小元素，且是有序的。L[1]和R[1]分别是L和R中未被复制的最小元素(因为还没有任何元素被复制)。因此，初始化时循环不变式成立。

保持

假设在循环的某次迭代开始时，循环不变式成立。即A[p..k-1]包含L[1..i-1]和R[1..j-1]中的k-p个最小元素，且A[p..k-1]是有序的。L[i]和R[j]是各自数组中未被复制的最小元素。

在循环体中，我们比较L[i]和R[j]：

如果L[i] ≤ R[j]，则将L[i]复制到A[k]，然后i和k都加 1。
- 因为L[i]是L中未被复制的最小元素，且L[i] ≤ R[j]，所以L[i]是L和R中未被复制的最小元素。
- 将L[i]放入A[k]后，A[p..k]现在包含L[1..i]和R[1..j-1]中的 $k - p + 1$ 个最小元素，且是有序的。
- L[i+1]和R[j]现在是各自数组中未被复制的最小元素。
如果L[i] > R[j]，则将R[j]复制到A[k]，然后j和k都加 1。
- 类似地，R[j]是R中未被复制的最小元素，且R[j] < L[i]，所以R[j]是L和R中未被复制的最小元素。
- 将R[j]放入A[k]后，A[p..k]现在包含L[1..i-1]和R[1..j]中的 $k - p + 1$ 个最小元素，且是有序的。
- L[i]和R[j+1]现在是各自数组中未被复制的最小元素。

因此，在每次迭代后，循环不变式仍然成立。

终止

当循环终止时，k = r + 1。根据循环不变式，A[p..k-1]即A[p..r]包含L[1..i-1]和R[1..j-1]中的 $r - p + 1$ 个最小元素，且是有序的。因为L和R总共有 $n 1 + n 2 = r - p + 1$ 个元素，所以A[p..r]包含了L和R的所有元素，且是有序的。

递归(Recursion) 是算法设计中的一种重要技术，指函数或过程直接或间接调用自身来解决问题的方法。 ↩
这种可直接求解的边界叫做基线条件(Base Case)。如实现一的基本情况。 ↩
这意味着右数组有 $⌈ n ⌉$ 个元素，左数组有 $⌊ n ⌋$ 个元素。其中 $⌈ x ⌉$ 表示大于或等于 $x$ 的最小整数， $⌊ x ⌋$ 表示小于或等于 $x$ 的最大整数。 ↩
这只是辅助函数的时间复杂度，归并排序的实际复杂度在后面解答。 ↩

分治法分析

了解了归并排序的实现原理和循环不变式，我们将要讨论归并排序的运行时间。

分而治之的特点是递归式的，所以我们一般采用分段函数，在 基线条件(Base Case) 和一般条件分别进行讨论。首先我们将数据规模定为 $n$ ，按照之前的定义，运行时间为 $T (n)$ 。对于一个常量 $c$ ， $n \leq c$ 时，可以直接求解，运行时间总为常数时间 $Θ (1)$ 。此时，基线条件就是 $n \leq c$ 。一般条件下，我们要将其分为多个子问题，假设分成 $a$ 个子问题，每个子问题的规模为原问题的 $\frac{1}{b}$ ，那么消耗的时间则为 $a T (\frac{n}{b})$ 。这个时候再加上合并( $C (n)$ )和分解问题( $D (n)$ )所需要的时间，就得到了递归式: $T (n) = {Θ (1) a T (\frac{n}{b}) + C (n) + D (n) if n \leq c, otherwise.$

假定归并排序的输入规模 $n$ 是 $2$ 的幂次，此时分解总产生两个规模均为 $n /2$ 的子问题，当 $n > 1$ (基线条件: $n \leq 1$ )时，有:

分解(Divide): 分解过程仅仅计算数组的中间项，需要常数时间，即 $D (n) = Θ (1)$ 。
解决(Conquer): 我们递归地求解两个规模均为 $n /2$ 的子问题，将贡献 $2 T (n /2)$ 的运行时间。
合并(Combine): 我们证过在一个具有 $n$ 个元素的子数组上过程MERGE(即辅助函数)需要 $Θ (n)$ 的时间，所以 $C (n) = Θ (n)$ 。

对于归并排序又恰知 $a = b = 2$ ，即有递归式: $T (n) = {Θ (1) 2 T (\frac{n}{2}) + Θ (n) if n \leq 1 这里也可为 n = 1, if n > 1$ 后面我们会学一个“主定理”，用它可得 $T (n) = Θ (n lo g n)$ ¹。

注: $Θ$ 和 $O$ 等渐进符号底数通常可以忽略，如

为了直观地理解上递归式的解为什么是 $T (n) = Θ (n lo g n)$ ，我们并不需要主定理。把上递归式重写为: $T (n) = {c 2 T (\frac{n}{2}) + c n if n = 1, if n > 1$ 其中常量 $c$ 代表求解规模为 $1$ 的问题所需的时间(等价于 $Θ (1)$ )，以及在分解步骤与合并步骤处理每个数组元素所需的时间。

该章节仍在编写，在 Github仓库上提交PR以为本书贡献内容。

这里省略了底数 $2$ ，即此处的 $lo g$ 等价于 $lo g_{2}$ 。除非另有明确说明，这是算法分析中的默认约定(而非数学中的)。许多高效算法通常将问题一分为二，计算机科学中许多操作基于二进制，故 $lo g$ 非常有效。 ↩

连续数学中的运算工具

连续数学(Continuous Mathematics) 研究连续变化的对象和现象，涉及无限可分、平滑过渡的数学结构。本章介绍连续数学中强有力的运算工具，以帮助算法分析(或提供特殊运算支持)。

求和

介绍数学中求和和求积相关知识，为算法的数学证明提供帮助。

求和意义和性质

求和意义和性质

当一个算法包含循环控制结构时，例如while或者for循环，我们可以将算法的运行时间表示为每一次执行循环体所花时间之和。通过累加每次迭代所用时间，可以获得其和(或称级数)。

序号

在数学上，我们有一个求和序号——∑(英语名称: sigma，汉语名称：西格玛，是第十八个希腊字母)。

作用: 表示一系列数值的累加。

基本用法: $i = 1 \sum n i$

下标( $i = 1$ ): 起始序号，表示求和变量的起始值
上标( $n$ ): 终止序号，表示求和变量的终止值。
待求和的项( $i$ )

例: 给定一个数列 $a_{1}, a_{2}, \dots, a_{n}$ ,其中n是非负整数，可以将有限和 $a_{1} + a_{2} + \dots + a_{n}$ 写作: $i = 1 \sum n a_{i}$ 并且: $i = 1 \sum n a_{i} = a_{1} + a_{2} + \dots + a_{n}$ 让该数列无限延长( $a_{1}, a_{2}, \dots$ )，则有: $i = 1 \sum \infty a_{i} = a_{1} + a_{2} + \dots$ 即: $i \to \infty lim i = 1 \sum \infty$

当其极限不存在时，该级数¹发散；反之，该级数收敛。对于收敛级数，不能随意对其项改变求和顺序。而对于绝对收敛级数(若对于级数 $\sum_{i = 1}^{\infty} a_{i}$ 有级数 $\sum_{i = 1}^{\infty} ∣ a_{i} ∣$ 也收敛，则称其为绝对收敛级数)，则可以改变其项的求和顺序。

性质

线性性质

对于求和，我们有下面的两个基本线性性质: $k = 1 \sum n (a_{k} + b_{k}) = k = 1 \sum n a_{k} + k = 1 \sum n b_{k}$ $k = 1 \sum n c \cdot a_{k} = c \cdot k = 1 \sum n a_{k} (c 为常数)$ 将两个综合起来就有: 对于任意实数 $c$ 和任意有限序列 $a_{1}, a_{2}, \dots, a_{n}$ 和 $b_{1}, b_{2}, \dots, b_{n}$ ，有 $k = 1 \sum n (c \cdot a_{k} + b_{k}) = c \cdot k = 1 \sum n a_{k} + k = 1 \sum n b_{k}$ 注: 线性性质对于无限收敛级数同样适用。线性性质可以用来对项中包含渐近记号的和式求和。

等差级数

等差数列的前 $n$ 项和称为一个等差级数²，也叫算术级数。常见的有: $k = 1 \sum n k = 1 + 2 + 3 + \dots + n$ 用高斯求和，得 $k = 1 \sum n k = \frac{n ( n + 1 )}{2} = Θ (n^{2})$

该章节仍在编写，在 Github仓库上提交PR以为本书贡献内容。

编程中使用

pub fn sigma_sum(start: i32, end: i32, f: impl Fn(i32) -> i32) -> i32 {
    // 这里利用rayon还可以并行计算，对大数据很有用
    (start..=end)   // 生成一个包含结束值(闭合)的迭代器
        .map(f)     // 对迭代器每一个项获取求和数据
        .sum()      // 完成求和
}

// example-test
sigma_sum(1, 5, |x| x * x)  // 输出1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 + 5 ^ 2的和

对于算术级数可以利用高斯求和，时间复杂度从\Theta(n)降低到\Theta(1):

pub fn gauss_sum(start: i64, end: i64) -> i64 {
    // 先除后乘，防止中间溢出
    if (start + end) % 2 == 0 {
        (start + end) / 2 * (end - start + 1)
    } else {
        (end - start + 1) / 2 * (start + end)
    }
}

级数是无穷数列的和。即形如: $\sum_{i = 1}^{\infty} a_{i} = a_{1} + a_{2} + \dots$ ↩
“等差级数”在无穷情形下通常不被视为严格定义的级数，除非明确讨论其发散性。 ↩

幂与对数

幂

幂是指将一个数(底数)自乘若干次(由指数决定)的运算。其一般形式为 $a^{n}$ ，表示 $a$ 乘以自身 $n$ 次。

如 $1 0^{3} = 10 \times 10 \times 10 = 1000$ 中， $10$ 是底数， $3$ 是指数。

不同指数的幂有特性:

正整数指数

域: $n \in N^{+}$ ¹
定义: $a^{n} = a \times a \times \dots \times a$
性质:
- $a^{m} \times a^{n} = a^{m + n}$
- $(a^{m})^{n} = a^{mn}$
- $a^{n} \times b^{n} = (a + b)^{n}$
- $a^{m} / a^{n} = a^{m - n}$

零指数

域: $n = 0$
定义: $a^{0} = 1 (a \neq = 0)$
注:
- 这是为了保持幂运算的连续性，例: $a^{m} / a^{m} = 1 = a^{0}$ ，确保像这类运算可以正常执行。
- $0^{0}$ 未定义的。(某些情况下等于一 $1$ 但不推荐使用)

负整数指数

域: $n \in Z^{-}$
定义: $a^{n} = \frac{1}{a ^{- n}}$
注:
- 负指数表示倒数。
- 这是为了扩展幂运算的定义域，使其在整数范围内封闭。

分数指数

域: $n = \frac{p}{q} 其中 p, q \in Z, q \neq = 0$
定义: $a^{\frac{p}{q}} = (q a)^{p}$

注: 分数指数的本质是将幂运算延拓到有理数集。这里的推广基于正整数指数的性质: $(a^{m})^{n} = a^{mn}$ :

如果分数指数要满足该性质，我们可以用一个简单的式子: $(a^{\frac{1}{q}})^{q} = a^{(\frac{1}{q} \times q)} = a$ 看前面的一项 $设 x = (a^{\frac{1}{q}}), 则 x^{q} = a ∵ (q a)^{q} = a ∴ x = q a 即 a^{\frac{1}{q}} = x = q a$ 再利用 $(a^{m})^{n} = a^{mn}$ ，不难得到 $a^{\frac{p}{q}} = a^{\frac{1}{q} \times p} = (q a)^{p}$ 。

无理指数

域: $n \in R / Q$
注: 无理指数将幂运算延拓到实数甚至复数集。

定义: 设 $a > 0$ 是一个正实数， $α$ 是一个无理数。选取一个有理数序列 ${r_{n}}$ 使得 $lim_{n \to \infty} r_{n} = α$ ，则无理指数 $a^{α}$ 定义为: $a^{α} = n \to \infty lim a^{r_{n}}$ 这个方法的本质是通过有理数无限逼近一个无理数来进行。我们也可以通过指数函数来进行延拓，此处不再赘述。

编程中使用

一般来讲，我们将设计的幂算法只支持自然数。更广的作用域，在编程中通常不使用。接下来我们开始设计:

从定义出发，我们不难想到只需要对一个基数进行循环n次，每次乘它自身，便可得到:

pub fn power_iter(base: i64, exponent: u32) -> i64 {
    // 下面省略溢出检测
    let mut result = 1;
    for _ in 0..exponent {
        result *= base;
    }
    result
}

它的时间复杂度是 $Θ (n)$ ，对于较大的输入规模，这个算法可能并不特别好。我们还有一种名为快速幂的方法:

fn power_fast(mut base: i64, mut exponent: u32) -> i64 {
    let mut result = 1;
    while exponent > 0 {
        if exponent % 2 == 1 {
            result *= base;
        }
        base *= base;
        exponent /= 2;
    }
    result
}

它采用分治法的策略，时间复杂度是 $Θ (lo g n)$ 。其数学基础是对于输入规模 $n$ ，如果它是偶数，那么 $a^{n} = (a^{2})^{n /2}$ ，如果它是奇数，那么 $a^{n} = a (a^{2})^{(n - 1) /2}$ 。快速幂算法实际上是在利用指数的二进制表示: $13 = 110 1_{2} = 8 + 4 + 1 = 2^{3} + 2^{2} + 2^{0} 3^{13} = 3^{(8 + 4 + 1)} = 3^{8} \times 3^{4} \times 3^{1}$ ²

所以完全可以用位运算:

fn power_fast(mut base: i64, mut exponent: u32) -> i64 {
    let mut result = 1;
    while exponent > 0 {
        if exponent & 1 == 1 {  // 等价于 exponent % 2 == 1
            result *= base;
        }
        base *= base;
        exponent >>= 1;  // 等价于 exponent /= 2
    }
    result
}

利用std中pow可以直接进行幂运算:

let base = 2;
let exponent = 3;
let result = base.pow(exponent); // 2^3 = 8

对数

对数(Logarithm) 是数学中用于简化乘除运算的一种函数，定义为幂运算的逆运算。具体来说，如果满足以下等式: $a^{b} = N (a > 0, a \neq = 1)$ 那 $b$ 就是以 $a$ 为底 $N$ 的对数，记作: $b = lo g_{a} N$ 其中， $a$ 为底数( $a > 1$ )， $N$ 为真数( $N > 0$ )。在上面这两个式子中，我们可以得到对数与指数的关系: $lo g_{a} N = b ⟺ a^{b} = N$ 我们常用几种特殊的对数:

$10$ : 常用对数。 $lo g_{1} 0$ (可以简写为 $l g$ )，用于科学计算和工程。
$e$ : 自然对数。 $lo g_{e}$ (可以简写为 $ln$ )，广泛用于微积分和自然科学。
$2$ : 二进制对数。 $lo g_{2}$ (仅在计算机科学中，我们可以简写为 $lo g$ )，常见于计算机科学和信息论。

性质

对数的运算有很多特殊的性质:

乘法性质

性质：
$lo g_{a} (MN) = lo g_{a} M + lo g_{a} N (M, N > 0)$

证明：
设 $x = lo g_{a} M$ ， $y = lo g_{a} N$ ，则：
$a^{x} = M, a^{y} = N$
两式相乘：
$a^{x} \cdot a^{y} = MN ⟹ a^{x + y} = MN$
取对数得：
$lo g_{a} (MN) = x + y = lo g_{a} M + lo g_{a} N$
证毕。

除法性质

性质：
$lo g_{a} (\frac{M}{N}) = lo g_{a} M - lo g_{a} N (M, N > 0)$

证明：
设 $x = lo g_{a} M$ ， $y = lo g_{a} N$ ，则：
$a^{x} = M, a^{y} = N$
两式相除：
$\frac{a ^{x}}{a ^{y}} = \frac{M}{N} ⟹ a^{x - y} = \frac{M}{N}$
取对数得：
$lo g_{a} (\frac{M}{N}) = x - y = lo g_{a} M - lo g_{a} N$
证毕。

幂运算性质

性质：
$lo g_{a} (M^{k}) = k lo g_{a} M (M > 0, k \in R)$

证明：
设 $x = lo g_{a} M$ ，则：
$a^{x} = M ⟹ (a^{x})^{k} = M^{k} ⟹ a^{k x} = M^{k}$
取对数得：
$lo g_{a} (M^{k}) = k x = k lo g_{a} M$
证毕。

换底公式

性质：
$lo g_{a} N = \frac{lo g _{b} N}{lo g _{b} a} (a, b, N > 0, a, b \neq = 1)$

证明：
设 $x = lo g_{a} N$ ，则：
$a^{x} = N ⟹ lo g_{b} (a^{x}) = lo g_{b} N ⟹ x lo g_{b} a = lo g_{b} N$
解得：
$x = \frac{lo g _{b} N}{lo g _{b} a}$
即：
$lo g_{a} N = \frac{lo g _{b} N}{lo g _{b} a}$
证毕。

特殊值性质

性质1：
$lo g_{a} 1 = 0$
证明：
由 $a^{0} = 1$ ，根据定义：
$lo g_{a} 1 = 0$
证毕。

性质2：
$lo g_{a} a = 1$
证明：
由 $a^{1} = a$ ，根据定义：
$lo g_{a} a = 1$
证毕。

对数将复杂的乘除、幂运算转化为加减乘除，是数学和科学中不可或缺的工具。

在编程中使用

其实在幂那里我们就已经知道了——由于计算机的二进制特性，利用位运算我们可以计算整数以 $2$ 为底的对数:

pub fn log2_bitwise(n: u32) -> u32 {
    // 下面省略数据校验
    31 - n.leading_zeros()
}

位操作法 的核心思想是一个整数的二进制表示中，最高有效位(MSB)的位置即为其以2为底的对数。n.leading_zeros() 返回n的二进制表示中前导零³的个数。u32的二进制长度是32，由于位置编号从0开始(范围是0~31)，所以最高有效位是31 - leading_zeros。对于其他底数，我们也可以使用牛顿迭代法:

pub fn log_newton(x: f64, base: f64, epsilon: f64) -> f64 {
    // 下面省略数据校验
    let mut y = (x.ln() / base.ln()).max(0.0); // 初始猜测
    loop {
        let next_y = y - (base.powf(y) - x) / (base.powf(y) * base.ln());
        if (next_y - y).abs() < epsilon {
            return next_y;
        }
        y = next_y;
    }
}

牛顿迭代法 是一种用于近似求解方程 $f (x) = 0$ 的根的高效数值方法。其主要通过切线逼近逐步修正解的近似值。从一个初始猜测值 $x_{0}$ 开始。用当前点 $(x_{n}, f (x_{n}))$ 的切线（导数）更新 $x_{n + 1}$ : $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ 重复迭代，直到 $∣ x_{n + 1} - x_{n} ∣$ 小于预设精度 $ϵ$ ⁴。

利用std中相关方法可以直接进行对数运算:

// log
let five = 5.0f32;
// log5(5) - 1 == 0
let abs_difference = (five.log(5.0) - 1.0).abs();

// log2
let two = 2.0f32;
// log2(2) - 1 == 0
let abs_difference = (two.log2() - 1.0).abs();

// log10
let ten = 10.0f64;
// log10(10) - 1 == 0
let abs_difference = (ten.log10() - 1.0).abs();

// ln
let one = 1.0_f64;
// e^1
let e = one.exp();
// ln(e) - 1 == 0
let abs_difference = (e.ln() - 1.0).abs();

练习与回答

试证明一个整数的二进制表示中，最高有效位(MSB)的位置即为其以2为底的对数。

证明

命题：对于正整数 $n$ ，其二进制最高有效位的位置 $k$ 满足: $k = ⌊ lo g_{2} n ⌋$

证明：

设 $n$ 的二进制表示为: $n = b_{k} \cdot 2^{k} + b_{k - 1} \cdot 2^{k - 1} + \dots + b_{0} \cdot 2^{0} (b_{k} = 1)$

因为 $b_{k} = 1$ ，所以: $2^{k} \leq n \leq 2^{k + 1} - 1 < 2^{k + 1}$

对不等式取 $lo g_{2}$ : $k \leq lo g_{2} n < k + 1$

因此: $k = ⌊ lo g_{2} n ⌋$

见集合。 $N^{+}$ 有时也用 $Z^{+}$ 。 ↩
$110 1_{2}$ 中的 $_{2}$ 表示二进制形式，同理 $_{16}$ 是十六进制。 ↩
前导零(Leading Zeros) 是指一个数的二进制表示中，从最高位开始连续出现的零，直到遇到第一个1为止。 ↩
$ϵ$ (epsilon) 是希腊字母表的第5个字母。表示任意小的正数，用于量化“无限接近”的概念。计算机科学中向如上迭代算法中也可表示停止阈值，一般用常量(如const EPS = 0.000001)。 ↩

离散数学相关

离散数学(Discrete Mathematics) 研究可数、分离的对象，强调不连续性和有限性或可数无限性。计算机科学的数学基础主要在于离散数学(但目前还离不开连续数学的工具，如有需要请前往连续数学中的运算工具学习相关内容)。本章将介绍离散数学中的一些定义和性质，这些内容我们在其他章节中也肯定会提到，主要作为补充和回顾，可以粗略阅读。

集合

集合

该章节仍在编写，在 Github仓库上提交PR以为本书贡献内容。

PR贡献指南

通过以下文档了解如何贡献:

文档语法

本书基于 mdBook，一脉相传地继承了 CommonMark 的语法，标准如下:

文本和段落

文本1，文本2

一个段落

段落间要求空行
简单换行会变为空格

渲染

文本1，文本2

一个段落

段落间要求空行简单换行会变为空格

标题

标题使用#标记，并且应该单独占一行。更多的#表示更小的标题:

文本和段落可在标题前
#### A
文本和段落可在两标题间
#### B

空行不影响渲染

#### C
文本和段落可在两标题后

##### 更小标题

渲染

文本和段落可在标题前

A

文本和段落可在两标题间

B

空行不影响渲染

C

文本和段落可在两标题后

更小标题

注

建议#数量在 1 至 5 间。
标题应明显分割内容以增强阅读体验。
是否空行取决于语意关系。

列表

列表可以是无序的或有序的，有序列表将自动排序:

#### 无序写法1(方形)
* 换行不影响
* 换行不影响

* 换行
不影响
#### 无序写法2(圆形)
- 换行不影响
- 换行不影响

- 换行
不影响

#### 有序写法1
1. 换行不影响

1. 换行不影响
1. 换行
不影响
#### 有序写法2
1. 换行不影响
2. 换行不影响

3. 换行
不影响

列表支持嵌套:
1. 有序写法
    1. A
    2. B
    3. C
2. 无序写法
    * 1
        - 1
        - 2
        - 3
    * 4
        1. A
        2. B

渲染

无序写法1(方形)

换行不影响
换行不影响
换行不影响

无序写法2(圆形)

换行不影响
换行不影响
换行不影响

有序写法1

换行不影响
换行不影响
换行不影响

有序写法2

换行不影响
换行不影响
换行不影响

列表支持嵌套:

有序写法
1. A
2. B
3. C
无序写法
- 1
  - 1
  - 2
  - 3
- 4
  1. A
  2. B

注

推荐用有序写法2和无序写法2(圆形)

链接

链接到 URL 或本地文件很简单:

本书用 [mdBook](https://github.com/rust-lang/mdBook)。

你可阅读 [README](./README.md) 来了解PR方式。

(直接用不影响)

[直接用不影响]

(本地路径采用相对，不应超出src的范围)

裸链接: <https://rust-lang.github.io/mdBook/format/markdown.html>

渲染

本书用 mdBook。

你可阅读 README 来了解PR方式。

(直接用不影响)

[直接用不影响]

(本地路径采用相对，不应超出src的范围)

裸链接: https://rust-lang.github.io/mdBook/format/markdown.html

注意

以.md结尾的相对链接将被转换为.html扩展名。建议尽可能使用.md链接。这在 Markdown 文件在 mdBook 外部查看时很有用，例如在 GitHub 或 GitLab 上，这些平台会自动渲染 Markdown。
链接到README.md将会被转换为index.html。这是因为在某些服务(如 GitHub)中，它们会自动渲染 README 文件，而网页服务器通常期望根文件被称为index.html。
用#链接到各个标题，如文本和段落 ([文本和段落](#文本和段落)) 和 PR贡献指南 ([PR贡献指南](./README.md#PR贡献指南))

图片

包含图片只需包含指向它们的链接(URL或本地文件)，就像上面链接部分一样:

![License](https://img.shields.io/github/license/TickPoints/algorithm_learning)

渲染

License

加粗

文本可以通过在每个侧面包裹两个星号来渲染:

**加粗**

加粗

代码

通过在文本两侧添加反引号从而在单行中获取代码段，推荐为数字(如`1`)和小型代码片段(如`while`)添加。

通过三个连续的反引号(```)来创造代码框，在首三个连续的反引号后添加如rs(Rust)，md(Markdown)，text来控制语言和渲染逻辑。

渲染

通过在文本两侧添加反引号从而在单行中获取代码段，推荐为数字(如1)和小型代码片段(如while)添加。

通过三个连续的反引号(```)来创造代码框，在首三个连续的反引号后添加如rs(Rust)，md(Markdown)，text来控制语言和渲染逻辑。

mdBook 在标准 CommonMark 规范之外有几个扩展:

删除线

文本可以通过在每个侧面包裹两个波浪号来渲染:

你好，Rust~~世界~~!

渲染

你好，Rust世界!

脚注

脚注会在文本中生成一个小编号的链接，点击后会将读者带到该项底部的脚注文本¹。脚注标签的写法类似于链接引用，前面有一个尖角符号。

脚注会在文本中生成一个小编号的链接，点击后会将读者带到该项底部的脚注文本[^note1]。脚注标签的写法类似于链接引用，前面有一个尖角符号。

[^note1]: 必须放在文档底部。

注意

推荐以[^noteX]的格式书写。

表格

阅读Github的表格扩展规范

数学公式

我们采用mdBook-KaTeX渲染LaTex数学表达式。而不使用mdBook自带的MathJax支持以避免一些问题并增强体验。

一般格式如下:

行内: $ f(x) = ax^2 + bx + c$

全行:
$$
f(x) = x^2 \\
x \in \R
$$

用`\$`而正常显示\$

渲染

行内: $f (x) = a x^{2} + b x + c$

全行: $f (x) = x^{2} x \in R$

用\$而正常显示$

注

以上内容为编写文档时可能用到的所有语法，更多语法可参见其他地方(如Github文档)，上面有很多推荐，文档编写者应该尽量满足，同时严格的编写语法是必须满足的。

必须放在文档底部。 ↩

PR规范

标准流程

首先获取已有内容，您可以尝试 Fork 当前仓库，然后克隆自己的新仓库，接着像您为别的仓库提供PR一样即可。

或者，直接在Github中修改内容并提交。

如何编辑

该写点什么

根据《算法导论》的相关内容，设计章节和准备代码，接着用中文书面语表述出来。在这里您可以有自己的语言习惯，但不要过于口语化，使用朴素的陈述口气会更符合本书一贯的风格。( 但如果您想要这样的也可以哦:)

首先不要一律照搬《算法导论》相关内容，任何伪代码都不应该在本书中出现。本书的定位是一本轻教材，但一般的话，您可以把它理解为一本学习笔记。编写本书的时候贯彻教学相长的思想，参考其他的章节，您可以领会到这种意味。

其次，应该使用Rust语言来完成伪代码，对于不太严格的完成，需要解释原因，但同时要保证本书的知识点。如果因为对伪代码不太严格的完成导致知识点被忽略，应该自然地衔接补充。

目录格式

这里介绍的是如何创建新文档。

首先要明确非必要不引入新文档，如有必要按照特殊情形。

文档与算法导论相对应。通常1~3个文档与算法导论的一节大知识相对应。部分特殊文档(如本文档之类的)一般在前期工作就被创建，且后期将不能再创建。您可以合理的分割算法导论的一节大知识，以准备编写。通常不建议跨章节创建文档(即上一个章节还没完全创建下一个章节的内容)。

接下来需要给定名称，章节名总是由作者给定，但单个文档名可以您来给定。一般需要一个英文名(仅包含小写字母和下划线)和一个中文名称。在src/SUMMARY.md中找到合理的位置，放置您的文档，格式参考SUMMARY.md。

该行为容易导致文档崩溃，在没有前期经验的情况下，很容易出错。所以我们将其归为不推荐行为。

完成之后，提交即可(对于空文档请参考文档补充)。

注: 一般来说我们也推荐在您提交文档所在章节的README.md中放置索引。

文档补充

如果您在编写文档的过程中，认为编写周期过长(比方说准备长期的空文档)，那么可以先停下来，在合理的位置留下下面这个注:

> 该章节仍在编写，在 [Github仓库](https://github.com/TickPoints/algorithm_learning) 上提交PR以为本书 [贡献内容](/pr_guide/pr_standard.md)。

接着提交PR即可。

如果您是想为本书进行补充，那么直接在当前页面点击标签栏的Edit图标就可以直接进入编辑模式(或是参考标准流程)。

Edit图标

补充或修改一般是较小行为，不建议大动作的更改(如果您需要一个标准，那么80行以上的更改可以被称为这个)，这类PR一般会被快速通过。

内容排布

严格的可以参考导论匹配，一般情况下阅读前面的文档就够了。

特殊情形

不推荐行为:

引入新文档
引入图片
修改src/not-found.md
删除文件
修改 src以外的一切
修改任何README.md文件

在编写中，我们常常不应进行上面提到的任何一个不推荐行为，在没有必要的情况下，永远不要去做它们。但如果有必要，您就要遵循这些规则:

任何不推荐行为的PR，都应该事先说明。如果您做了这些不推荐行为，必须在提交的时候告知。
任何不推荐行为的PR，都需要issue作支持，您可以自己提issue或是使用他人的issue。issue提出的一段合理时间后再进行PR。在这段过程中，简单的行为或不应当的行为可能会被指出。对于简单的行为(如仅仅只是创建一个空的新页面)，其它作者将帮助您完成。而对于不应当的行为，您就不能进行PR，保持冷静对待，可以尝试迂回的解决，这可以避免不必要的麻烦。(一定记得等段一段适当时间，防止在PR提出之后才被否决，造成浪费)

导论匹配

下面所介绍的内容均是指正式文档(不包括引言和PR贡献指南)

结构(标题格式)

每一个文档只允许有且只有一个主标题，即直接使用单个#引导的标题，如:

# 导论匹配

这个标题必须在文档开头，且总是要求与Summary相对应。一般来说还与当前所在章节的README.md中的内容相对应，如:

# PR贡献指南
通过以下文档了解如何贡献:
- [文档语法](./document_syntax.md)
- [PR规范](./pr_standard.md)
- [导论匹配](./introductory_match.md)

剩下的标题中必须有## 练习与回答，推荐在前面加上---用来分割，如:

---
## 练习与回答

此外所有的代码实现都必须冠以标题，如:

### 实现一

代码格式

像PR规范中所说的那样，应该使用Rust语言来完成《算法导论》中的伪代码，对于特殊情况可以尝试迂回的实现。

对于一个实现的主函数，必须以realizeX命名(当X为1，允许省略)。附函数(如辅助函数)可以参照《算法导论》中的过程命名，但必须要符合Rust命名规范。

在PR前，您要保证:

您的代码在最新稳定的Rust编译器下通过编译，且不出现警告。
您的代码完成了《算法导论》中的伪代码逻辑。
您的代码能够对所有的输入得到一个有效的输出。
您的代码已经过格式化。

如果您能实现上面这些，将不胜感激。(注: 我们也推荐你能给出代码的循环不变式并证明以此证明算法正确性。同时对于部分文档需要给出证明，也可以避免其他作者额外的工作)

图片格式

任何可以渲染的图片均可，一般来说推荐.png、.jpg(.jpeg)，如果是网络照片(通过URL获取)请确保是合理安全来源，且拥有使用权限。如果是本地照片(提交到仓库)，要求符合以下命名格式:

对照文章(如有多篇取最重要的一篇)_图片意义(尽量短小)_后缀

如:

introductory_match_example.jpg

其次需要提前对图片进行压缩，然后随着PR提交即可。要注意这是不推荐行为。

如有侵权请联系，我们将马上删除照片。

Keyboard shortcuts

算法学习