1. 数值问题¶

1.1. 数值问题¶

1.1.1. 引言¶

本模块介绍各种与数字上的数学运算相关的算法。例如乘两个数或把某个数乘方到给定幂这样的活动。特别是，当由于被运算的值太大而无法使用内置的整数或浮点运算时，我们会讨论相应的情况。对多项式或矩阵的运算也有类似的分析。

既然我们不能依赖硬件用一次常数时间操作来处理输入，我们就想知道如何最有效地实现该运算以最小化时间代价。这就引出了一个问题：我们应该如何对输入规模应用通常的、关于增长率的渐近代代价度量。第一，加法或乘法的一个实例是什么？操作数的每个值都产生一个不同的问题实例。而乘两个数时输入规模又是什么？如果我们把输入规模视为二（因为输入了两个数），那么任何非常数时间的算法的增长率相对于输入的增长都是无限高的。这毫无意义，尤其考虑到我们从小学算术中就知道，随着所涉及数值的增大，数的加法和乘法确实变得更难。事实上，我们从标准的学校算法中知道：标准加法的代价与被加数字的位数成线性关系，而用一个 $m$ 位数乘一个 $n$ 位数时，乘法代价为 $n \times m$。

当我们执行对输入规模敏感的数值算法时，操作数的位数看起来确实是要考虑的关键因素。对一个合适的对数底来说，位数就是数值的对数。因此，为了计算算法的渐近增长率，我们将把输入值的"规模"视为该值的对数。基于这一观点，有许多似乎与此类运算相关的特征。

对大数值进行算术运算的代价并不低廉。
值 $n$ 仅有一个实例。
长度小于或等于 $k$ 的实例有 $2^k$ 个。
值 $n$ 的大小（长度）为 $\log n$ 。
当 $n$ 的值增大时（例如从 $2^k-1$ 增至 $2^k$ 再增至 $2^k+1$ ），特定算法的代价可能会降低，但通常会在 $n$ 的长度增加时上升。

1.1.2. 求幂¶

我们开始考察标准数值算法时，先考虑如何求幂。也就是说，如何计算 $m^n$？我们可以总共用 $n-1$ 次乘法乘以 $m$。我们能做得更好吗？能，有一个我们可以使用的简单分治方法。可以意识到，当 $n$ 为偶数时， $m^n = m^{n/2}m^{n/2}$。如果 $n$ 为奇数，那么 $m^n = m^{\lfloor n/2\rfloor}m^{\lfloor n/2\rfloor}m$。这引出下面的递归算法:

int Power(int base, int exp) {
  int half, total; if exp = 0 return 1; half = Power(base, exp/2); total = half * half; if (odd(exp)) then total = total * base; return total;
}

函数 Power 有递推关系

\[\begin{split}f(n) = \left\{ \begin{array}{ll} 0&n=1\\ f(\lfloor n/2\rfloor) + 1 + n \bmod 2&n>1 \end{array} \right.\end{split}\]

它的解是

\[f(n) = \lfloor \log n\rfloor + \beta(n) - 1\]

其中 $\beta$ 是 $n$ 的二进制表示中 1 的个数。

这个代价与问题规模相比如何？原始问题规模是 $\log m + \log n$，而所需的乘法次数是 $\log n$。这比进行 $n-1$ 次乘法要好得多（实际上是指数级地好）。

1.1.3. 最大公因子¶

接下来我们将介绍欧几里得算法，用于求两个整数的最大公因子（LCF）。 LCF 是能整除两个输入的最大整数。

首先我们有这样的观察：如果 $k$ 整除 $n$ 和 $m$，那么 $k$ 整除 $n - m$。我们知道这是真的，因为如果 $k$ 整除 $n$，那么对某个整数 $a$ 有 $n = ak$；如果 $k$ 整除 $m$，那么对某个整数 $b$ 有 $m = bk$。所以，$LCF(n, m) = LCF(n-m, n) = LCF(m, n-m) = LCF(m, n)$。

现在，对任何值 $n$，存在 $k$ 和 $l$ 使得

\[n = km + l\ \mbox{where}\ m > l \geq 0.\]

由 $\bmod$ 函数的定义，我们可以推出这样的事实：

\[n = \lfloor n/m \rfloor m + n \bmod m.\]

因为 LCF 是 $n$ 和 $m$ 的因子，又因为 $n = km + l$，所以 LCF 必定是 $km$ 和 $l$ 两者的因子，也是这些项各自的最大公因子。由此可知，$LCF(n, m) = LCF(m, l) = LCF(m, n \bmod m)$。

这个观察引出一个简单的算法。我们假设 $n \geq m$。每次迭代我们用 $m$ 替换 $n$，用 $n \bmod m$ 替换 $m$，直到把 $m$ 驱动到零:

int LCF(int n, int m) {
  if (m == 0) return n;
  return LCF(m, n % m);
}

要确定这个算法有多昂贵，我们需要知道每步我们取得了多少进展。注意，两次迭代之后，我们用 $n \bmod m$ 替换了 $n$。所以关键问题变成： $n \bmod m$ 相对于 $n$ 有多大？

\[\begin{split}\begin{eqnarray*} n \geq m &\Rightarrow& n/m \geq 1\\ &\Rightarrow& 2\lfloor n/m\rfloor > n/m\\ &\Rightarrow& m\lfloor n/m\rfloor > n/2\\ &\Rightarrow& n - n/2 > n - m\lfloor n/m\rfloor = n \bmod m\\ &\Rightarrow& n/2 > n \bmod m \end{eqnarray*}\end{split}\]

因此，函数 LCF 至多经过 2 次迭代就会把它的第一个参数减半。于是总代价为 $O(\log n)$。

OpenDSA 完整目录

Chapter 26 Number Problems

1. 数值问题¶

1.1. 数值问题¶

1.1.1. 引言¶

1.1.2. 求幂¶

1.1.3. 最大公因子¶