如何以低于O(m)的时间复杂度快速计算幂运算？

当然不是只有暴力乘法这一种解法！你提到的“利用已算出的幂来推导更大的幂”的思路，其实就是快速幂算法（也叫平方求幂法）的核心，它能把时间复杂度从O(m)直接降到O(log m)，不管是递归还是迭代都能轻松实现。

核心思路 #

快速幂的本质是通过分治或二进制拆解，不断将问题规模减半：

• 如果m是偶数：n^m = (n^(m/2))^2，比如计算n^{8时，只需要先算出n}4，再平方一次就行，而不是连乘8次
• 如果m是奇数：n^m = n * n^(m-1)，先把奇数幂转成偶数幂的情况，再用上面的规则处理
• 边界情况：任何数的0次幂都是1（n^0 = 1）

递归实现 #

先给你一个递归版本的代码（以Python为例），逻辑和你想的完全一致：

def fast_power_recursive(n, m):
    # 边界条件：0次幂返回1
    if m == 0:
        return 1
    # 先计算一半的幂
    half_power = fast_power_recursive(n, m // 2)
    # 根据m的奇偶性处理
    if m % 2 == 0:
        return half_power * half_power
    else:
        return n * half_power * half_power

举个例子，计算n^5：

1. 先算n^(5//2)=n2
2. 因为5是奇数，所以结果是n * (n^2) * (n^2) = n^5，总共只需要3次乘法，而暴力解法要4次。

迭代实现 #

递归虽然直观，但如果m特别大（比如10^9），可能会遇到栈溢出的问题，这时候迭代版本更稳妥：

def fast_power_iterative(n, m):
    result = 1
    current_base = n
    while m > 0:
        # 如果当前二进制位是1，就把当前基数乘到结果里
        if m % 2 == 1:
            result *= current_base
        # 基数平方，对应二进制位左移一位
        current_base *= current_base
        # 幂次右移一位（相当于除以2）
        m = m // 2
    return result

比如计算n^8（二进制是1000）：

• 初始result=1，current_base=n，m=8
• m是偶数，current_base变成n²，m=4
• m还是偶数，current_base变成n⁴，m=2
• m依旧偶数，current_base变成n⁸，m=1
• m是奇数，result *= n⁸，得到最终结果，总共3次乘法，比暴力的7次少太多。

复杂度对比 #

• 暴力解法：需要m-1次乘法，时间复杂度O(m)
• 快速幂：每次把m减半，最多需要log₂(m)次乘法，时间复杂度O(log m)
  比如当m=1024时，暴力要1023次乘法，而快速幂只需要10次，差距非常明显！

额外补充 #

• 如果需要处理负幂次，只需要计算正幂次的倒数：n^(-m) = 1 / fast_power(n, abs(m))
• 对于整数溢出问题（比如Java/C++这类强类型语言），可以根据需求加入取模操作，避免数值过大。

内容的提问来源于stack exchange，提问作者Cipri