4.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\) 。另一种语言可能会做不同的事。

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