数据结构与算法 / 系统课时

指数与对数

指数与对数

二分查找、平衡树和分治算法都在反复缩小问题规模。要准确理解这类算法的执行轮数,需要掌握指数、对数及换底关系,并把“每轮缩小一半”转换成对数表达式。

学习目标

  • 理解指数与对数的互逆关系及其合法取值范围。
  • 能够使用换底公式比较不同底数的对数。
  • 能够推导二分过程的轮数与 O(log⁡n)O(\log n) 复杂度。

核心原理

指数表达式 ax=ya^x=y 表示把底数 aa 按指数规则扩展到结果 yy。对数回答相反的问题:底数 aa 的多少次方等于 yy。

ax=y  ⟺  log⁡ay=xa^x=y\iff \log_a y=x

实数范围内,底数必须满足 a>0a>0 且 a≠1a\ne 1,真数必须满足 y>0y>0。常见底数包括 22、1010 和自然常数 ee。

下面各公式要求对数底数合法,真数 x、y 为正,幂指数 k 可为实数。

log⁡a(xy)=log⁡ax+log⁡ay\log_a(xy)=\log_a x+\log_a y
log⁡a(xy)=log⁡ax−log⁡ay\log_a\left(\frac{x}{y}\right)=\log_a x-\log_a y
log⁡a(xk)=klog⁡ax\log_a(x^k)=k\log_a x

不同底数可以通过换底公式转换:

log⁡bx=log⁡axlog⁡ab\log_b x=\frac{\log_a x}{\log_a b}

复杂度中的对数通常默认固定且大于 1 的底数。因为 log⁡2n\log_2 n 与 log⁡10n\log_{10}n 只相差一个常数因子,而大 OO 记号会忽略固定常数。

二分过程为何是对数

先约定教学用的缩半过程:每次把正整数规模 m 变成 ⌈m/2⌉\lceil m/2\rceil,到 1 就停止。对正整数重复向上取整后,第 k 轮余下 ⌈n/2k⌉\lceil n/2^k\rceil。可按 k 归纳,或注意 ⌈⌈x⌉/2⌉\lceil\lceil x\rceil/2\rceil 与 ⌈x/2⌉\lceil x/2\rceil 都是使两倍结果不小于 x 的最小整数。到 1 的条件是 2k≥n2^k\ge n,所以恰需 ⌈log⁡2n⌉\lceil\log_2 n\rceil 轮。

标准迭代二分查找每轮先检查一个中点,再排除中点及另一半,未命中时剩余至多 ⌊m/2⌋\lfloor m/2\rfloor 个位置,到空区间才停止。非空输入最坏检查 ⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor+1 次。n=0 时直接返回未命中,检查 0 次。这里假定升序且按下标访问和比较均为常数时间,迭代辅助空间为常数,递归版还需计算调用栈。

初始规模 n 向上取整缩到 1 二分最坏检查位置
1 0 1
2 1 2
8 3 4
10 4 4
64 6 7

易错点

  • 把 log⁡2n\log_2 n 误认为 n/2n/2。前者表示缩半次数,后者表示缩半一次后的规模。
  • 忽略向上取整。规模为 10 时,向上取整缩到 1 需要 4 轮。先确定终点和取整规则,再使用公式。
  • 对 00 或负数取实数对数。算法推导前应确认问题规模为正数。
  • 认为所有嵌套循环都是 O(n2)O(n^2)。若循环变量每次乘以 22,迭代次数通常是 O(log⁡n)O(\log n)。

用整数精确计算轮数

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。若按固定比例缩小,还需保证每一步确实减少,避免整数取整导致在终点附近停滞。

本课总结

  • 对数是指数的逆运算,用来回答“需要多少次幂才能达到目标”。
  • 每轮按固定比例缩小问题规模时,执行轮数通常是对数级。
  • 对数底数的变化只带来常数因子,因此复杂度中常写作 O(log⁡n)O(\log n)。

下一课预告

下一课学习直接证明与反证法,把上面的计数结论写成有前提、有推导、可复查的证明。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

指数与对数

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通