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 次对数运算。

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