算法-二分幂算法

前言

二分幂算法（Binary Exponentiation）是一种高效计算大指数幂的算法，也称为「快速幂」或「平方求幂」。它能够将计算 $a^n$ 的时间复杂度从 $O(n)$ 降低到 $O(log n)$，大幅提高了计算效率。

基本原理

二分幂算法基于一个简单的数学性质：任何整数的幂可以通过将指数分解为二进制表示，然后利用乘法的结合律来计算。

例如，计算 $a^{11}$ 时，我们可以将 $11$ 写成二进制 $1011$，即：
$$11 = 2^3 + 2^1 + 2^0 = 8 + 2 + 1$$

因此：$a^{11} = a^8 × a^2 × a^1$

而 $a^1, a^2, a^4, a^8$ 等这些值可以通过反复平方得到：

• $a^1 = a$
• $a^2 = a^1 × a^1 = a × a$
• $a^4 = a^2 × a^2$
• $a^8 = a^4 × a^4$

算法实现

迭代版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 迭代版本
def binary_exponentiation_iterative(a, n):
    """
    计算 a^n 的迭代版本二分幂算法
    
    参数:
        a: 底数
        n: 指数（非负整数）
    
    返回:
        a^n 的结果
    """
    result = 1
    while n > 0:
        # 如果n的二进制表示的当前末位为1
        if n & 1:
            result *= a
        # 将a平方
        a *= a
        # n右移一位，即n = n/2
        n >>= 1
    return result

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 递归版本
def binary_exponentiation_recursive(a, n):
    """
    计算 a^n 的递归版本二分幂算法
    
    参数:
        a: 底数
        n: 指数（非负整数）
    
    返回:
        a^n 的结果
    """
    if n == 0:
        return 1
    
    # 计算a^(n/2)
    half_pow = binary_exponentiation_recursive(a, n // 2)
    
    # 如果n是奇数
    if n % 2 == 1:
        return half_pow * half_pow * a
    # 如果n是偶数
    else:
        return half_pow * half_pow

应用场景

1. 大数幂模运算：在密码学、数论问题中经常需要计算 (a^n) % m，二分幂算法结合模运算可以高效完成。

2. 矩阵快速幂：计算矩阵的高次幂，常用于解决线性递推关系。

3. 斐波那契数列：通过矩阵快速幂求解第n项斐波那契数。

4. 组合数学：某些组合计算涉及大量幂运算。

算法复杂度

• 时间复杂度：$O(log n)$，因为每次迭代都将指数减半。
• 空间复杂度：迭代版本为 $O(1)$，递归版本为 $O(log n)$。

示例分析

以计算 $3^{13}$ 为例：

1. $13$ 的二进制表示为 $1101$
2. 初始 $result = 1，a = 3$
3. 遍历二进制位:
   • 第 $1$ 位是 $1$：$result = 1 × 3 = 3$，然后 $a = 3 × 3 = 9$
   • 第 $2$ 位是 $0$：$result$ 不变，$a = 9 × 9 = 81$
   • 第 $3$ 位是 $1$：$result = 3 × 81 = 243$，然后 $a = 81 × 81 = 6561$
   • 第 $4$ 位是 $1$：$result = 243 × 6561 = 1,594,323$

通过二分幂算法，我们只需要进行 $4$ 次乘法运算，而不是 $13$ 次，大大提高了计算效率。

后记

二分幂算法是计算机科学中的基础算法之一，它在各种数学计算、密码学和图论问题中都有广泛应用。掌握这一算法不仅能够提高计算效率，也能帮助解决许多其他相关问题。