后记

匿名函数

匿名函数(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)$是错误写法.

2. 渐近符号不能随意代数运算. 不能随意消去和解方程之类(可以使用主定理, 我们将在下一章学到).

3. 等式中多个渐近符号, 跟主项有关. $$3n^2+O(n)=O(n^2)$$ 表示: 一个形如 $3n^2+h(n)$, 其中 $h(n)\in O(n)$ 的函数, 属于 $O(n^2)$. 但反过来就不一定成立: $$O(n^2)=3n^2+O(n)\text{错误}$$ 因为左边包含所有 $\le C{n}^2$ 的函数($C$为常数), 右边却强制主项是 $3n^2$, 显然不等价.

4. 链式等式中, 等号可以表示递推或属于关系.

5. 渐近符号与上下文相关, 例如$n\to \infty$, $n\to 0$表示的意思完全不同. 前文已经提到, 本书中一般表示$n\to \infty$.

1. 这里再次使用了一个渐近符号在等式中的非形式化运用. 参考本章中的渐近符号非形式化运用规范. ↩

2. 其实官方名称还是匿名函数, 不过Js社区普遍称之为箭头函数. ↩