程序员必学：快速幂算法详解

程序员必学：快速幂算法详解

快速幂算法是计算机科学中的一个重要概念，特别是在算法竞赛和高性能计算中。本文将详细介绍快速幂算法的基本概念、实现方法以及应用场景，帮助读者深入理解这一算法的核心思想和具体实现。

关于快速幂

快速幂算法是参加算法竞赛（如 NOI、ACM 等）的必备基础知识，即使是不参加算法竞赛的程序员，也应当掌握这一算法。快速幂算法在《计算机程序设计艺术》（The Art of Computer Programming，简称 TAOCP）一书中有所提及，该书由计算机科学领域的知名科学家 Donald Ervin Knuth 编写。

Knuth 在 1974 年获得图灵奖，目前 TAOCP 已出版了第 1、2、3、4A 卷，计划中的第 4B、5、6、7 卷尚未出版。第一卷首发于 1968 年，Knuth 现年 82 岁，计划在 105 岁之前完成这部巨著。

微软创始人 Bill Gates 曾评价道：“如果你认为自己是一位非常优秀的程序员，那就应该阅读 Knuth 的 TAOCP；如果你能读懂全部内容，可以直接给我发送一份简历。” Knuth 本人则表示：“看不懂就别当程序员了！”不过 TAOCP 对新手来说阅读难度较大，书中的所有示例都使用了 Knuth 自创的 MIX 汇编语言。

阅读本文之前的提醒

在深入学习快速幂算法之前，需要具备以下基础知识：

• 熟悉算法中的时间复杂度和空间复杂度概念
• 熟悉二进制和十进制的转换
• 熟悉常见的位运算操作，如 n & 1 用于获取最低二进制位的值，n >> 1 用于求正整数 n 的一半

什么是幂（Power）？

幂运算的基本概念是：x 的 n 次幂表示 n 个 x 相乘，例如 2 的 4 次幂就是 2 * 2 * 2 * 2。用简化表示法，x 的 n 次幂记作 x ^ n（本文中的 ^ 不表示按位异或）。

最直观的幂运算实现方法如下（以 Java 语言为例）：

int power(int x, int n) {
    int result = 1;
    while (n-- > 0) {
        result *= x;
    }
    return result;
}

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)。

什么是快速幂？

快速幂算法的目标是提高幂运算的效率，将时间复杂度优化至 O(logn)。这里介绍两种实现方法：递归和非递归。

递归实现

递归实现的快速幂算法代码如下：

int fastPower(int x, int n) {
    if (n == 0) return 1;
    int result = fastPower(x, n >> 1);
    result *= result;
    return (n & 1) == 0 ? result : result * x;
}

这个方法的时间复杂度和空间复杂度都是 O(logn)。分析复杂度的方法包括：

• 代入特定值进行分析，例如当 n 为 16 时，方法的递归调用过程可以直观地展示每次调用时 n 的规模减半的特点。
• 使用主定理（Master Theorem）进行更专业的复杂度分析。

非递归实现

以计算 3 的 21 次幂为例，分析非递归实现的代码：

int fastPower(int x, int n) {
    int result = 1;
    while (n != 0) {
        if ((n & 1) == 1) {
            result *= x;
        }
        x *= x;
        n >>= 1;
    }
    return result;
}

执行流程如下：

1. 初始化 result 为 1。
2. 当 n 不为 0 时，进入循环：

• 检查 n 的最低位是否为 1，如果是，则将当前的 x 乘入 result。
• 将 x 自身平方（相当于计算下一个 2 的幂次）。
• 将 n 右移一位（相当于检查下一个二进制位）。

这种方法的时间复杂度是 O(logn)，空间复杂度是 O(1)。

LeetCode 实战

LeetCode 上的第 50 号题 "Pow(x, n)" 可以直接应用快速幂算法。以下是两种实现方式：

递归实现

public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n == -1) return 1 / x;
    double half = myPow(x, n >> 1);
    half *= half;
    return ((n & 1) == 1) ? half * x : half;
}

非递归实现

public double myPow(double x, int n) {
    long y = (n < 0) ? -((long) n) : n;
    double result = 1.0;
    while (y > 0) {
        if ((y & 1) == 1) {
            result *= x;
        }
        x *= x;
        y >>= 1;
    }
    return (n < 0) ? (1 / result) : result;
}

这两种实现方式都充分利用了快速幂算法的优势，能够高效地处理大数的幂运算问题。