4.4.1. 对数¶

以 \(b\) 为底、值为 \(y\) 的 对数 是把 \(b\) 提升到该幂次即可得到 \(y\) 的那个幂次。通常，这写作 \(\log_b y = x\) 。因此，如果 \(\log_b y = x\) ，则 \(b^x = y\) ，且 \(b^{log_b y} = y\) 。

程序员经常使用对数。下面是两个典型用法。

在 OpenDSA 中，几乎所有使用的对数都以 2 为底。这是因为数据结构和算法最常把事物对半分割，或用二进制位存储编码。每当你在 OpenDSA 中看到记号 \(\log n\) ，要么意指 \(\log_2 n\) ，要么该词是按渐近意义使用的，因此实际的底并不重要。对于以 2 以外的任何底为底的对数，我们会显式写出底。

对于 \(m\) 、 \(n\) 和 \(r\) 的任意正值，以及任意正整数 \(a\) 和 \(b\) ，对数具有以下性质。

1. \(\log (nm) = \log n + \log m\) 。

2. \(\log (n/m) = \log n - \log m\) 。

3. \(\log (n^r) = r \log n\) 。

4. \(\log_a n = \log_b n / \log_b a\) 。

前两条性质说明，两个数相乘（或相除）的对数可以通过把这两个数的对数相加（或相减）得到。 [1] 性质 (3) 只是性质 (1) 的推广。性质 (4) 告诉我们，对于变量 \(n\) 和任意两个整数常数 \(a\) 和 \(b\) ， \(\log_a n\) 与 \(\log_b n\) 相差一个常数因子 \(\log_b a\) ，而与 \(n\) 的值无关。我们使用的大多数运行时间分析都属于忽略成本中常数因子的类型。性质 (4) 表明，这类分析无需关心对数的底，因为这只能以常数因子改变总成本。

一个有用的恒等式是：

为了对为什么该式成立给出一些直观理解：对 \(n\) 取（以 2 为底的）对数意味着什么？如果 \(\log_2 n = x\) ，那么 \(x\) 就是把 2 提升到该幂次即可回到 \(n\) 的那个幂次。所以，当对数的底为 2 时， \(2^{\log n} = n\) 当然成立。

讨论对数时，指数常常引起混淆。性质 (3) 告诉我们 \(\log n^2 = 2 \log n\) 。我们如何表示对数的平方（与 \(n^2\) 的对数相对）？这可以写作 \((\log n)^2\) ，但传统上使用 \(\log^2 n\) 。另一方面，我们可能想取 \(n\) 的对数的对数。这写作 \(\log \log n\) 。

当我们需要知道必须对一个数取多少次对数才能达到 \(\leq 1\) 的值时（这种情况很罕见），会使用一种特殊记号。该量写作 \(\log^* n\) 。例如， \(\log^* 1024 = 4\) ，因为 \(\log 1024 = 10\) ， \(\log 10 \approx 3.33\) ， \(\log 3.33 \approx 1.74\) ，且 \(\log 1.74 < 1\) ，总共是 4 次对数运算。

下面是一些操作对数的练习。