算法基础 -- 快速幂算法详解

快速幂算法详解

快速幂（Fast Power或Exponentiation by Squaring）是一种能够在 $O(\log n)$ 时间复杂度内高效计算幂次（如 $a^n$ ）的算法。相比于朴素的逐次相乘（需要 $O (n)$ 次乘法），快速幂极大地减少了运算次数，尤其当指数 $n$ 较大时更显优势。以下从原理、实现思路及具体示例三个方面详细讲解。

一、快速幂的基本原理

计算 $a^n$ 时，可以利用以下两个数学性质：

幂的拆分
- $a^n = a \times a^{n-1}$ ，如果 $n$ 是奇数；
- $a^n = (a^{n/2})^2$ ，如果 $n$ 是偶数。
平方快速翻倍

如果已经知道 $a^k$ ，那么：
$a^{2k} = (a^k)^2$

通过上述性质，我们可以每次将指数 $n$ 的规模减半，从而实现对数级别的处理。

当 $n$ 为偶数：
$a^n = (a^{n/2})^2$
当 $n$ 为奇数：
$a^n = a \times a^{n-1}$

通过不断折半，我们最终可以将计算复杂度降低到 $O(\log n)$ 。

二、快速幂的实现思路

实现快速幂的方法包括递归和迭代，常用的是基于“二进制指数拆分”的迭代实现。

1. 递归实现

递归的基本思路是不断将 $n$ 按奇偶拆分，直到基准情况（如 $n = 0$ 或 $n = 1$ ）。伪代码如下：

function fastPower(a, n):if n == 0:return 1if n == 1:return aif n is even:half = fastPower(a, n // 2)return half * halfelse:return a * fastPower(a, n - 1)

2. 迭代实现

迭代实现通过“处理指数的二进制位”来实现。思路如下：

准备结果变量 res = 1，初始幂底 base = a。
当 $n > 0$ 时，依次处理 $n$ 的二进制最低位：
- 如果最低位是 1（即 $n$ 为奇数），则更新结果 res = res * base；
- 无论奇偶，都将 base = base * base；
- 将 $n$ 右移一位（n >>= 1，即 $\div 2$ ）。
循环结束时，res 即为最终结果。

伪代码如下：

function fastPowerIterative(a, n):res = 1base = awhile n > 0:if (n & 1) == 1:res = res * basebase = base * basen >>= 1return res

3. 快速幂取模

在许多实际问题中，需要计算 $a^n \bmod m$ 。此时可在每次乘法后加入取模操作，避免中间结果过大：

function fastPowerMod(a, n, m):res = 1base = a % mwhile n > 0:if (n & 1) == 1:res = (res * base) % mbase = (base * base) % mn >>= 1return res

通过每次取模操作，可以确保数值始终在合理范围内，不会溢出。

三、示例演算

示例 1：递归实现

计算 $3^{13}$ ：

$n = 13$ 是奇数，结果为 $\times 3^{12}$ ；
$3^{12} = (3^6)^2$ ；
$3^6 = (3^3)^2$ ；
$3^3 = 3 \times 3^2$ ；
$3^2 = (3^1)^2$ ；
$3^1 = 3$ 。

最终结果为 $3^{13} = 1594323$ 。

示例 2：迭代实现

计算 $3^{13}$ ，其二进制表示为 $13 = 1101_2$ ：

res = 1, base = 3, n = 13(1101)。
低位是 1：更新 res = 1 * 3 = 3；更新 base = 3^2 = 9，右移 $n = 110$ 。
低位是 0：跳过 res 更新；更新 base = 9^2 = 81，右移 $n = 11$ 。
低位是 1：更新 res = 3 * 81 = 243；更新 base = 81^2 = 6561，右移 $n = 1$ 。
低位是 1：更新 res = 243 * 6561 = 1594323；更新 base = 6561^2 = 43046721，右移 $n = 0$ 。
$n = 0$ ，循环结束，结果为 $1594323$ 。