3. 杂项数学记号¶

本模块汇集了若干数学术语和概念的定义，供需要时查阅。

计量单位 ： OpenDSA 模块对计量单位使用以下记号。 "B" 用作字节的缩写，"b" 表示位， "KB" 表示千字节 \((2^{10} = 1024\) 字节)， "MB" 表示兆字节 \((2^{20}\) 字节)， "GB" 表示吉字节 \((2^{30}\) 字节)， "ms" 表示毫秒 （1 毫秒是 1/1000 秒）。 当意指 2 的幂时，数字与单位缩写之间不放置空格。 因此，一个容量为 25 吉字节的磁盘驱动器（这里吉字节意指 \(2^{30}\) 字节）将写作 "25GB"。 当意指十进制数值时则使用空格。 因此 2000 位将写作 "2 Kb"，而 "2Kb" 表示 2048 位。 2000 毫秒写作 2000 ms。 注意，在本书中，大量存储几乎总是以 2 的幂来度量， 而时间则以 10 的幂来度量。

阶乘函数 ： 阶乘 函数，对大于 0 的整数 \(n\) 写作 \(n!\) ，是 1 到 \(n\) （含）之间所有整数的乘积。 于是， \(5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120\) 。 作为特例， \(0! = 1\) 。 阶乘函数随着 \(n\) 变大而快速增长。 由于直接计算阶乘函数是一个耗时的过程， 拥有一个能给出良好近似值的公式会很有用。 斯特林近似（Stirling's approximation）指出 \(n! \approx \sqrt{2\pi n}(\frac{n}{e})^n\) ， 其中 \(e \approx 2.71828\) （ \(e\) 是自然对数系统的底） [1]。 因此我们看到，虽然 \(n!\) 的增长 慢于 \(n^n\) （因为 \(\sqrt{2\pi n}/e^n < 1\) ）， 但对于任意正整数常数 \(c\) ，它的增长快于 \(c^n\) 。

排列 ： 序列 \(\mathbf{S}\) 的一个 排列 就是把 \(\mathbf{S}\) 的成员按某种顺序排列。 例如，整数 1 到 \(n\) 的一个排列 就是把这些值按某种顺序排列。 如果序列包含 \(n\) 个互不相同的成员， 那么该序列有 \(n!\) 个不同的排列。 这是因为排列的第一个成员有 \(n\) 种选择； 对第一个成员的每种选择，第二个成员有 \(n-1\) 种选择，依此类推。 有时人们希望获得一个序列的 随机排列 ， 即从 \(n!\) 个可能的排列中选出一个， 使得每个排列被选中的概率相等。 生成随机排列的一个简单函数如下。 这里，序列的 \(n\) 个值存储在 数组 A 的位置 0 到 \(n-1\) 中， 函数 swap(A, i, j) 交换数组 A 中的元素 i 和 j ， 而 Random(n) 返回 0 到 \(n-1\) 范围内的一个整数值。

// Randomly permute the values in array A
public static void permute(Object[] A) {
  for (int i = A.length; i > 0; i--) // for each i
    swap(A, i-1, random(i));         //   swap A[i-1] with a random
}                                    //   position in the range 0 to i-1.

// Randomly permute the values in array A
public static <T> void permute(T[] A) {
  for (int i = A.length; i > 0; i--) { // for each i
    swap(A, i-1, random(i));         //   swap A[i-1] with a random
  }
}                                    //   position in the range 0 to i-1.

//Randomly permute the values in array A
void permute(int A[], int n) {
  for (int i = n; i > 0; i--) // for each i
    swap(A, i-1, int(Random(i)));    //   swap A[i-1] with a random
                                     //   position in the range 0 to i-1.
}

布尔变量 ： 一个 布尔变量 是一个取 True 和 False 两个值之一的变量。 这两个值通常分别与值 1 和 0 相关联， 尽管没有理由必须如此。 依赖 0 与 False 之间的对应关系是一种糟糕的编程实践， 因为它们是逻辑上不同、类型也不同的对象。

逻辑记号 ： 我们偶尔会用到符号逻辑或布尔逻辑的记号。 \(A \Rightarrow B\) 表示" \(A\) 蕴含 \(B\) "或 "如果 \(A\) 则 \(B\) "。 \(A \Leftrightarrow B\) 表示" \(A\) 当且仅当 \(B\) " 或" \(A\) 等价于 \(B\) "。 \(A \vee B\) 表示" \(A\) 或 \(B\) " （在符号逻辑语境中或执行布尔运算时都很有用）。 \(A \wedge B\) 表示" \(A\) 且 \(B\) "。 \(\sim\!A\) 和 \(\overline{A}\) 都表示"非 \(A\) "， 即 \(A\) 的否定，其中 \(A\) 是一个布尔变量。

向下取整与向上取整 ： \(x\) 的 向下取整 （写作 \(\lfloor x \rfloor\) ） 接受实数值 \(x\) 并返回最大整数 \(\leq x\)。 例如， \(\lfloor 3.4 \rfloor = 3\) ， \(\lfloor 3.0 \rfloor\) 也是如此， 而 \(\lfloor -3.4 \rfloor = -4\) ， \(\lfloor -3.0 \rfloor = -3\) 。 \(x\) 的 向上取整 （写作 \(\lceil x \rceil\) ）接受实数值 \(x\) 并返回最小整数 \(\geq x\)。 例如， \(\lceil 3.4 \rceil = 4\) ， \(\lceil 4.0 \rceil\) 也是如此， 而 \(\lceil -3.4 \rceil = \lceil -3.0 \rceil = -3\) 。

取模函数 ： 取模 （或 模 ）函数返回整数除法的余数。 在数学表达式中有时写作 \(n \bmod m\) ， 而在许多程序设计语言中语法为 n % m 。 根据余数的定义， \(n \bmod m\) 是满足 \(n = qm + r\) 的整数 \(r\) ，其中 \(q\) 为整数， 且 \(|r| < |m|\) 。 因此，当 \(n\) 和 \(m\) 为正整数时， \(n \bmod m\) 的结果必须介于 0 和 \(m-1\) 之间。 例如， \(5 \bmod 3 = 2\) ； \(25 \bmod 3 = 1\) ， \(5 \bmod 7 = 5\) ， \(5 \bmod 5 = 0\) 。

给 \(q\) 和 \(r\) 赋值的方式不止一种， 取决于如何解释整数除法。 最常见的数学定义把取模函数计算为 \(n \bmod m = n - m\lfloor n/m\rfloor\) 。 此时， \(-3 \bmod 5 = 2\) 。 然而，Java 和 C++ 编译器通常使用底层处理器的机器指令 来计算整数运算。 在许多计算机上，这是通过截断所得分数来实现的， 即 \(n \bmod m = n - m (\mathrm{trunc}(n/m))\) 。 按此定义， \(-3 \bmod 5 = -3\) 。 另一种语言可能会做不同的事。

遗憾的是，对许多应用来说，这并不是用户想要或期望的。 例如，许多 散列系统 会对记录的 键 值进行某种计算， 然后对散列表长度取模。 这里的期望是结果成为散列表中的合法下标， 而不是一个负数。 散列函数的实现者必须要么确保计算结果始终为正， 要么在取模函数的结果为负时给该结果加上散列表长度。