我的算法书 - 对数

一句话算法

对数回答的是：底数要乘多少次，才能得到目标数。

问题模型

对数是指数运算的逆运算。

若：

a^x=b

其中 $a>0,a\ne 1,b>0$ ，则：

x=\log_a b

读作“以 $a$ 为底 $b$ 的对数”。

“对数”

$\log_a b$ 表示把 $a$ 连乘多少次可以得到 $b$ 。

在算法中，最常见的是以 $2$ 为底的对数：

\log_2 n

它表示从 1 开始，每次翻倍，翻多少次能到达 n 附近。

核心直觉

指数是“不断放大”：

1, 2, 4, 8, 16, 32, ...

对数是反过来问：

32 是 2 翻倍多少次得到的？

答案是：

2^5=32\Rightarrow \log_2 32=5

所以当一个算法每一步都把规模减半时：

n -> n/2 -> n/4 -> n/8 -> ...

它通常只需要约 $\log_2 n$ 步。

基本性质

由定义 $a^x=b\iff x=\log_a b$ 可以直接得到：

\log_a 1=0

因为 $a^0=1$ 。

\log_a a=1

因为 $a^1=a$ 。

\log_a(a^x)=x

因为对数和指数互为逆运算。

a^{\log_a b}=b

因为 $\log_a b$ 本来就是让 $a$ 变成 $b$ 的指数。

运算法则

下面默认 $a>0,a\ne 1,M>0,N>0$ 。

乘法变加法

\log_a(MN)=\log_a M+\log_a N

证明：

设：

x=\log_a M,\quad y=\log_a N

则：

M=a^x,\quad N=a^y

所以：

MN=a^x a^y=a^{x+y}

两边取以 $a$ 为底的对数：

\log_a(MN)=x+y=\log_a M+\log_a N

除法变减法

\log_a\frac{M}{N}=\log_a M-\log_a N

证明：

设：

x=\log_a M,\quad y=\log_a N

则：

\frac{M}{N}=\frac{a^x}{a^y}=a^{x-y}

两边取对数：

\log_a\frac{M}{N}=x-y=\log_a M-\log_a N

幂次提到前面

\log_a(M^k)=k\log_a M

证明：

设：

x=\log_a M

则：

M=a^x

所以：

M^k=(a^x)^k=a^{kx}

两边取对数：

\log_a(M^k)=kx=k\log_a M

由除法公式还能得到：

\log_a\frac{1}{N}=-\log_a N

换底公式

不同底数的对数可以互相转换：

\log_a b=\frac{\log_c b}{\log_c a}

其中 $c>0,c\ne 1$ 。

证明：

设：

x=\log_a b

则：

a^x=b

两边取以 $c$ 为底的对数：

\log_c(a^x)=\log_c b

使用幂次公式：

x\log_c a=\log_c b

所以：

x=\frac{\log_c b}{\log_c a}

代回 $x=\log_a b$ ：

\log_a b=\frac{\log_c b}{\log_c a}

常用推论：

\log_a b=\frac{1}{\log_b a}

算法中的常用推论

每次减半需要多少步

若一个规模为 $n$ 的问题，每一步都变成原来的一半，那么经过 $k$ 步后规模大约是：

\frac{n}{2^k}

当规模降到 $1$ 时：

\frac{n}{2^k}\le 1

等价于：

n\le 2^k

所以：

k\ge \log_2 n

因此二分查找、倍增跳跃、线段树高度等问题，经常出现 $O(\log n)$ 。

二进制位数

一个正整数 $n$ 的二进制位数是：

\lfloor \log_2 n\rfloor+1

因为若：

2^k\le n<2^{k+1}

则最高位的下标是 $k$ ，二进制位数是 $k+1$ 。

乘法规模转加法规模

若一个数量是很多因子的乘积：

X=a_1a_2\cdots a_m

取对数后：

\log X=\log a_1+\log a_2+\cdots+\log a_m

这在概率、组合计数、大数比较中常见：当乘积太大不能直接存时，可以比较对数和。

复杂度分析

对数本身是数学工具，不是某个固定算法。

在复杂度分析中：

$O(\log n)$ 通常表示问题规模按固定比例缩小。
$O(n\log n)$ 常见于排序、分治、线段树批量操作。
换底只差一个常数，因此复杂度里通常不写底数：

$\log_a n=\frac{\log_b n}{\log_b a}$
其中 $\log_b a$ 是常数。

代码实现

本文不提供代码模板。竞赛中若需要计算实数对数，可以使用 C++ <cmath> 中的 log、log2、log10。若要计算任意底：

cpp

        1
2
3

        double log_base(double a, double b) {
    return log(b) / log(a);
}

注意浮点误差：如果题目只需要整数的 $\lfloor\log_2 n\rfloor$ ，通常优先使用二进制位运算或预处理 Log 数组，而不是浮点对数。

测试用例

基础计算

\log_2 32=5

因为：

2^5=32

换底

\log_2 8=\frac{\log_{10}8}{\log_{10}2}=3

二分步数

若 $n=100$ ，每次减半：

100 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1

需要约 $7$ 步，而：

\lceil\log_2 100\rceil=7

应用分类详解

对数的本质是描述“指数增长的反方向”。看到翻倍、减半、树高、二进制位数、大乘积比较时，都应该想到对数。

一、复杂度分析

典型模式： 每一步把规模除以固定常数。

识别信号： 出现“折半”“翻倍”“倍增”“树高”。

核心建模： 问题规模经过 $k$ 步变为 $n/2^k$ ，令它小于等于 $1$ ，得到 $k=O(\log n)$ 。

应用场景	经典题目	核心思路
二分查找	有序数组查找	每次排除一半
倍增 LCA	树上祖先查询	每次跳 $2^k$ 级
线段树	区间查询修改	树高约为 $\log_2 n$

二、二进制与位数

典型模式： 需要知道一个数最高位在哪里。

识别信号： 出现“最高位”“二进制长度”“不超过 $n$ 的最大 $2^k$ ”。

核心建模： 最高位 $k$ 满足 $2^k\le n<2^{k+1}$ ，所以 $k=\lfloor\log_2 n\rfloor$ 。

三、大数比较

典型模式： 两个乘积或幂太大，不能直接计算。

识别信号： 出现很多数相乘、指数很大、只需比较大小。

核心建模： 对乘积取对数，把乘法变成加法，比较对数和。

经典例题

1. 二分查找最多比较次数

长度为 $n$ 的有序数组，每次比较后剩下一半候选，最多需要 $\lceil\log_2 n\rceil$ 级别的比较。

2. ST 表中的 `Log` 数组

预处理 Log[i] = floor(log2(i))，查询区间长度 len 时用 $2^k$ 覆盖，其中 $k=\lfloor\log_2 len\rfloor$ 。

3. 大幂比较

比较 $a^b$ 和 $c^d$ 的大小时，可以比较：

b\log a

和：

d\log c

避免直接计算巨大整数。

参考

本书二分查找章节：base/binary_search/index.md
本书 ST 表章节：base/sparse_table/index.md

一句话算法

问题模型

核心直觉

基本性质

运算法则

乘法变加法

除法变减法

幂次提到前面

换底公式

算法中的常用推论

每次减半需要多少步

二进制位数

乘法规模转加法规模

复杂度分析

代码实现

测试用例

基础计算

换底

二分步数

应用分类详解

一、复杂度分析

二、二进制与位数

三、大数比较

经典例题

1. 二分查找最多比较次数

2. ST 表中的 Log 数组

3. 大幂比较

参考

2. ST 表中的 `Log` 数组