数据结构与算法 / 系统课时
指数与对数
指数与对数
二分查找、平衡树和分治算法都在反复缩小问题规模。要准确理解这类算法的执行轮数,需要掌握指数、对数及换底关系,并把“每轮缩小一半”转换成对数表达式。
学习目标
- 理解指数与对数的互逆关系及其合法取值范围。
- 能够使用换底公式比较不同底数的对数。
- 能够推导二分过程的轮数与 复杂度。
核心原理
指数表达式 表示把底数 按指数规则扩展到结果 。对数回答相反的问题:底数 的多少次方等于 。
实数范围内,底数必须满足 且 ,真数必须满足 。常见底数包括 、 和自然常数 。
下面各公式要求对数底数合法,真数 x、y 为正,幂指数 k 可为实数。
不同底数可以通过换底公式转换:
复杂度中的对数通常默认固定且大于 1 的底数。因为 与 只相差一个常数因子,而大 记号会忽略固定常数。
二分过程为何是对数
先约定教学用的缩半过程:每次把正整数规模 m 变成 ,到 1 就停止。对正整数重复向上取整后,第 k 轮余下 。可按 k 归纳,或注意 与 都是使两倍结果不小于 x 的最小整数。到 1 的条件是 ,所以恰需 轮。
标准迭代二分查找每轮先检查一个中点,再排除中点及另一半,未命中时剩余至多 个位置,到空区间才停止。非空输入最坏检查 次。n=0 时直接返回未命中,检查 0 次。这里假定升序且按下标访问和比较均为常数时间,迭代辅助空间为常数,递归版还需计算调用栈。
| 初始规模 n | 向上取整缩到 1 | 二分最坏检查位置 |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 8 | 3 | 4 |
| 10 | 4 | 4 |
| 64 | 6 | 7 |
易错点
- 把 误认为 。前者表示缩半次数,后者表示缩半一次后的规模。
- 忽略向上取整。规模为 10 时,向上取整缩到 1 需要 4 轮。先确定终点和取整规则,再使用公式。
- 对 或负数取实数对数。算法推导前应确认问题规模为正数。
- 认为所有嵌套循环都是 。若循环变量每次乘以 ,迭代次数通常是 。
用整数精确计算轮数
Python 正整数的 bit_length 给出二进制位数。正整数 n 的上取整二进制对数等于 (n−1) 的位数,避免浮点对数在整数边界舍入。二分最坏检查数则是 n 的位数。
python
def halving_rounds(size):
if size < 1:
raise ValueError("size 必须为正整数")
rounds = 0
while size > 1:
size = (size + 1) // 2
rounds += 1
return rounds
def ceil_log2(size):
if size < 1:
raise ValueError("size 必须为正整数")
return (size - 1).bit_length()
def worst_binary_visits(size):
if size < 0:
raise ValueError("size 必须是非负整数")
visits = 0
while size:
visits += 1
size //= 2 # 取排除中点后的较大一侧
return visits
for n in (1, 2, 8, 10, 64, 2**53 + 1):
assert halving_rounds(n) == ceil_log2(n)
assert worst_binary_visits(n) == n.bit_length()
print(n, halving_rounds(n), worst_binary_visits(n))前五行的两列分别与表格一致。最后一行 n=9007199254740993,两列都是 54。若按固定比例缩小,还需保证每一步确实减少,避免整数取整导致在终点附近停滞。
本课总结
- 对数是指数的逆运算,用来回答“需要多少次幂才能达到目标”。
- 每轮按固定比例缩小问题规模时,执行轮数通常是对数级。
- 对数底数的变化只带来常数因子,因此复杂度中常写作 。
下一课预告
下一课学习直接证明与反证法,把上面的计数结论写成有前提、有推导、可复查的证明。
按自己的节奏,确认真正理解。