算法学习

目的

用Rust实现《算法导论》第3版中的所有伪代码, 同时对一些例题进行解答. 本项目专为中文开发者设计, 旨在辅助算法学习与实践.

阅读

本书用mdBook, 阅读方法可参考 这里.

Note

阅读前请确保至少掌握Rust基础语法, 可通过官方书籍来补充了解, 部分语法知识会单独介绍, 中文版也可参照中文版官方书籍.

Note

通常来说, 由于《算法导论》对于大部分语言的支持性, 基础语法一般可以完成算法导论中的所有内容. 但实际使用时我们更推荐用Rust的零成本抽象, 所以会补充介绍, 必要时还会额外用算法知识解释.

Note

另外一部分地方(如标准库函数介绍)也给出中文版官方文档的链接.

内容从《算法导论》第一部分第2章(这是正式开始介绍算法的地方)开始提供.

其它

开源协议

本书以MIT协议开源.

插件

mdbook-mermaid

采用Jan-Erik Rediger提供的mdbook-mermaid插件, 许可证是MPL. 本书以保留原 MPL 文件的版权声明和许可证文本进行兼容.

mdbook-katex

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

字体

采用monaspace, 许可证是SIL OFL. 本书以保留原 OFL 文件的版权声明和许可证文本进行兼容.

参考书

本书参考《算法导论》编写.

特殊

关于近期更改

由于 mdbook 升级到v0.5导致的破坏性更新, 部分插件已不再可以正常工作. 我们已做了一些更新, 更多相关内容可以查看#2. 现在可以使用mdbook最新版, 并推荐使用setup.sh给出的插件版本.

算法基础

介绍算法基础内容.

• 插入排序
• 循环不变式
• 分析算法
• 分治法
• 分治法分析
• 二分查找
• 思考与提高
• 后记

插入排序

主问题重现

我们在下面用形式化语言¹ 给出主问题的一个重现:

输入

$n$ 个数的数组 $[a_1,a_2,\dots ,a_n]$

输出

输入数组的升序排列 $[a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }]$, 满足 $a_1^{\prime }\le a_2^{\prime }\le \cdots \le a_n^{\prime }$

主问题思考

这个主问题是我们本章将要讨论的基点. 是一个非常经典的排序问题. 在这里我们引入一个相对简单的排序: 插入排序(Insert Sort).

来看下面实现:

INSERT-SORT

#![allow(unused)]
fn main() {
pub fn insert_sort<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;
        }
    }
}
}

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

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

Note

这里我们采用了泛型, 使得任何实现了Ord trait的数组(切片)均可进行插入排序.

另一种方法不通过swap交换, 而是将操作值保存, 直到最后再进行赋值, 像接下来的实现:

#![allow(unused)]
fn main() {
pub fn insert_sort_of_copy<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;
    }
}
}

Note

需要Copy

同理, 也可以使用Clone:

#![allow(unused)]
fn main() {
pub fn insert_sort_of_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. 尝试将INSERT-SORT改为降序排列(满足 $a_1^{\prime }\ge a_2^{\prime }\ge \cdots \ge a_n^{\prime }$ ).

#![allow(unused)]
fn main() {
pub fn insert_sort_in_reverse<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;
        }
    }
}
}

Note

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

所以我们也有下面这种设置排序规则的:

#![allow(unused)]
fn main() {
// 实现以`compare`来控制排序规则的插入排序
pub fn insert_sort_by<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,
}

pub fn insert_sort_by<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;
        }
    }
}

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 },
    ];

    // 按年龄升序排序
    insert_sort_by(&mut people, |a, b| a.age < b.age);
    println!("按年龄排序: {:?}", people);

    // 按名字字典序排序
    insert_sort_by(&mut people, |a, b| a.name < b.name);
    println!("按名字排序: {:?}", people);
}

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

2. 考虑以下查找问题:

输入: $n$ 个数的数组 $[a_1,a_2,\dots ,a_n]$ 和一个值 $v$

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

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

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

LINEAR-SEARCH

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

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

1. 本处“形式化语言“并非指是一种由严格定义的符号组成的字符串集合, 而是描述一类算法对于 输入/输出 关系的控制, 以自然语言化, 较精准化, 弱数学化提供算法行为. ↩

2. NIL是算法描述中表示“空“或“终止“的通用符号. 并且与NULL等空指针中区分. 在一些结构(如链表), NIL是一类特殊哨兵值(后见), 在标准库实现中, NIL就有所存在. ↩

3. 线性查找(Linear Search), 也称为顺序查找, 是一种简单直观的搜索算法. 它的核心思想是逐个遍历数据集中的元素, 直到找到目标值或遍历完所有元素. ↩

循环不变式

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

定义

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

性质

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

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

这个定义非常漂亮, 但还有更好理解的版本:

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

解释

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

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

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

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

证明

我们需要证明:

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

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 的值确实是数组所有元素的和, 算法正确.

体会

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

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

1. 与算法目标相关

不变式应该直接或间接地描述算法的最终目标.

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

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

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

3. 可验证

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

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

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

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

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

深化

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

#![allow(unused)]
fn main() {
pub fn linear_search<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 是正确的.

练习与回答

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

设计

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

外层循环的不变式

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

内层循环的不变式

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

证明

外层循环不变式的证明

1. 初始化:

   • 当 i = 1 时, arr[0..1] 只有 1 个元素, 自然是有序的.
   • 成立.

2. 保持:

   • 假设 arr[0..i] 是有序的.
   • 内层循环会将 arr[i] 插入到 arr[0..i] 的正确位置, 使得 arr[0..i+1] 有序.
   • 成立.

3. 终止:

   • 当 i == arr.len() 时, arr[0..arr.len()] 是整个数组, 并且已经有序.
   • 成立.

内层循环不变式的证明

1. 初始化:

   • 内层循环开始时, j = i, arr[j..i] 是空区间(j == i), 所以 arr[j..i] 的所有元素(无)都大于 arr[j-1].
   • arr[0..i] 除了 arr[j] 外有序(因为外层循环不变式保证 arr[0..i] 有序).
   • 成立.

2. 保持:

   • 如果 arr[j] < arr[j-1], 则交换它们, 此时:
   • arr[j] 的新值是原来的 arr[j-1], 而 arr[j-1] 的新值是原来的 arr[j].
   • 由于 arr[0..i] 原本有序(除了 arr[j]), 交换后 arr[j-1] 仍然比左边的元素大(否则不会继续循环).
   • 成立.

3. 终止:

   • 内层循环终止时, j == 0 或 arr[j] >= arr[j-1].
   • 此时 arr[j] 已经插入到正确的位置, arr[0..i+1] 有序.
   • 成立.

代码的正确性

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

Note

上面的内容与《算法导论》有所不同, 但尽量减少了术语的使用, 理解难度更低.

分析算法

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

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

RAM模型

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

核心特点

1. 随机访问内存

   • 假设内存是“扁平化“的, 访问任意地址的数据耗时相同(与硬盘的顺序访问不同).
   • 例如, 读取 A[i] 和 A[j] 的时间相同, 无论 i 和 j 的距离多远.

2. 基本操作耗时恒定

   • 算术运算(+, -, *, /)
   • 逻辑比较(>, ==, &&)
   • 内存读写(赋值、访问变量)
   • 控制流(if, for, return等)

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

3. 单处理器、无并发

   • 假设程序按顺序执行, 不考虑多线程、缓存或并行计算的影响.

4. 无限内存(理想化)

   • 忽略物理内存限制, 但实际分析中仍需考虑空间复杂度.

为什么使用RAM模型？

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

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

#![allow(unused)]
fn main() {
pub fn insert_sort<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$ 表示每个操作的代价.

#![allow(unused)]
fn main() {
pub fn insert_sort<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
        }
    }
}
}

Note

下面要使用求和知识, 可参见 附录.

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

#![allow(unused)]
fn main() {
// 先给定 n = arr.len()
pub fn insert_sort<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$对于输入情况的解释非常复杂), 那么有: $$\begin{array}{rl}T(n)& =c_1(n-1)+c_2(n-1)+c_3\left(\sum _{i=1}^{n-1}{t}_i\right)\\ & +c_4\left(\sum _{i=1}^{n-1}(t_i-1)\right)+c_5\left(\sum _{i=1}^{n-1}(t_i-1)\right)\end{array}$$

接着我们代入t_i最值, 于是有:

最优情况: $$\begin{array}{rl}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)\end{array}$$ 观察后可以发现, $c_i$属于基本操作, 所以 $(c_1+c_2+c_3)$ 是常数, 不难得 $T(n)$ 是关于 $n$ 的线性函数¹.

最坏情况:

最坏情况下, 注意到 $$\sum _{i=1}^{n-1}{t}_i=\sum _{i=1}^{n-1}(i+1)=\frac{n(n+1)}{2}-1$$ 和 $$\sum _{i=1}^{n-1}(t_i-1)=\sum _{i=1}^{n-1}i=\frac{n(n-1)}{2}$$ 同样我们代入变形: $$\begin{array}{rl}T(n)& =\frac{c_3+c_4+c_5}{2}{n}^2+\left(c_1+c_2+\frac{c_3-c_4-c_5}{2}\right)n\\ & -\left(c_1+c_2+c_3-\frac{c_4+c_5}{2}\right)\end{array}$$ 很显然, 这是一个二次函数.

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

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

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

增长量级

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

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

在后面的内容中, 我们非形式化的使用$\Theta$. ³

练习与回答

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

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

记住最高阶项决定一切, 忽视系数和低次项直接得到答案——$\Theta (n^3)$.

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

1. Rust代码

#![allow(unused)]
fn main() {
pub 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. 时间复杂度分析

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

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

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

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

比较次数的期望值: $$\begin{array}{rl}E& =\sum _{k=1}^n\left(\text{第 }k\text{ 次找到的概率}\times k\right)\\ & =\sum _{k=1}^n\left(\frac{1}{n}\times k\right)=\frac{1}{n}\cdot \frac{n(n+1)}{2}=\frac{n+1}{2}\end{array}$$

则

$$T_{\text{avg}}(n)=\Theta (n)$$

1. 这里的线性函数并不是高等数学中的严格定义. 《算法导论》中, 使用的是初等数学中的宽松定义(即形如 $f(x)=kx+b(k\ne 0)$ 的一次函数). 对于高等数学来说, 上面的函数既不满足齐次性, 又不满足叠加性(当$(c_1+c_2+c_3)$为0时, 原函数变化成零函数, 满足线性要求, 但显然不为0). 由于$b=c_1+c_2+c_3\ne 0$所以该函数更准确的叫仿射函数. ↩

2. 希腊语中的第8个字母, 读作 theta. ↩

3. 时间复杂度(Time Complexity) 描述算法执行时间随输入规模增长的变化趋势. 运行时间(Running Time) 描述算法在特定输入下实际消耗的时间. 在本章之后, 我们正式将二者区分. ↩

分治法

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

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

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

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

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

我们将用分治法来设计一个排序算法, 该算法的最坏情况时间复杂度比插入排序要少得多.

归并排序

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

输入

$n$ 个数的数组 $[a_1,a_2,\dots ,a_n]$

输出

输入数组的升序排列 $[a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }]$, 满足 $a_1^{\prime }\le a_2^{\prime }\le \cdots \le a_n^{\prime }$

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

MERGE-SORT

#![allow(unused)]
fn main() {
pub fn merge_sort<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

它的变化过程是这样的:

flowchart LR
    step1["步骤1<br/>Left: 2 4<br/>Right: 3 7 8<br/>New: 1"] --> step2
    step2["步骤2<br/>Left: 4<br/>Right: 3 7 8<br/>New: 1 2"] --> step3
    step3["步骤3<br/>Left: 4<br/>Right: 7 8<br/>New: 1 2 3"] --> step4
    step4["步骤4<br/>Left: <br/>Right: 7 8<br/>New: 1 2 3 4"] --> step5
    step5["步骤5<br/>Left: <br/>Right: <br/>New: 1 2 3 4 7 8"]

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

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

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

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

练习与回答

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总共有$n1+n2=r-p+1$个元素, 所以A[p..r]包含了L和R的所有元素, 且是有序的.

1. 递归(Recursion) 是算法设计中的一种重要技术, 指函数或过程直接或间接调用自身来解决问题的方法. ↩

2. 这种可直接求解的边界叫做基线条件(Base Case), 与之相对的就是递归条件(Recursive Case). 如 MERGE-SORT 的基本情况. ↩

3. 这意味着右数组有$\lceil n\rceil$个元素, 左数组有$\lfloor n\rfloor$个元素. 其中$\lceil x\rceil$表示大于或等于$x$的最小整数, $\lfloor x\rfloor$表示小于或等于$x$的最大整数. ↩

4. 这只是辅助函数的时间复杂度, 归并排序的实际复杂度在后面解答. ↩

分治法分析

了解了归并排序的实现原理和循环不变式, 我们将要讨论归并排序的时间复杂度.

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

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

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

对于归并排序又恰知 $a=b=2$, 即有递归式: $$T(n)=\{\begin{array}{ll}\Theta (1)& \text{if }n\le 1\text{这里也可为}n=1,\\ 2T\left(\frac{n}{2}\right)+\Theta (n)& \text{if }n>1\end{array}$$

后面我们会学一个“主定理“, 用它可得 $T(n)=\Theta (n\log n)$. 这里省略了底数$2$, 即此处的$\log$等价于${\log }_2$. 除非另有明确说明, 这是算法分析中的默认约定(而非数学中的). 许多高效算法通常将问题一分为二, 计算机科学中许多操作基于二进制, 故$\log$非常有效¹.

事实上, 在渐进界($\Theta$)中, $\log$底数影响不大. 以${\log }_{2}n$为例, 利用换底公式, 可得${\log }_{2}n=\frac{{\log }_{x}n}{{\log }_{x}2}={\log }_{2}x\times {\log }_{x}n$. 其中$x$为大于$1$的常数, 所以${\log }_{2}x$也是常数, 省略常数, 得到${\log }_{2}n=\Theta (lo{g}_{x}n)$, 印证了我们上面的结论. 其实忽略底数的本质是对数增长速率的一致性和常数因子的无关性. ²

为了直观地理解上递归式的解为什么是$T(n)=\Theta (n\log n)$, 我们并不需要主定理. 把上递归式重写为: $$T(n)=\{\begin{array}{ll}c& \text{if }n=1,\\ 2T\left(\frac{n}{2}\right)+cn& \text{if }n>1\end{array}$$ 其中常量 $c$ 代表求解规模为 $1$ 的问题所需的时间(等价于 $\Theta (1)$ ), 以及在分解步骤与合并步骤处理每个数组元素所需的时间. 然后我们用 递归树 来展示一下这个过程:

graph TD
    A["cn"] --> B["cn/2"]
    A --> C["cn/2"]

    B --> D["cn/4"]
    B --> E["cn/4"]

    C --> F["cn/4"]
    C --> G["cn/4"]

    D -.-> H["..."]
    D -.-> I["..."]
    E -.-> J["..."]
    E -.-> K["..."]
    F -.-> L["..."]
    F -.-> M["..."]
    G -.-> N["..."]
    G -.-> O["..."]

    H --> P["c"]
    I --> Q["c"]
    J --> R["c"]
    K --> S["c"]
    L --> T["c"]
    M -.-> U["..."]
    N --> V["c"]
    O --> W["c"]

这个完整的递归树有${\log }_{2}n+1$层(分解层数和最后一层), 每一层贡献了$cn$的代价, 总量为$cn\times ({\log }_{2}n+1)=\Theta (n\log n)$.

深入

为了严谨起见, 我们对文中所涉及的“编程范式“和“编程策略“概念进行明确定义:

• 编程范式(Programming Paradigm) : 指代程序代码组织的基本思想和哲学框架, 它规定了程序的结构化方式和核心的抽象机制
• 编程策略(Programming Strategy) : 指代解决特定问题的具体方法论或战术, 指导如何将问题分解并最终实现目标

二者关键区别在于其抽象层级和作用范围. 例如, 面向对象编程(OOP)是一种范式；而增量法(Incremental Approach)则是一种策略. 两者定义上的潜在重叠可能引起混淆. 以“分而治之“为例:

其名称虽带有哲学意味, 但本身并非编程范式. 因为它并未规定代码的具体结构或引入新的语言抽象. 相反, “分而治之“作为一种通用的分解思想, 更适用于策略层面, 这与增量法属于同一层级.

与之对照的, 在Rust编程中常用的 范型(Generics) 则是一种确切的编程范式, 因为它通过参数化类型极大地约束和改变了代码的结构与抽象方式.

迭代(Iterative Approach) 和 递归(Recursive Approach) 是分别实现 增量法 和 分治法 这两类策略的常见具体代码形式:

• 迭代: 通过循环结构逐步逼近目标.
• 递归: 通过自我调用来分解和解决问题.

简单来说,

• 增量法本质上是一种线性扩张: 问题被分解为一系列线性步骤, 答案通过逐步累积增量结果构建.
• 分治法本质上是树状分解: 问题被递归地分解为相互关联的子问题(常形成树状结构), 最终答案通过组合子问题的答案获得.

因而

• 即使使用递归实现的插入排序, 其问题求解模式仍是增量策略.
• 即使使用迭代实现的归并排序, 其问题求解模式仍是分治策略. 递归与迭代作为实现形式, 在理论上可以互相转换.

插入排序

基于上面的理论依据, 现在我们可以把插入排序表示为如下的一个递归过程. 为了排序A[1..n], 我们递归地排序A[1..n-1], 然后把A[n]插入已排序的数组A[1..n-1]. 为插入排序的这个递归版本的最坏情况时间复杂度写一个递归式.

我们先给出一个Rust实现:

pub fn insert_sort_by_recursion<T: Ord>(arr: &mut [T]) {
    // 基本情况: 数组长度为 0 或 1 时已经有序
    if arr.len() <= 1 {
        return;
    }

    let n = arr.len();

    // 递归排序前 n-1 个元素
    insert_sort_by_recursion(&mut arr[..n - 1]);

    // 将最后一个元素插入到已排序的前 n-1 个元素中
    let mut i = n - 1;
    while i > 0 && arr[i - 1] > arr[i] {
        arr.swap(i - 1, i);
        i -= 1;
    }
}

fn main() {
    // 测试用例
    let mut arr = [5, 2, 4, 6, 1, 3];
    println!("排序前: {:?}", arr);

    insert_sort_by_recursion(&mut arr);
    println!("排序后: {:?}", arr);

    let mut empty_arr: [i32; 0] = [];
    insert_sort_by_recursion(&mut empty_arr);
    println!("空数组: {:?}", empty_arr);

    let mut single_arr = [7];
    insert_sort_by_recursion(&mut single_arr);
    println!("单元素数组: {:?}", single_arr);
}

先观察其基线情况: 当数组长度为1时(即 n = 1), 数组已经是有序的, 不需要任何操作, 故 $$T(n)=\Theta (1)\text{ if }n=1$$

Note

其实$n\le 1,n\in \mathbb{N}$更精准(n = 0时为空数组).

然后, 我们进行递归式分析. 因为为了排序A[1..n], 我们递归地排序A[1..n-1], 所以$T(n)=T(n-1)+\Theta (n)$ (其中$\Theta (n)$是进行插入的时间复杂度). 综上则有:

$$T(n)=\{\begin{array}{ll}T(n-1)+\Theta (n)& \text{if }n>1,\\ \Theta (1)& \text{if }n=1.\end{array}$$

我们可以进一步分析, 对递归式展开:

$$\begin{array}{rl}T(n)& =T(n-1)+c\cdot n\\ & =T(n-2)+c\cdot (n-1)+c\cdot n\\ & =T(n-3)+c\cdot (n-2)+c\cdot (n-1)+c\cdot n\\ & ⋮\\ & =T(1)+c\cdot 2+c\cdot 3+\cdots +c\cdot n\\ & =d+c\cdot (2+3+\cdots +n)\\ & =d+c\cdot \left(\frac{n(n+1)}{2}-1\right)\\ & =\Theta (n^2)\end{array}$$ 可见递归版插入排序与迭代版最坏时间复杂度一致.

练习与回答

1. 使用数学归纳法证明: 当$n$刚好是$2$的幂时, 以下递归式的解是$T(n)=n\log n$. $$T(n)=\{\begin{array}{ll}2& \text{if }n=2,\\ 2T\left(\frac{n}{2}\right)+n& \text{if }n=2^k,k>1\end{array}$$

证明

数学归纳法是一种证明与自然数相关的命题的方法.

首先我们要证明 基例(Base Case) ³:

由递归定义, 得 $$T(2)=2$$ 代入解: $$T(2)=2log2=2$$ 二者一致, 故基例成立.

然后我们证明 归纳步骤(Inductive Step):

对于 $n=2^k$, 通过解有 $T(2^k)=2^k\log 2^k=k\times 2^k$(归纳假设).

接着通过递归定义, 假令 $n=2^{k+1}$: $$T(2^{k+1})=2T\left(\frac{2^{k+1}}{2}\right)+2^{k+1}=2T(2^k)+2^{k+1}$$

接着通过归纳假设变形: $$T(2^{k+1})=(k+1)2^{k+1}$$ 这与原有的归纳假设不冲突, 因此归纳假设成立.

从而证明了递归式的解为$T(n)=n\log n$.

1. 关于对数相关知识, 请参考幂与对数. ↩

2. 因而, 《算法导论》中也使用过$\lg$来代替$\log$. (其实《算法导论》很多情况令$\lg$等效于${\log }_2$, 而非${\log }_{10}$, 本书不破坏$\lg$的原有定义) ↩

3. 在该证明中类似于我们之前的 基线条件(Base Case). ↩

二分查找

考虑以下查找问题:

输入: $n$ 个数的数组 $[a_1,a_2,\dots ,a_n]$ 和一个值 $v$

输出: 下标$i$使得$v=A[i]$, 或者当$v$不在$A$出现时, 返回特殊值$NIL$

上面这个问题是我们在插入排序那一节就已经介绍的.

注意到, 如果序列A已排好序, 就可以将该序列的中点与v进行比较. 根据比较的结果, 原序列中有一半就可以不用再做进一步的考虑了, 这种在 有序数组中高效查找特定元素的算法 被称为 二分查找(Binary Search).

BINARY-SEARCH

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

pub fn binary_search<T: Ord>(arr: &[T], v: &T) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len().checked_sub(1)?;               // 处理空数组

    while low <= high {
        let mid = low + (high - low) / 2;
        match arr[mid].cmp(v) {
            Ordering::Equal => return Some(mid),
            Ordering::Less => low = mid + 1,
            Ordering::Greater => high = mid - 1,
        }
    }

    None
}
}

Note

在这里checked_sub用于检查整数减法, 计算 self - rhs, 如果发生溢出则返回 None. 并使用Ordering方便用match进行匹配.

首先, 我们要确定区间[low, high], low为数组首索引(在Rust中为0), high为数组尾索引(在Rust中为arr.len() - 1).

然后, 在区间内找到中间值mid = (low + high) / 2, 这可能会溢出, 利用简单数学证明可得: $$\begin{array}{rl}\text{mid}& =\frac{\text{low}}{2}+\frac{\text{high}}{2}\\ & =\frac{\text{low}}{2}+\frac{\text{high}-\text{low}+\text{low}}{2}\\ & =\frac{\text{low}}{2}+\frac{\text{high}-\text{low}}{2}+\frac{\text{low}}{2}\\ & =\text{low}+\frac{\text{high}-\text{low}}{2}\end{array}$$ 该式可以避免溢出. (事实上, 标准库的实现也是这么做的)

利用条件low <= high可以确保区间[low, high]成立.

接着, 判定arr[mid]与v的关系. 当二者相等时(Ordering::Equal), 直接返回当前索引；如果较大说明右半部分不存在, 通过收紧(high = mid - 1), 将右边部分排除, 同理较小时用low = mid + 1将左半部分排除.

二分查找显然使用了分治法¹, 不过比较特殊的是它没有合并的步骤(并且采用迭代法). 我们利用循环不变式来证明二分查找的正确性:

在每次循环迭代开始时, 如果目标值 v 存在于数组中, 则 v 一定位于子数组 arr[low..high-1] 中, 其中 arr 是已排序的数组, low 和 high 是当前搜索区间的边界索引.

这个循环不变式比较简单, 留给读者自证. 从上面的过程, 我们不难证得$T(n)=\Theta (\log n)$.

我们增高难度, 在现有的基础上, 我们不再保证有且仅有一个i, 即A数组中可能存在多个v, 要求给出最小的i. 这是一个常见的求左边界的二分算法, 我们用Rust实现:

#![allow(unused)]
fn main() {
pub fn find_left_boundary<T: Ord>(arr: &[T], v: &T) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len().checked_sub(1)?;

    while low < high {          // 取消等于
        let mid = low + (high - low) / 2;
        if arr[mid] < *v {      // 注意解引用
            low = mid + 1;      // 与之前相同
        } else {
            high = mid;         // 目标值在左侧或当前位置
        }
    }

    if arr.get(low)? == v {     // 使用get更安全
        Some(low)
    } else {
        None
    }
}
}

这里主要逻辑改写在比较部分: 当arr[mid] < v时, 目标值必然在右侧, 所以移动low；当arr[mid] >= v目标值可能出现在左侧或当前位置(arr[mid] == v), 所以移动high到mid(不是mid - 1). 重点在low >= high说明所有的v都已出现(这里就是上面low < high不使用等号的原因), 那么low必然在最小v的位置上. 当然这个算法有个问题, 不存在时会误报, 所以要二次判断.

同理, 不难写出寻找最大i的二分算法:

#![allow(unused)]
fn main() {
pub fn find_right_boundary<T: Ord>(arr: &[T], v: &T) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len().checked_sub(1)?;

    while low < high {
        let mid = low + (high - low + 1) / 2;   // 向上取整
        if arr[mid] <= *v {
            low = mid;                          // 保留当前位置
        } else {
            high = mid - 1;
        }
    }

    if arr.get(low)? == v {
        Some(low)
    } else {
        None
    }
}
}

可以发现, 比较逻辑的改写比较复杂, 在比较微小的地方出错就会导致算法进入死循环或错估, 所以循环不变式在判断二分算法的正确性上非常重要.

在向我们刚刚的数组切片或有序数组中, std标准库提供了一系列方法:

#![allow(unused)]
fn main() {
let v = vec![1, 3, 5, 7, 9];
assert_eq!(v.binary_search(&5), Ok(2));
assert_eq!(v.binary_search(&4), Err(2));    // 插入后为 [1, 3, 4, 5, 7, 9]
}

上面这个例子中binary_search返回Result<usize, usize>, Ok(index) 中 index 为元素所在位置, Err(index) 中则为未找到元素时, 如果将元素插入到数组, 保持有序的位置. binary_search_by允许通过函数来设置查找规则, binary_search_by_key允许通过键(如结构体字段)查找.

Note

上面的这些方法和实现都要确保数组已经排序, 否则返回的结果无意义. binary_search_by之类的, 通常来说与上面的手写性能相差不大, 但更具有扩展性.

在较新的版本(Rust 1.52+)中, partition_point 可以用来返回满足条件的第一个元素的位置:

#![allow(unused)]
fn main() {
let v = vec![1, 2, 2, 3, 3, 4, 5];
println!("{}", v.partition_point(|&x| x < 4));  // 第一个不小于4的元素位置
}

Note

该函数底层是self.binary_search_by(|x| if pred(x) { Less } else { Greater }).unwrap_or_else(|i| i)这种写法使得binary_search永远找不到等于的位置, 所以就会返回插入之后仍然有序的位置, 也就是第一个不满足pred函数的位置. (其中pred是调用者的输入)

我们重新来看插入排序:

pub fn insert_sort<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;
        }
    }
}

其中

while j > 0 && arr[j] < arr[j - 1] {
    arr.swap(j, j - 1);
    j -= 1;
}

这个部分是将需要排序的元素在有序数组中移动找到适合的位置, 在有序数组中查找, 完全可以利用二分:

#![allow(unused)]
fn main() {
pub fn insert_sort_by_binary_search<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        // 此处直接使用标准库, 下面代码完全可以用`partition_point`进行修改, 取决于您
        let pos = arr[..i].binary_search(&arr[i]).unwrap_or_else(|pos| pos);
        // 将整个区间右移1个单位(直接使用`swap`理论上也完全可以)
        arr[pos..=i].rotate_right(1);
    }
}
}

上面这个优化仅仅改变了比较次数, 不影响总体的时间复杂度. 对于大规模数据和操作代价较高的会有一定优化, 其他情况下还是使用线性更优.

两数之和

考虑下面这道题:

输入: $n$ 个整数的数组 $[a_1,a_2,\dots ,a_n]$ 和一个整数 $x$

输出: 下标 $i_1$和$i_2$ 使得 $A[i_1]+A[i_2]=x$, 或者当数组中无两数之和为 $x$ 时, 返回特殊值$NIL$

Tip

保证有且仅有一个满足条件的解

我们将用增量法, 分治法和一特殊方法解决此问题.

增量法最简单, 我们可以用两层循环:

#![allow(unused)]
fn main() {
pub fn incremental(arr: &[i32], x: i32) -> Option<(usize, usize)> {
    for i in 0..arr.len() {
        for j in (i + 1)..arr.len() {
            if arr[i] + arr[j] == x {
                return Some((i, j));
            }
        }
    }
    None
}
}

但复杂度将达到$\Theta (n^2)$.

分治法则不难想到二分查找:

#![allow(unused)]
fn main() {
pub fn divide_and_conquer(arr: &[i32], x: i32) -> Option<(usize, usize)> {
    // 先对数组进行排序 (保留原索引)
    let mut sorted: Vec<(usize, &i32)> = arr.iter().enumerate().collect();
    sorted.sort_by(|a, b| a.1.cmp(b.1));

    let mut left = 0;
    let mut right = sorted.len() - 1;

    while left < right {
        let sum = sorted[left].1 + sorted[right].1;
        if sum == x {
            // 确保返回的索引顺序与原数组一致
            let (i1, i2) = (sorted[left].0, sorted[right].0);
            return Some((i1.min(i2), i1.max(i2)));
        } else if sum < x {
            left += 1;
        } else {
            right -= 1;
        }
    }

    None
}
}

该方案虽然使用了排序, 但按照归并排序的时间复杂度(标准库的排序实现更为复杂, 这里简单的以归并排序为例), 该实现仍然是$\Theta (n\log n)$.

最后一种方法非常特殊, 在后面的课程中我们会具体讲到, 这里简单介绍一下:

哈希表(Hash Map 或 Hash Table) 是一种通过 哈希函数(Hash Function) 将 键(key) 映射到存储位置的数据结构. 具体来说, 哈希函数将任意类型的键转换为一个固定范围内的整数(称为哈希值), 该值作为索引用于在数组中存储对应的值. 借助数组的随机访问特性, 哈希表在理想情况下的查找、插入和删除操作的时间复杂度均为 $\Theta (1)$.

#![allow(unused)]
fn main() {
// 使用标准库实现的哈希表
use std::collections::HashMap;

pub fn search_by_hash_map(arr: &[i32], x: i32) -> Option<(usize, usize)> {
    let mut map = HashMap::new();

    for (i, &num) in arr.iter().enumerate() {
        // 计算与当前项相加等于x的值
        let complement = x - num;
        // 在哈希表中寻找是否有complement
        if let Some(&j) = map.get(&complement) {
            // 如果有, 直接返回当前索引和complement所在索引
            return Some((j, i));
        }
        // 否则, 保存当前项对应的索引
        map.insert(num, i);
    }

    None
}
}

该算法是单循环的, 又因为哈希表的读取运算是常数时间, 所以这个实现时间复杂度为$\Theta (n)$.

练习与回答

1. 我们作以下考虑: 虽然归并排序的最坏情况运行时间为$\Theta (n\log n)$, 而插入排序的最坏情况运行时间为$\Theta (n^2)$, 但是插入排序中的常量因子可能使得它在$n$较小时, 在许多机器上实际运行得更快. 因此, 在归并排序中当子问题变得足够小时, 采用插入排序来使递归的叶变粗是有意义的. 考虑对归并排序的一种修改, 使用插入排序来排序长度为$k$的$n/k$个子表, 然后使用标准的合并机制来合并这些子表, 这里$k$是一个待定的值.

#![allow(unused)]
fn main() {
pub fn merge_sort_by_insert(arr: &mut [i32], k: usize) {
    let n = arr.len();
    if n <= k {
        insertion_sort(arr);
        return;
    }
    let mid = n / 2;
    merge_sort_by_insert(&mut arr[..mid], k);
    merge_sort_by_insert(&mut arr[mid..], k);
    merge(arr, mid);
}

fn insertion_sort(arr: &mut [i32]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j - 1] > arr[j] {
            arr.swap(j - 1, j);
            j -= 1;
        }
    }
}

fn merge(arr: &mut [i32], mid: usize) {
    let mut temp = arr.to_vec();
    let (mut i, mut j, mut k) = (0, mid, 0);
    while i < mid && j < arr.len() {
        if temp[i] <= temp[j] {
            arr[k] = temp[i];
            i += 1;
        } else {
            arr[k] = temp[j];
            j += 1;
        }
        k += 1;
    }
    while i < mid {
        arr[k] = temp[i];
        i += 1;
        k += 1;
    }
    while j < arr.len() {
        arr[k] = temp[j];
        j += 1;
        k += 1;
    }
}
}

这种实现与 Timsort² 的核心思想一致, 结合了归并与插入的优点, 接下来我们深入讨论:

在上述算法中, 插入排序可以在$\Theta (nk)$时间内排序每个长度为$k$的$n/k$个子表(每个子表排序的时间复杂度为$\Theta (k^2)$, 故$T(n)=\Theta (k^2)\cdot (n/k)=\Theta (nk)$). 同样不难看出, 合并子表的时间复杂度是$\Theta (n\log (n/k))$, 综上就有该算法最坏情况下的时间复杂度为$\Theta (nk+n\log (n/k))$. 为了确保任何$k$的取值不能使修改后算法时间复杂度高于原算法, $k=O(\log n)$³.

在实际使用中, $k$不能随着的$n$增长增长过快, 所以通常使用常数或对数级, 一般选用20至100的常数, 或者利用$k=\log n$的对数情况动态调整. 更现实化的时候, 可以通过cpu缓存规则或者混合策略(分段使用常数和对数)来解决.

1. 二分查找是通过缩小搜索区间来工作, 而不是逐步构建解, 因此不属于增量方法. 它属于分治法的一种特例, 我们称作 减治法(decrease and conquer). ↩

2. Timsort 是一种高效的混合排序算法, 由 提姆·彼得斯(Tim Peters) 在 2002 年为 Python 语言设计(Python 2.3 及后续版本的默认排序算法). 其针对现实世界中的部分有序数据进行了优化, 具有稳定性和适应性. ↩

3. 即$k$的增长速度不超过$\log n$, 这里读者可以先行自证, 此类标准的证明方法在后续讲到. ↩

思考与提高

冒泡排序

介绍插入排序的时候我们提到了另一种简单却低效的排序算法——冒泡排序(Bubble Sort).

BUBBLE-SORT

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

fn main() {
    // 测试整数排序
    let mut numbers = [64, 34, 25, 12, 22, 11, 90];
    println!("排序前: {:?}", numbers);
    bubble_sort(&mut numbers);
    println!("排序后: {:?}", numbers);

    // 测试字符串排序
    let mut words = ["banana", "apple", "pear", "orange", "grape"];
    println!("排序前: {:?}", words);
    bubble_sort(&mut words);
    println!("排序后: {:?}", words);
}

关于这个排序, 我们的循环不变式是这样的: 每次外层循环(i循环)结束时, 数组的最后i个元素是已排序的, 并且是整个数组的最大i个元素.

上式读者自证不难, 从上面的循环不变式不难看出: 冒泡排序通过两两互相比较, 每次都将这次最大的数据放到后面. 很显然, 它用的是跟插入排序一样的增量法, 时间复杂度也为$T(n)=n^2$.

当然我们也不难看出, 如果一次循环没有进行任何交换说明已经排好序了, 可以提前终止:

#![allow(unused)]
fn main() {
pub fn bubble_sort_optimized<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    for i in 0..n {
        let mut swapped = false; // 标记本轮是否发生交换
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
                swapped = true;
            }
        }
        // 如果本轮没有交换, 说明数组已经有序, 提前终止
        if !swapped {
            break;
        }
    }
}
}

现在冒泡排序主要用于教学, 由于效率低几乎不会实际使用. 插入排序由于内部有更高效的循环机制, 对于较小的数据反而更快, 还可以 与归并相结合得到TimSort.

霍纳规则

霍纳(William George Horner, 1786–1837) 是英国数学家, 以提出 霍纳规则(Horner’s Rule) 而闻名. 该规则用于高效计算多项式的值.

我们来看这样一个多项式: $$P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+\cdots +a_{1}x+a_0$$ 上面这样的多项式便是一般的标准多项式. 霍纳规则的核心思想非常简单, 即不断的提取公因式$x$, 从而完成降次: $$P(x)=a_0+x(a_1+x(a_2+x(a_3+\cdots +x(a_{n-1}+x{a}_n)+\dots )))$$ 但真正重要的是, 我们可以在这个过程中融入迭代法, 从而得到:

#![allow(unused)]
fn main() {
use std::ops::{Mul, Add};

/// 使用霍纳规则计算多项式 P(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \dots + a_1 x + a_0
/// 输入:
/// - `coeffs`: 多项式系数切片, 按 `a_0` 到 `a_n` 顺序排列
/// - `x`: 计算多项式值的点
/// 返回:
/// - 计算结果 `T`
///
/// 要求:
/// - `T` 必须支持加法 (`+`) 和乘法 (`*`) 运算
/// - `T` 必须实现 `Copy` trait(或改用 `clone()`)
pub fn horner<T>(coeffs: &[T], x: T) -> T
where
    T: Mul<Output = T> + Add<Output = T> + Copy + Default,
{
    coeffs.iter().rev().fold(
        T::default(),
        |acc, &coeff| acc * x + coeff
    )
}
}

注: 这种迭代的思想在泰勒展开、密码学, 之前提到的牛顿迭代都有广泛的应用. 霍纳并非最早提出此方法, 类似思想可追溯至中国古代数学家秦九韶(《数书九章》, 高次方程数值解), 因此在中国也称为 秦九韶算法.

该算法用了fold()一次, 不难看出时间复杂度为$\Theta (n)$, 我们写个普通运算:

pub fn polynomial_sum<T>(coeffs: &[T], x: T) -> T
where
    T: Mul<Output = T> + Add<Output = T> + Copy + From<u32>,
{
    coeffs.iter().enumerate().fold(T::from(0), |acc, (i, &coeff)| {
        acc + coeff * (0..i).fold(T::from(1), |acc, _| acc * x)
    })
}

该算法用了fold()两次(一次用于幂, 也可用快速幂使总时间复杂度降为$\Theta (n\log n)$), 不难看出时间复杂度为$\Theta (n^2)$. 对比可见霍纳规则效率之高.

逆序对

设$A$为一个有$n$个不相同元素的数组, 若$i<j$且$A[i]>A[j]$, 则称$(i,j)$为$A$的一个 逆序对(inversion).

我们来考虑$[2,3,8,6,1]$有哪些逆序对, 首先想到遍历列表:

#![allow(unused)]
fn main() {
let mut a = [2, 3, 8, 6, 1];
for i in 0..a.len() {
    for j in (i + 1)..a.len() {
        if a[i] > a[j] {
            println!("({i}, {j})");
        }
    }
}
}

很显然, 时间复杂度为$\Theta (n^2)$.

对于寻找“哪些逆序对“, 该时间复杂度不能再降了. 因为最坏情况下有$\Theta (n^2)$¹的逆序对, 输出它们并需要$\Theta (n^2)$的时间复杂度. 那试考虑 寻找“有几个逆序对“有无更低时间复杂度的解:

应该不难注意到分治法常见的时间复杂度——$\Theta (n\log n)$, 不妨来试一下:

我们回顾该合并:

// 比较左右子数组的元素, 按顺序合并到原数组
while i < left.len() && j < right.len() {
    if left[i] <= right[j] {
        arr[k] = left[i].clone();
        i += 1;
    } else {
        // 注意到, 此时 `left[i..]` 均与 `right[j]` 成逆序对
        // 基于 `left` 和 `right` 均已排序的条件
        arr[k] = right[j].clone();
        j += 1;
    }
    k += 1;
}

那么有:

fn count_inversions(arr: &mut [i32]) -> usize {
    let n = arr.len();
    if n <= 1 {
        return 0;
    }

    let mid = n / 2;
    let mut left = arr[..mid].to_vec();
    let mut right = arr[mid..].to_vec();

    let mut inversions = 0;
    inversions += count_inversions(&mut left);
    inversions += count_inversions(&mut right);

    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];
            i += 1;
        } else {
            arr[k] = right[j];
            j += 1;
            inversions += left.len() - i;
        }
        k += 1;
    }

    while i < left.len() {
        arr[k] = left[i];
        i += 1;
        k += 1;
    }
    while j < right.len() {
        arr[k] = right[j];
        j += 1;
        k += 1;
    }

    inversions
}

fn main() {
    let mut a = [2, 3, 8, 6, 1];
    let inversions = count_inversions(&mut a);
    println!("Number of inversions: {}", inversions);
}

时间复杂度降为 $\Theta (nlogn)$.

1. 这里指 空间复杂度, 后面的则仍为时间复杂度. 空间复杂度会在后面介绍. ↩

后记

迭代器与循环

Note

通过对Rust标准的迭代器进行介绍, 帮助部分学者补充相关知识, 并为后续大量使用迭代器代替循环做铺垫.

迭代器从名字来看就跟迭代有关, 我们来回顾一下迭代法: 通过循环结构逐步逼近目标. 可见迭代就是通过循环结构进行操作. 然而很多循环结构, 例如遍历等的代码具有非常普遍的相似性, 迭代器就可以用来帮助我们减少相似的代码. 所以: 迭代器(Iterator) 是负责遍历序列中的每一项和决定序列何时结束的逻辑结构.

在Rust中, 迭代器是惰性的, 它是实现了Trait std::iter::Iterator的数据结构. 基本的迭代器分为三类: IterMut, Iter, IterMut, 分别代表着不同所有权机制(拥有, 不可变引用, 可变引用). 对应的可用into_iter等函数来取得. 迭代的基础是数据, 我们必须在数据上进行迭代, 标准库大部分数据都实现了Iterator:

let nums = vec![1i32, 2, 3];
let squared: Vec<i32> = nums.iter();

由于惰性性质, 在不使用任何方法时, 迭代器不产生任何效果(仅在使用时求值评估).

接下来介绍相关方法:

// 下面相关方法均省略有关`self`和范型的定义
map(FnMut(Self::Item) -> B) -> Map<Self, F>
filter(FnMut(&Self::Item) -> bool) -> Filter<Self, F>

上面两个方法用来过滤元素或进行中间操作:

#![allow(unused)]
fn main() {
// 将数据平方
let nums = vec![1i32, 2, 3];
let squared: Vec<i32> = nums.iter()
    .map(|&x: &i32| x.pow(2)) // 明确参数类型
    .collect();
// 筛选数据
let numbers = 1..10;
let evens: Vec<_> = numbers
    .filter(|x: &i32| x % 2 == 0) // 明确类型注解
    .collect();
}

它们都需要使用collect, 方便在最后转换为数据集合, 上面使用的中间结构(Map等)同样是迭代器, 因此你是可以进行连续操作的.

fold(init: B, FnMut(B, Self::Item) -> B) -> B

同样是最后操作, 但其结果是一个具体值, 利用它, 我们可以进行求和操作:

#![allow(unused)]
fn main() {
let sum = [1, 2, 3].iter()
    .fold(0i32, |acc: i32, &x| acc + x);
}

我们可以通过另一个函数reduce(FnMut(B, Self::Item) -> B) -> Option<B>, 来寻找最大值:

#![allow(unused)]
fn main() {
let max = [5, 3, 8].iter()
    .reduce(|a: &i32, b: &i32| if a > b { a } else { b });
}

这两个函数在一定程度上可以互相转换, fold函数是要求初始值, reduce则不用, 其期待用途也不同.

另外常用的是几个控制流操作:

// 限制最大元素数量
take(n: usize) -> Take<Self>
// 转为带索引元组
enumerate() -> Enumerate<Self>
// 跳过前几个元素
skip(n: usize) -> Skip<Self>
// 压缩(合并)迭代器
zip(other: U) -> Zip<Self, <U as IntoIterator>::IntoIter>
// 展开嵌套结构
flatten() -> Flatten<Self>
// 在迭代器每个元素上调用闭包(与`map`不同, 它不返回内容)
for_each<F>(f: FnMut(Self::Item))
// 在中间观测
inspect(f: FnMut(&Self::Item)) -> Inspect<Self, FnMut(&Self::Item)>

使用示例如下:

#![allow(unused)]
fn main() {
// 取前5个元素
let taken = (1..).take(5);    // 1~5 (由于惰性性质, 可安全切割)

// 带索引遍历
for (i, c) in "Rust".chars().enumerate() {
    println!("{}: {}", i, c);
}
// 0: 'R' 1: 'u' 2: 's' 3: 't'

// 跳过前3个元素
let skipped = (1..10).skip(3); // 4~9

// 合并两个序列
let zipped: Vec<_> = (1..4)
    .zip(["a", "b", "c"])
    .collect();
// [(1, "a"), (2, "b"), (3, "c")]

// 展开嵌套结构
let matrix = [[1, 2], [3, 4]];
let flat: Vec<_> = matrix.iter().flatten().collect();
// [1, 2, 3, 4]

// 调试观察
(1..4).inspect(|x| println!("Processing: {}", x))
    .for_each(|x| { /* 逻辑 */ });
}

更多

Rust的for循环语法实际上是迭代器的语法糖:

#![allow(unused)]
fn main() {
let values = vec![1, 2, 3, 4, 5];

for x in values {
    println!("{x}");
}
}

Rust将其反糖化为:

#![allow(unused)]
fn main() {
let values = vec![1, 2, 3, 4, 5];
{
    let result = match IntoIterator::into_iter(values) {
        mut iter => loop {
            let next;
            match iter.next() {
                Some(val) => next = val,
                None => break,
            };
            let x = next;
            let () = { println!("{x}"); };
        },
    };
    result
}
}

另外我们常使用的区间也是基于迭代器的:

#![allow(unused)]
fn main() {
let numbers = 0..;                      // 生成一个无限迭代器 (由于惰性性质, 它不会被马上求值, 所以是安全的)
let five_numbers = numbers.take(5);     // 切割为有限

for number in five_numbers {
    println!("{number}");
}
}

由于Rust迭代器的零成本特性, 它一般不会拖累性能. 甚至在某些优化条件下, 拥有比默认情况(手写的一般逻辑)更快的效果.

本章历史背景

循环不变式

循环不变式概念源于程序形式化验证的需求. 罗伯特·弗洛伊德(Robert W. Floyd) 是1967年的图灵奖得主, 同年他在论文 《为程序分配意义》(Assigning Meanings to Programs) 中首次系统化提出循环不变式, 作为证明程序正确性的数学工具. 东尼·霍尔(Tony Hoare) 是1980年图灵奖得主, 在1969年发表 《计算机程序设计的公理基础》(An Axiomatic Basis for Computer Programming), 提出霍尔逻辑(Hoare Logic), 将循环不变式纳入公理化验证框架.

插入排序

这个算法思想早见于计算机科学之前(1938年的时候就有通过机械来对卡片进行排序的系统), 1950年代在计算机上系统实现.

1970年代后, 弗洛伊德和霍尔的循环不变式正式在教科书中用来证明.

归并排序

约翰·冯·诺依曼(John von Neumann) 在1945年提出归并排序, 最早采用分治思想的排序算法. 他自己并没有使用循环不变式, 但分治递归的思想天然适用于循环不变式的证明框架.

托马斯·科尔曼(Thomas H. Cormen) 等人在1990版的《算法导论》中首次将循环不变式作为算法分析的必备工具.

时间复杂度

艾伦·图灵(Alan Turing) 1936年在论文 《关于可计算数》(On Computable Numbers) 中隐含“计算步数”概念, 为时间复杂度奠基.

尤里斯·哈特马尼斯和理查德·斯特恩斯(Juris Hartmanis & Richard E. Stearns) 在1965年论文 《关于算法的计算复杂度》(On the Computational Complexity of Algorithms) 首次明确定义“时间复杂度”(Time Complexity), 获1993年图灵奖.

渐近符号

保罗·巴赫曼(Paul Bachmann) 在数论著作(1894)中首创大$O$符号. 后来由唐纳德·克努特(Donald Knuth) 在1976年 《计算机程序设计艺术》(卷1) 中推广其用于算法分析, 在其同一著作另一卷中使用了$\Theta$定义严格紧确界, 同年也定义了下界(它们的严格定义将在下一章介绍).

“Floyd的循环不变式和Knuth的$\Theta$记号, 将算法分析从经验描述提升为精确科学. ”

—— 《算法设计的艺术》(The Art of Algorithm Design, 2015)

渐近分析

在上一章节中我们介绍了时间复杂度, 它与$T(n)$函数的增长情况息息相关, 本章我们将在相对数学的角度讨论函数在极限情况下的增长状态.

Tip

本章原名: 函数的增长.

• 渐近符号
• 非紧渐近符号
• 后记

渐近符号

我们来回顾一下什么是时间复杂度, 这是一个特殊的概念, 用来形式化的解释一个算法所需要的运行时间与输入规模的特定条件下的映射关系. 其中特定条件就是在之前的课程中所描述的最坏, 最优, 平均等条件. 用数学语言表达来看: $$T(n)$$ 其中, $T$ 表示最终的运行时间, $n$ 表示输入规模, 通过一些额外标记, 如 $T_{\text{worst}}(n)$ 来表述特定情况.

在数学中, 渐近(Asymptotic) 描述的是函数或序列在某个极限点附近的行为趋势. $T(n)$ 本身就是一个函数, 当 $n\to \infty$ 时, 可能会无限接近另外一个函数或方程, 对其的分析, 便是本书中一般指的渐近分析. 即分析当自变量趋近于某个极限(在本书中通常表示 $n\to \infty$)时, 函数或序列如何逼近某个特定的值、曲线或增长模式, 而不一定严格达到它.

这也是我们为什么需要渐近分析的理由, 它帮助我们在面对一个足够大的数据规模(数据规模一般为自然数)时, 仍能较好的对算法的运行时间进行估计. 我们来回顾已经遇到过的两个渐近符号: $\Theta$ 和 $O$, 它们本质上是作用于函数的. 我们先将这个 $T(n)$ 所逼近的函数记作 $g(n)$, 对于 $T(n)$ 来说, 这两种渐近符号就是与 $g(n)$ 和其自身有关的集合, 即 $T(n)\in \Theta (g(n))$ (所以前文说 $=$ 是非形式化的).

既然如此, 那让我们来对这个集合做正式定义:

$\Theta$ 记号

$$\begin{array}{rl}& \Theta (g(n))=\\ & \{f(n)|\exists c_1,c_2>0,n_0>0:\forall n\ge n_0,0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\}\end{array}$$ $\Theta$ 是本书中常用的渐近符号, 我们来分析一下这个定义:

• $f(x)$ 是这个记号所代表集合的成员, 例如我们之前用的$T(n)$.
• 条件是: 存在正常量 $c_1,c_2$ 和 $n_0$, 使得所有的 $n>n_0$ 有 $0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$. 其中 $n_0$ 是一个临界值, 这个临界值之后(包括自身)的所有 $n$ 都满足渐近关系.

在这里我们通过两个系数正常量 $c_1,c_2$, 控制两个 $g(n)$ 使得这两个 $g(n)$ 把 $f(n)$ 夹在中间. 反着来说, 如果 $f(n)$ 在 $n_0$ 之后被夹在 $c_1\cdot g(n)$ 和 $c_2\cdot g(n)$ 中, 那么 $f(n)\in \Theta (g(n))$, 并称 $g(n)$ 是 $f(n)$ 的 渐近紧确(上下)界(Asymptotic Tight Bound), 简称 (紧)确界 .

xychart-beta
    title "紧确上下界示例"
    x-axis 0 --> 30
    y-axis 0 --> 80
    line [3, 0, 7, 8, 16, 32, 64, 128]
    line [2, 4, 6, 8, 10, 12, 14, 16]
    line [1, 10, 9, 8, 7, 6, 5, 4]

在上面这个图例中, 起点为 $2$ 的函数为 $f(x)$, $1$ 函数为 $c_{1}g(n)$, $3$的函数为 $c_{1}g(n)$. 在 $y=8$ 前面它们的大小很难看出规律, 在 $y=8$之 后显现出$c_{1}g(n)\le f(n)\le c_{2}g(n)$, 此时 $n=13$. 所以 $n_0=13$ 时, $f(x)=\Theta (g(n))$, 这个时候夹逼的两个系数为 $c_1,c_2$.

在分析算法一节中, 我们发现最高阶项决定一切, 从而将一个函数转化为关于$\Theta$渐近形式, 这在直觉上是对的, 不过现在我们要来证明:

假设, 我们的想法是对的, 那么, 对于$\frac{n^3}{1000}-100n^2-100n+3$ $$c_1{n}^3<\frac{n^3}{1000}-100n^2-100n+3<c_2{n}^3$$ 用$n^3$除以上式得: $$c_1<\frac{1}{1000}-\frac{100}{n}-\frac{100}{n^2}+\frac{100}{n^3}<c_2$$ 对于上面的 $\frac{1}{1000}-\frac{100}{n}-\frac{100}{n^2}+\frac{100}{n^3}$ 变形, 得 $\frac{1}{1000}-100\left(\frac{n^2+n-1}{n^3}\right)$.

因为 $n\in \mathbb{N}$, 所以上式最大肯定无法到达 $\frac{1}{1000}$, 可以让$c_2=\frac{1}{1000}$.

接着想要找到一个不小于零的最小值, 由于该式的特殊性, 这一步比较难, 设 $f(x)=\frac{1}{1000}-\frac{100}{n}-\frac{100}{n^2}+\frac{100}{n^3}$, 可利用计算机求得: $f(100000)\approx -0.0000000099$, $f(100001)\approx 0.0000000000003$, 所以可以让 $c_1=10^{-13}$.

所以, 现在选择 $c_1=10^{-13}$, $c_2=\frac{1}{1000}$, $n_0=100001$即可证明 $\frac{n^3}{1000}-100n^2-100n+3=\Theta (n)$.

利用反证法, 我们也可以证明 $6n^3\ne \Theta (n^2)$: 假设存在 $c_2$ 和 $n$, 使得对所有 $n\ge n_0$, 有 $6n^3\le c_2{n}^2$. 然而用 $n^2$ 除该式, 得 $n\le \frac{c}{6}$, 因为 $c$ 为常量, 所以对任意大的 $n$, 该不等式不可能总成立.

上面的仅作为例子, 对于任意二次函数的证明可以参考练习与回答.

照这样, 我们也可以把其他的记号都定义出来:

$O$ 记号1

$O$ 记号在历史上出现的最早, 也最为常用(因为不需要像$\Theta$同时保证一个下界, 因此无需更复杂的数学证明)². $$O(g(n))=\{f(x)|\exists c>0,n_0\in \mathbb{N}:\forall n\ge n_0,|f(n)|\le c\cdot |g(n)|\}$$

在定义下一个记号之前让我们先缓一下, 在二分查找一节中我们提到了下面这个问题:

在上述算法中, 插入排序可以在$\Theta (nk)$时间内排序每个长度为$k$的$n/k$个子表(每个子表排序的时间复杂度为$\Theta (k^2)$, 故$T(n)=\Theta (k^2)\cdot (n/k)=\Theta (nk)$). 同样不难看出, 合并子表的时间复杂度是$\Theta (n\log (n/k))$, 综上就有该算法最坏情况下的时间复杂度为$\Theta (nk+n\log (n/k))$. 为了确保任何$k$的取值不能使修改后算法时间复杂度高于原算法, $k=O(\log n)$.

让我们来尝试证明它: 这里的核心部分是: 对于$\Theta (nk+n\log (n/k))$, 若$\Theta (nk+n\log (n/k))\le \Theta (n\log n)$³, 试求$k$的取值.

首先观察$\le \Theta (n\log n)$, 说明$nk+n\log (n/k)$的渐近增长率⁴不超过$n\log n$, 应用我们刚刚所学的$O$符号就可以把不等式转换成: $$nk+n\log (n/k)=O(n\log n)$$

我们需要展示存在常数 $c>0$ 和 $n_0$ , 使得对于所有 $n\ge n_0$, 有: $$nk+n\log \left(\frac{n}{k}\right)\le c\cdot n\log n$$

两边同时除以$n$(假设 $n>0$): $$k+\log \left(\frac{n}{k}\right)\le c\log n$$

展开 $\log \left(\frac{n}{k}\right)=\log n-\log k$, 并变形得: $$k-\log k\le (c-1)\log n$$

为了对于所有的$n$, 使上面表达式都成立, 我们需要考虑两种情况:

1. $k$ 为常数(即 $k=O(1)$)

那么 $k-\log k$ 也是常数.

因为 $(c-1)\log n$ 将会随 $n$ 的增长趋向于无穷大

所以, 对于任何常数 $k$, 存在 $n_0$ 使得对于 $n\le n_0$, 不等式成立. 此时: $$\begin{gathered} \because nk=O(n) \\ n\log \left(\frac{n}{k}\right)=n\log n-n\log k=\Theta (n\log n) \\ \therefore nk+n\log (n/k)=\Theta (n\log n) \end{gathered}$$

$\Theta (n\log n)$ 是满足要求的, 因为我们只需要保证渐近增长率不超过 $n\log n$ 即可, 同时满足下界当然是可以的, 这也体现了在某些条件下$O$与$\Theta$的相互转换.

2. $k$ 随 $n$ 增长

由原不等式变形可得: $k-\log k=O(\log n)$. 下面的严谨证明我们需要用到下一节的内容, 这里我们简单思考一下:

一般情况下($k\in \mathbb{C}\text{且}|k|\to \infty$), $\log k$的渐近增长率总小于$k$, 所以上式等价于: $$k=O(\log n)$$

$\Omega$ 符号

很显然, $O$是上界, $\Theta$是上下界都有, 那么此处的$\Omega$就应该能猜到是下界: $$\Omega (g(n))=\{f(n)|\exists c>0,n_0\in \mathbb{N}:\forall n\ge n_0,|f(n)|\ge c\cdot |g(n)|\}$$ 与上界的定义非常相似, 不证而明.

上面这三个渐近符号都有一个特点: 紧, 这里的上下界都是可达到的, 下一节中的内容则允许不达到. 另外我们还有另外一种定义方法, 通过函数来反向定义, 如: $$\begin{array}{rl}& f(n)=\Theta (g(n))\\ & ⟺\exists c_1>0,c_2>0,n_0\in \mathbb{N},\\ & \forall n\ge n_0,c_1\cdot |g(n)|\le |f(n)|\le c_2\cdot |g(n)|\end{array}$$ 这对于其他几种渐近符号也是通用的.

练习与回答

1. 试较严格地证明函数 $f(n)=3n^2+2n+5$ 是 $\Theta (n^2)$.

证明

根据定义, 需找到常数 $c_1,c_2>0$ 和 $n_0\ge 1$, 使得对所有 $n\ge n_0$, 有: $$c_1{n}^2\le 3n^2+2n+5\le c_2{n}^2$$

当 $n\ge 1$ 时, $2n\le 2n^2$ 和 $5\le 5n^2$ 因此: $$f(n)=3n^2+2n+5\le 3n^2+2n^2+5n^2=10n^2$$ 取 $c_2=10$, 当 $n\ge 1$ 时, 上界成立.

当 $n\ge 1$ 时, $2n$ 和 $5$ 均为非负数, 因此: $$f(n)=3n^2+2n+5\ge 3n^2$$ 取 $c_1=3$, 当 $n\ge 1$ 时, 下界成立.

综上, 取 $c_1=3$, $c_2=10$, $n_0=1$, 满足 $\Theta (n^2)$ 的条件. 因此, $f(n)=\Theta (n^2)$.

2. 判断以下函数的渐近关系:
   • $f(n)=n^3+7n$ 与 $g(n)=n^3$
   • $f(n)={\log }_{2}n$ 与 $g(n)={\log }_{3}n$

由题意, 易知上述两者均有$f(n)=\Theta (g(n))$. 详细证明略.

3. 严格证明任意二次函数$f(x)=\Theta (n^2)$.

对任意二次函数的证明

对于任意二次函数$f(x)=a{x}^2+bx+c$:

需找到常数 $c_1,c_2>0$ 和 $n_0\ge 1$, 使得对所有 $n\ge n_0$, 有: $$c_1{n}^2\le a{n}^2+bn+c\le c_2{n}^2$$

当 $n$ 充分大时, 线性项 $bn$ 和常数项 $c$ 可以被 $n^2$ 放大: $$bn\le |b|n\le |b|n^2(\text{当 }n\ge 1)$$ $$c\le |c|\le |c|n^2(\text{当 }n\ge 1)$$ 因此: $$f(n)=a{n}^2+bn+c\le a{n}^2+|b|n^2+|c|n^2=\left(a+|b|+|c|\right)n^2$$ 取 $c_2=a+|b|+|c|$, 则对所有 $n\ge 1$, 上界成立.

若 $a>0$, 当 $n$ 充分大时, 二次项 $a{n}^2$ 将主导其他项. 选择 $n_0$ 使得: $$|bn|\le \frac{a}{2}{n}^2\text{且}|c|\le \frac{a}{2}{n}^2$$ 这等价于: $$n\ge \max \left(\frac{2|b|}{a},\sqrt{\frac{2|c|}{a}}\right)$$ 取 $n_0=\max \left(1,\frac{2|b|}{a},\sqrt{\frac{2|c|}{a}}\right)$, 则对所有 $n\ge n_0$: $$f(n)=a{n}^2+bn+c\ge a{n}^2-|bn|-|c|\ge a{n}^2-\frac{a}{2}{n}^2-\frac{a}{2}{n}^2=\frac{a}{2}{n}^2$$ 取 $c_1=\frac{a}{2}$, 则下界成立.

在 $a\ne 0$ 的情况下, 上述分析对任意二次函数均成立.

1. 有时也可读作或简单的记作 Big-O. 事实上, 其他两种符号也可对应的称作 Big-Theta 和 Big-Omega. 但这两者远没有 Big-O 使用得多. ↩

2. 与等号的非形式化运用相似, 这里是对于渐近符号的不等式非形式化运用. 此处严格可表示为: $\Theta (nk+n\log (n/k))\subseteq \Theta (n\log n)$ ↩

3. 渐近增长率(Asymptotic Growth Rate) 是计算机科学和数学中用于描述函数在输入规模 $n$ 趋近于无穷大时的增长趋势的一种工具. 可以简单理解为渐近增长率就是一个函数渐近分析后的结果. ↩

4. 从技术上来讲, 因为不明确下界, 所以一般通过 $O$ 来描述一个算法的最坏情况. 然而, 绝大部分算法的最坏和最优情况的上下界都不相同, 再加上对一个算法的平均情况描述, 大多数时候就是最坏情况描述, 所以, 其实绝大部分渐近符号都只是在描述一个算法的最坏情况, 本书不对其进行过多区分. ↩

非紧渐近符号

算法的时间复杂度

在了解接下来的非紧渐近符号之前, 我们先来思考如何用一般(紧)渐近符号描述一个算法的时间复杂度.

$\Theta$ 的充要条件定理

我们以一个定理来引入, 即渐近符号的夹逼定理, 或者更正式的称为:

Theta 的充要条件定理 (Theorem on the equivalence of $\Theta$ and the combination of $O$ and $\Omega$)

如下: 对于两个正函数 $f(n)$ 和 $g(n)$, 有: $$f(n)=\Theta (g(n))\text{当且仅当}f(n)=O(g(n))\text{且}f(n)=\Omega (g(n))$$

这个定理说明了 Big-Theta 符号是 Big-O 和 Big-Omega 的“交集”. 其证明也非常的简单, 可以通过分别证明充分性和必要性解决. 通过前面的学习, 完成它应该不是什么大问题, 故本书不再赘述.

通过这个定义, 我们可以更好的了解算法的时间复杂度是怎么表示的. 在之前我们已经聊过这个问题了, 现在再深入地解决一下:

• 所有的符号都并非只是描述算法的一种情况, 我们一般给出三种情况: 最坏, 最优(好)和一般¹, 在无特定规定下, 符号描述可以参照脚注2².
• $O(g(n))$ 表示在对应情况下, 算法的时间复杂度不超过 $g(n)$ 的常数倍.
• $\Omega (g(n))$ 表示在对应情况下, 算法的时间复杂度至少为 $g(n)$ 的常数倍.
• $\Theta (g(n))$ 表示在对应情况下, 算法的时间复杂度总在 $g(n)$ 的两个常数倍之间.
• 以上三个表达都只是简单描述, 任何需要专业化的表达, 最好参照前面的定义进行.

$o$ 符号

接下来, 我们来看今天的主题——非紧渐近符号: 非紧渐近符号们提供了 非紧界(Non-tight bounds). 它们有时也被称为 严格渐近符号(Strict asymptotic notation) 或 小记号(Little notations)³.

我们来看 $o$ 符号的定义: $$o(g(n))=\{f(n)|\forall c>0,\exists n_0\in \mathbb{N},\forall n\ge n_0:|f(n)|<c\cdot |g(n)|\}$$

与 $O$ 主要区别在于: 在 $f(n)=O(g(n))$ 中, 界 $0\le f(n)\le cg(n)$ 对某个常量 $c>0$ 成立, 在 $f(n)=o(g(n))$ 中, 界 $0\le f(n)<cg(n)$ 对所有常量 $c>0$ 成立. 这也就是说, 在 $o$ 记号中, 当 $n$ 趋向于无穷大时, $f(n)$ 对于 $g(n)$ 就微不足道了, 即: $$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$$

关于非紧界这个描述, 是因为 $O$ 包含同阶函数而 $o$ 反之. 如, $f(n)=O(n)$ 但 $f(n)\ne o(n)$. 同理, 可以推出 $f(n)=o(g(n))\Rightarrow f(n)=O(g(n))$. 在本章节的练习与回答中, 也可以通过这种方法判断正误.

$\omega$ 符号

不严谨地说, 它与 $o$ 符号相反. 我们可以利用 $o$ 来定义它, 下面这个定义同样是它的一个性质: $$f(n)\in w(g(n))\text{当且仅当}g(n)\in o(f(n))$$ 形式化的定义是: $$\omega (g(n))=\{f(n)|\forall c>0,\exists n_0\in \mathbb{N},\forall n\ge n_0:|f(n)|>c\cdot |g(n)|\}$$

同样地, 我们有 $f(n)=\omega (g(n))\Rightarrow f(n)=\Omega (g(n))$. 例如, $n^2=\omega (n)$ 但 $n^2\ne \omega (n^2)$ 不过 $n^2=\Omega (n^2)$.

同时还要注意, 我们使用的是 $\Rightarrow$, 这意味着关于 Big-O 和 little-o, Big-Omega 和 little-omega 上面这两个结论都不可逆.

另外我们同样有个极限表达: $$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty$$

Warning

该章节仍在编写, 欢迎在 GitHub仓库 提交PR贡献内容.

练习与回答

1. 判断下列关于 Big-O 和 little-o 的陈述是否正确.
   • $3n^2+5n=O(n^2)$
   • $3n^2+5n=o(n^2)$
   • $\sqrt{n}=o(n)$
   • $\log n=O(n)$
   • $\log n=o(n)$

$3n^2+5n=o(n^2)$ 错误, 正确的应该是 $3n^2+5n=O(n^2)$ 或 $3n^2+5n=o(n^3)$. 其余四个均正确.

2. 根据已知内容, 判断下列关于 Big-Omega 和 little-omega 陈述是否正确.

已知:

• 若 ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty$, 则 $f(n)=\omega (g(n))$
• 若 ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=c>0$, 则 $f(n)=\Theta (g(n))\subseteq \Omega (g(n))$, 但不是 $\omega$

则判断:

• $f(n)=n^3$, $g(n)=n^2$ 是否满足 $f(n)=\omega (g(n))$
• $f(n)=5n\log n$, $g(n)=4n\log n$ 是否满足 $f(n)=\omega (g(n))$
• $f(n)=n\log n$, $g(n)=n$ 是否满足 $f(n)=\omega (g(n))$ 又满足 $f(n)=\Omega (g(n))$

对于上面已知内容, 可以在下一节具体学习. 以上除第2题以外都正确, 通过极限法证明即可.

Warning

该章节仍在编写, 欢迎在 GitHub仓库 提交PR贡献内容.

1. 事实上为: 最坏情况(Worst-case)、最好情况(Best-case)、平均情况(Average-case)、摊还情况(Amortized) ↩

2. 对于算法的最坏情况, 一般使用$O$；对于算法的平均情况, 一般使用$\Theta$；对于算法的最好情况, 一般使用$\Omega$. ↩

3. $o$(little-o) 是 $O$(Big-O) 的小记号. $\omega$(little-omega) 是 $\Omega$(Big-Omega) 的小记号. 当然可以！下面我们先简要回顾一下这四个渐近符号的定义, 然后设计一系列由浅入深的练习题, 帮助你清晰地区分 Big-Omega (Ω)、little-omega (ω)、Big-O (O) 和 little-o (o). ↩

思考与提高

最高阶项决定一切

我们发现最高阶项决定一切, 从而将一个函数转化为关于$\Theta$渐近形式, 这在直觉上是对的.

像上面这样, 在本书中我们多次提到 最高阶项决定一切, 大部分情况下它是正确的. 但需要更严谨的表述. “最高阶项决定一切” 这种表述很显然是基于多项式, 事实上它在多项式条件下确实是对的.

也就是说: 对于实系数多项式, 其渐近行为由最高次项决定. 严格的定理如下:

定理

设 $$f(n)=a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_0,a_k\ne 0$$ 则当 $n\to \infty$ 时, $$f(n)\sim a_k{n}^k\text{即}\underset{n\to \infty }{\lim }\frac{f(n)}{a_k{n}^k}=1$$

证明

$$\frac{f(n)}{a_k{n}^k}=\frac{a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_0}{a_k{n}^k}=1+\frac{a_{k-1}}{a_k}\cdot \frac{1}{n}+\frac{a_{k-2}}{a_k}\cdot \frac{1}{n^2}+\cdots +\frac{a_0}{a_k}\cdot \frac{1}{n^k}$$

当 $n\to \infty$, 所有 $\frac{1}{n^j}\to 0$（$j\ge 1$）, 所以:

$$\underset{n\to \infty }{\lim }\frac{f(n)}{a_k{n}^k}=1$$

即 $f(n)\sim a_k{n}^k$

由此可得:

• $f(n)=\Theta (n^k)$
• $f(n)=O(n^k)$
• $f(n)=\Omega (n^k)$

该证明相当简单, 且与直觉相符, 是一种显而易见的证明.

但数学中的函数并不只有这些, 我们还有一些常见的函数, 例如指数函数, 沿用上述证明，进一步推广也是有效的. 也就是说对于指数函数, 我们同样有最高阶项决定一切这样的表述.

然而有一些函数不满足我们上面的这个表述, 常见的是非加性结构: $T(n)=2T(n/2)+n$, 这种结构不能靠上面的方法直接证明, 相反，我们需要下一章将学到的主定理等工具. 这里暂时不做讨论. 另外振荡或交替项也很难探讨, 如 $f(n)=n+(-1{)}^{n}n$, 它们不收敛, 在极限讨论的时候，主导行为也相当复杂. 另外, 对数函数和 $e^n$ 这些不同函数混合的情况，也要进行单独考虑.

主导项

事实上, 在渐近分析中，真正重要的是 主导项（dominant term），即随着 $n\to \infty$，其占比趋于 1 的项。

若函数可写为和式： $$f(n)=f_1(n)+f_2(n)+\cdots +f_m(n)$$ 且存在某个 $f_i(n)$，使得对所有 $j\ne i$， $$\underset{n\to \infty }{\lim }\frac{f_j(n)}{f_i(n)}=0$$ 则称 $f_i(n)$ 为主导项，且 $$f(n)\sim f_i(n),\text{即 }f(n)=(1+o(1))f_i(n)$$

这就是 “主导项决定渐近行为” 的一般原则。

在渐近分析中，“最高次项决定一切” 是一个常见但需要谨慎理解的说法。它在许多情况下是成立的，尤其对于多项式函数或具有主导项的函数，但在更一般的情形下需要附加条件。

Warning

该章节仍在编写, 欢迎在 GitHub仓库 提交PR贡献内容.

后记

匿名函数

匿名函数(Anonymous Function) 是一种没有显式名称的函数, 它可以在需要时直接定义并使用.

可以从多个角度来理解什么是匿名函数. 我们可以先了解数学层面的匿名函数是怎样的:

$x\mapsto x^2+1$

上面这个函数表示将一个输入 $x$ 映射到 $x^2+1$ 这个函数. 我们没有给这样的一个函数命名(如$f$或$g$), 但确实明确表达了函数的行为, 有着“即用即弃”的特点, 常用于高阶运算, 比如积分、微分、函数组合等场景中临时构造函数, 如: $\int (x\mapsto x{e}^{-x}),dx$.

在本章的算法学习中, 我们明白所有的渐近符号都是对函数而言的, 如 $O(g(n))$, 那么像$\Theta (n^2)$这样的情况我们就知道它是在干什么了, 这里面$n^2$并非表示一个代数式, 而是表示一个匿名函数. 例如:

$2n^2+\Theta (n)=\Theta (n^2)$¹

这表示: “存在某个属于 $\Theta (n)$ 的函数 $f(n)$, 使得 $2n^2+f(n)$ 的增长阶是 $\Theta (n^2)$”.

其中, 这个 $f(n)$ 在原始的式子中并没有提到, 是我们后面才给其命了一个名字, 所以其于原始的式子就是一个匿名函数.

在编程中, 我们也用各种各样的方法来表示这类匿名函数, 常见的叫法叫 Lambda 函数(Lambda Function, 或 Lambda 表达式):

List<Integer> numbers = Arrays.asList(1, 2, 3);
numbers.forEach(n -> System.out.println(n));

或者叫箭头函数²:

const add = (a, b) => a + b;
[1, 2, 3].map(x => x * 2); // [2, 4, 6]

在我们Rust中, 则通常叫做闭包(closure):

fn main() {
    // 它没有名字, 但可绑定到其他变量
    let square = |x| x * x;
    println!("5 的平方是: {}", square(5));
    let base = 7;

    // 还能捕获外部作用域的变量
    let factor = 3;
    let multiply = |x| x * factor; // 匿名函数使用了外部变量 `factor`
    println!("10 * factor = {}", multiply(10));

    // 以及类型推导
    let numbers = vec![1, 2, 3, 4, 5];
    let evens: Vec<_> = numbers.iter().filter(|&x| x % 2 == 0).collect();
    println!("{:?}", evens);
    // 关于迭代器相关知识, 可以参照上一章的后记
}

渐近符号非形式化运用规范

1. 渐近符号一般出现在右边. $$f(n)=O(g(n))\text{表示}f(n)\in O(g(n))$$

$$O(g(n))=f(n)\text{是无意义的}$$

另外, 显而易见的 $O(n^2)$ 包含比 $O(n)$ 更多的函数(比如 $n^2\in O(n^2)$, 但 $n^2\notin O(n)$), 所以$O(n^2)=O(n)$是错误写法.