倍增

倍增（Doubling） 是一种通过重复翻倍来高效解决问题的方法，广泛应用于数学、计算机科学、通信等领域。其核心思想是通过预处理和分阶段扩大规模，将复杂操作的时间复杂度从线性降低到对数级。以下是其核心概念、应用场景及实例解析：

一、基本概念

1. 数学定义

   • 数值倍增：每次操作使数值变为原来的两倍，如 $a_n=2^n$（几何级数增长）。

   • 函数倍增：若 $f(n)=O(2^n)$，称其具有指数时间复杂度。

2. 计算机科学中的倍增法

   • 预处理：通过存储不同“步长”的信息（如 $2^k$ 步后的状态），将多次查询的耗时从 $O(n)$ 降至 $O(\log n)$。

   • 分治策略：将大问题分解为多个倍增的子问题，逐步合并结果。

二、典型应用场景

1. 算法优化

• 最近公共祖先（LCA）：

  • 问题：在树结构中快速找到两个节点的最近公共祖先。

  • 倍增法步骤：

    1. 预处理每个节点向上 $2^k$ 层的祖先（$k=0,1,\mathrm{2...}$）。

    2. 查询时通过二进制跳跃调整两节点深度，逐级逼近LCA。

  • 时间复杂度：预处理 $O(n\log n)$，单次查询 $O(\log n)$。

• 范围最值查询（RMQ）：

  • 问题：快速获取数组中区间的最小/最大值。

  • ST表（Sparse Table）：

    • 预处理每个起点 $i$ 的 $2^j$ 长度区间的最值。

    • 查询时选取覆盖区间的最长 $2^k$ 块，合并结果。

2. 快速幂算法

• 问题：高效计算 $a^b\mathrm{m}\mathrm{o}\mathrm{d}p$（大指数运算）。

• 倍增思想：将指数 $b$ 转为二进制，逐位计算 $a^{2^k}$ 并累乘。

  python

  复制

  下载

  deffast_power(a, b, p):
      result =1while b >0:if b %2==1:
              result =(result * a)% p
          a =(a * a)% p
          b = b //2return result

• 时间复杂度：$O(\log b)$，远优于朴素算法的 $O(b)$。

3. 网络传输（TCP拥塞控制）

• 慢启动机制：

  • 初始拥塞窗口（cwnd）为1 MSS（最大报文段）。

  • 每收到一个ACK，cwnd倍增，直至达到阈值或出现丢包。

  • 目的：快速探测可用带宽，避免网络过载。

三、倍增法与其他增长方式对比