二分法求幂（快速幂）

周子力大约 11 分钟教学文档算法设计与分析递归分治法快速幂Python

二分法求幂（快速幂）

题目描述

给定整数底数 $a$ 和非负整数指数 $n$ ，求 $a^n$ 。要求利用指数减半的思想设计求解算法，减少乘法次数，并输出计算结果。

本题中， $a$ 可以是正整数、负整数或0； $n$ 必须是整数且满足 $n\geq 0$ 。暂不处理负指数或小数指数。程序约定任何底数的0次方都返回1，包括输入 $(a,n)=(0,0)$ ；这一约定与 Python 整数幂运算一致。

示例： 输入 $a=2,n=13$ ，输出8192；输入 $a=-2,n=5$ ，输出 $-32$ ；输入 $a=7,n=0$ ，输出1。

这里的“二分”指将指数规模约减半。这种方法通常称为快速幂或二进制幂。实现时不直接调用 a ** n 或 pow(a, n) 得到答案，而是自己完成分解与合并。

题目分析

从连续相乘到指数减半

当 $n\geq 1$ 时，直接把 $n$ 个 $a$ 连续相乘，需要 $n-1$ 次乘法。也可以写成 $a^n=a\cdot a^{n-1}$ ，但每次指数只减少1，求解层数仍与 $n$ 成正比。

利用幂的运算性质，可以一次将指数缩小到约一半。设 $k=\lfloor n/2\rfloor$ ，分两种情况讨论：

偶数指数： 若 $n=2k$ ，则 $a^n=a^k\cdot a^k$ 。
奇数指数： 若 $n=2k+1$ ，则 $a^n=a^k\cdot a^k\cdot a$ ，平方后还要补乘一个 $a$ 。

因此，只需要先求出一次 $a^k$ ，把结果保存在局部变量 half 中，再计算 half * half。两处 $a^k$ 是同一个子问题，不需要分别递归求解。

定义函数、边界与递推关系

定义 fast_power(a, n)：返回底数 a 的 n 次方。数学上的递推关系为：

F(a,n)= \begin{cases} 1, & n=0,\\ a, & n=1,\\ F(a,n/2)^2, & n\geq 2\text{ 且 }n\text{ 为偶数},\\ F(a,\lfloor n/2\rfloor)^2\cdot a, & n\geq 3\text{ 且 }n\text{ 为奇数}. \end{cases}

代码使用 n // 2 进行整数除法，使用 n % 2 判断奇偶。对于 $n\geq 2$ ，总有 $\lfloor n/2\rfloor<n$ ，因此递归一定会到达0或1的终止条件。正指数的调用链会在1处停止；0次方由单独的边界分支直接处理。

以 $2^{13}$ 为例：

2^{13}=(2^6)^2\cdot 2,\qquad 2^6=(2^3)^2,\qquad 2^3=(2^1)^2\cdot 2.

调用规模由13变成6，再变成3，最后变成1。每层只进行一次子调用，返回后再进行一到两次乘法。

为什么结果正确

当 $n=0$ 或 $n=1$ 时，直接返回约定的正确结果。对于更大的指数，假设子调用已经正确求出 $a^k$ ：若 $n=2k$ ，平方后得到 $a^{2k}$ ；若 $n=2k+1$ ，平方后再乘 $a$ ，得到 $a^{2k+1}$ 。两种分支都恰好得到当前问题的答案。

这体现了分治中的“分解、求解、合并”：把指数减半，递归求解半次幂，再通过平方和必要的补乘合并结果。

实现代码

Python 递归实现

以下代码可以完整复制到 Python 文件中运行。整数底数保证结果可以使用 Python 整数精确表示。

def fast_power(a, n):
    """用指数减半的递归方法，返回整数 a 的非负整数次幂。"""
    if type(a) is not int or type(n) is not int:
        raise TypeError("a 和 n 必须是整数")
    if n < 0:
        raise ValueError("n 必须是非负整数")

    if n == 0:
        return 1
    if n == 1:
        return a

    half = fast_power(a, n // 2)  # 相同的半次幂只求一次
    squared = half * half

    if n % 2 == 0:
        return squared
    return squared * a          # 奇数指数补乘一个底数


for a, n in [(2, 13), (3, 5), (-2, 5), (7, 0), (0, 4), (0, 0)]:
    print(f"{a} 的 {n} 次方：{fast_power(a, n)}")

输出：

2 的 13 次方：8192
3 的 5 次方：243
-2 的 5 次方：-32
7 的 0 次方：1
0 的 4 次方：0
0 的 0 次方：1

half 是每层调用自己的局部变量。当前层会先等待子调用返回，再计算平方；奇数分支补乘的底数始终是 a，不是指数 n。

Python 循环实现

循环版本从指数的二进制低位向高位处理，用 result 累积已经选中的幂，用 base 保存当前对应的底数幂。

def fast_power_iterative(a, n):
    """用循环完成快速幂，不保存递归调用栈。"""
    if type(a) is not int or type(n) is not int:
        raise TypeError("a 和 n 必须是整数")
    if n < 0:
        raise ValueError("n 必须是非负整数")

    result = 1
    base = a
    exponent = n

    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        exponent //= 2
        if exponent > 0:
            base *= base       # 还有下一轮时，才准备下一轮的底数幂

    return result


print(fast_power_iterative(2, 13))  # 8192
print(fast_power_iterative(-2, 5))  # -32
print(fast_power_iterative(7, 0))   # 1

每轮开始时，都保持关系 result * base ** exponent == a ** n，右侧的 a 和 n 指原始输入。若剩余指数是奇数，先把一个 base 纳入 result；随后将指数减半，并在需要下一轮时把 base 平方。指数变成0后，result 就是答案。上面的等式用于解释正确性，代码不会实际用它计算幂。

算法执行过程

交互动画

动画默认使用 $a=2,n=13$ ，与下面的过程表一致。上方调用链按 13 → 6 → 3 → 1 展示指数减半；点击“下一步”后，按返回顺序 1 → 3 → 6 → 13 逐层计算，最终得到8192。黄色节点标记当前计算的调用，蓝色节点表示已返回的调用。

两个蓝色盒子表示同一个 half 值被复用，合并的运算是平方；奇数指数还需补乘一个底数 a。这不表示进行了两次子调用，也不是把结果翻倍。乘法次数按正文的递归代码统计，本例为5次，连续相乘为12次；“调用返回步骤数”与“乘法次数”分别计数。

支持上一步、下一步、自动播放、暂停、重置和全屏演示。修改参数后点击“应用”，可演示 $-9\leq a\leq 9$ 、 $0\leq n\leq 20$ 的整数输入；0次方返回1，1次方直接返回底数。动画使用精确整数计算，盒子内过长的数值会省略显示，完整结果保留在计算步骤和最终结果面板中。

递归调用：指数逐层减半

使用与代码相同的示例 $a=2,n=13$ ，调用过程为：

fast_power(2, 13)  等待 fast_power(2, 6)
  fast_power(2, 6)  等待 fast_power(2, 3)
    fast_power(2, 3)  等待 fast_power(2, 1)
      fast_power(2, 1)  直接返回2

每层只有一个子调用，调用结构是一条链。虽然合并时要使用两次 half，但没有再调用一次函数。

递归返回：平方并按奇偶补乘

当前指数 $n$	子调用返回的 `half`	当前层计算	当前层返回值	当前层乘法次数
1	—	终止条件，直接返回底数2	2	0
3	2	`2 * 2 * 2`，奇数补乘2	8	2
6	8	`8 * 8`，偶数只平方	64	1
13	64	`64 * 64 * 2`，奇数补乘2	8192	2

这个实现求 $2^{13}$ 只进行了5次乘法；直接将13个2连续相乘需要12次乘法。它没有依次算出所有的 $2^1,2^2,\ldots,2^{13}$ ，只求解了合并答案所需的指数。

循环执行：逐位累积幂

指数13的二进制表示为 $1101_2$ ，即 $13=8+4+1$ ，所以最终会把 $2^8$ 、 $2^4$ 和 $2^1$ 相乘。

轮次	本轮开始的 `exponent`	本轮开始的 `base`	本轮开始的 `result`	是否累乘	本轮结束的 `result`	下一轮指数
1	13	2	1	奇数，`1 * 2`	2	6
2	6	4	2	偶数，保持不变	2	3
3	3	16	2	奇数，`2 * 16`	32	1
4	1	256	32	奇数，`32 * 256`	8192	0

四轮开始时的 base 分别是 $2^1,2^2,2^4,2^8$ 。本例循环版本有3次底数平方和3次结果累乘，共6次乘法；与递归版本的具体次数不同，但都随指数的二进制位数增长。

复杂度分析

先采用课程常用的单位成本模型：把一次整数乘法、整数除法和奇偶判断视为常数时间，空间按变量及调用栈帧数量计数。

时间复杂度

递归实现每层只有一次规模约减半的子调用，并进行常数次额外操作。因此，对于 $n\geq 2$ ：

T(n)=T(\lfloor n/2\rfloor)+O(1),\qquad T(0)=T(1)=O(1).

当 $n\geq 1$ 时，共有 $\lfloor\log_2 n\rfloor+1$ 层调用，时间复杂度为 $O(\log n)$ ，其中 $n=1$ 单独看是常数时间； $n=0$ 也直接返回。若统一覆盖所有非负指数，可以写为 $O(\log(n+2))$ 。

循环实现每轮同样将剩余指数减半，时间复杂度也为 $O(\log(n+2))$ 。连续相乘的朴素方法则需要线性数量的乘法，对于正指数为 $O(n)$ 。

只计算一次半次幂是关键。 如果写成 fast_power(a, n // 2) * fast_power(a, n // 2)，就会重复求解相同子问题。此时递推式变成 $T(n)=2T(\lfloor n/2\rfloor)+O(1)$ ，时间复杂度退化到 $O(n)$ 。

辅助空间复杂度

递归版本需要保存各层调用的参数、局部变量与返回位置，辅助空间为 $O(\log(n+2))$ 。循环版本只维护固定数量的变量，辅助空间为 $O(1)$ 。

与猴子吃桃相比，猴子吃桃每层把剩余天数减少1，而快速幂每层把指数约减半，因此两者的递归深度分别是线性级和对数级。

Python 大整数的影响

上述复杂度按算术操作次数和变量数量计算。Python 整数能增长为大整数；当 $|a|\geq 2$ 时，结果 $a^n$ 的二进制位数随 $n\log_2|a|$ 增长，整数乘法不能一直按常数时间计费。循环版本的 $O(1)$ 指变量数量固定，不表示只需要常数个二进制位。快速幂减少了乘法次数，精确结果所需的存储与输出成本仍然存在。

易错点

易错点	正确理解
没有处理 `n == 0`	按本题约定返回1；循环版本也应从 `result = 1` 开始
用 `n / 2` 递归	应使用 `n // 2`，保证子问题指数仍为整数
奇数指数只计算 `half * half`	还要补乘一个底数 `a`，例如 $2^3=2^1\cdot 2^1\cdot 2$
把半次幂递归计算两次	用局部变量保存一次子调用的结果，再进行平方
写成 `a ^ n`	Python 的 `^` 是按位异或；本题用乘法实现幂运算
把 `half * half` 写成 `half * 2`	前者是平方，后者是数量翻倍，含义不同
没有拒绝负指数	本篇算法的输入范围是非负整数指数，代码会抛出 `ValueError`
认为循环版本只在指数为偶数时才更新底数	每次进入下一轮都对应指数减半，底数应平方；奇数时还需先累乘

课堂练习

用递归版本手算 $3^5$ ，写出调用指数、返回值以及总乘法次数。
输入 $(a,n)=(5,0),(0,6),(-2,6),(-2,5)$ ，分别返回什么？
求 $a^{16}$ 时，调用链有哪些指数？这个递归实现要进行几次乘法？
求 $2^{10}$ 时，循环版本会选择哪些底数幂纳入 result？
为什么将两个 fast_power(a, n // 2) 直接相乘，会失去对数级的时间复杂度？

参考答案

调用指数为 5 → 2 → 1；返回值依次为3、9、243。指数2这一层进行1次乘法，指数5这一层进行2次乘法，共3次。
分别为1、0、64、 $-32$ 。偶数次幂消去负号，奇数次幂保留负号。
调用链为 16 → 8 → 4 → 2 → 1。四个非终止层都只进行一次平方，共4次乘法。
$10=1010_2=8+2$ ，会选择 $2^2=4$ 和 $2^8=256$ ，两者相乘得到1024。
两次子调用的参数完全相同，却分别执行，产生重复计算。调用数量由一条链变成二叉展开，递推式为 $T(n)=2T(\lfloor n/2\rfloor)+O(1)$ ，时间复杂度变为 $O(n)$ 。

相关学习：猴子吃桃、汉诺塔、递归与分治。