快速幂是什么？如何在 O(log n) 时间内计算 x 的 n 次方？

简化版

快速幂利用 x^n = (x^(n/2))^2（n 为偶）或 x·(x^((n−1)/2))^2（n 为奇），每算一次就把指数折半，所以只需 O(log n) 次乘法，而朴素地连乘要 O(n) 次。实现有两种：递归（分治） 和 迭代（把指数看成二进制）。要注意 n 为负数、以及对 INT_MIN 取负会溢出的坑。

详细版

核心恒等式（把指数对半拆）：

x^n = (x^(n/2))^2            n 是偶数
x^n = x · (x^((n-1)/2))^2    n 是奇数

递归（分治）版：

double myPow(double x, long n) {
    if (n < 0) { x = 1 / x; n = -n; } // 负指数：底数取倒数，指数取正
    return fastPow(x, n);
}
double fastPow(double x, long n) {
    if (n == 0) return 1.0;           // 递归基
    double half = fastPow(x, n / 2);  // 只算一半，结果复用
    return (n % 2 == 0) ? half * half : half * half * x;
}

迭代（二进制）版——把指数 n 按二进制展开，哪一位是 1，就把对应的 x^(2^k) 乘进结果：

double myPow(double x, long n) {
    if (n < 0) { x = 1 / x; n = -n; }
    double res = 1.0;
    while (n > 0) {
        if ((n & 1) == 1) res *= x;  // 当前最低位是 1，累乘
        x *= x;                       // x → x² → x⁴ → x⁸ ...
        n >>= 1;                      // 指数右移一位
    }
    return res;
}

为什么 O(log n)：每一步指数减半（或二进制右移一位），log₂n 步就到 0。
关键写法：half*half 只算一次子问题、复用结果——如果写成 fastPow(x,n/2)*fastPow(x,n/2) 会重复递归退化成 O(n)。

完整版教学

一、朴素法为什么慢：O(n) 次乘法

要算 x^n，最直白的写法是循环乘 n 次：res = x*x*...*x。这要做 n−1 次乘法，是 O(n)。当 n 很大（比如求 a^b mod p，b 是上亿的大数），O(n) 就太慢了。快速幂能把它压到 O(log n)。

二、分治思路：指数折半，平方加速

关键观察：x^n 不必一个一个乘，可以「翻倍」着算。 比如要算 x^8：

x → x² → x⁴ → x⁸   （每步把上一步的结果平方）

只用了 3 次乘法，而不是 7 次。因为 x^8 = (x^4)^2 = ((x^2)^2)^2，每平方一次，指数就翻倍。反过来看就是分治：求 x^n，先递归求出 x^(n/2)，再平方。

指数是奇数怎么办？比如 x^9 = x · x^8 = x · (x^4)^2，多乘一个 x 补上折半时丢掉的那一次。归纳成：

n 偶：x^n = (x^(n/2))²
n 奇：x^n = x · (x^((n-1)/2))²

三、递归实现与复杂度

递归版直接翻译上面的恒等式：先递归求 half = x^(n/2)，再根据奇偶决定返回 half*half 还是 half*half*x。

一定要先把子问题算出来存进变量 half，再平方。 有人写成 fastPow(x, n/2) * fastPow(x, n/2)——这会把同一个子问题算两遍，递归树重新变满，退化回 O(n)，快速幂就白做了。

复杂度：递归式 T(n)=T(n/2)+O(1)，由主定理（情况二）得 O(log n)；递归深度 log n，空间 O(log n)（栈）。

四、迭代实现：把指数看成二进制

迭代版更省空间（O(1)），思路是把指数拆成二进制。任何数都能写成 2 的幂之和，例如：

13 = 1101₂ = 8 + 4 + 1
x^13 = x^8 · x^4 · x^1

于是从低位到高位扫描 n 的每一个二进制位：

维护一个 x 的「翻倍链」：x, x², x⁴, x⁸, ...（每轮 x *= x）；
若当前最低位是 1（n & 1），就把当前的 x 累乘进结果；
然后 n >>= 1 处理下一位。

扫完 log₂n 个二进制位就结束，时间 O(log n)、空间 O(1)。递归版好理解，迭代版更实用，两者本质相同。

五、坑：负指数与 INT_MIN 溢出

两个高频出错点：

负指数：x^(-n) = 1 / x^n。做法是把底数取倒数、指数取绝对值再算：x = 1/x; n = -n;。
INT_MIN 取负溢出：当 n = -2147483648（Integer.MIN_VALUE）时，-n 会溢出（正数放不下）。解决办法是把 n 提升成 long 再取负（上面代码的形参用 long），或先处理成 long m = n; m = -m;。这是 LeetCode「Pow(x, n)」最常见的 WA 点。

易错提醒：别忘了 x^0 = 1（含 0^0 约定为 1）是递归基；x=0、n<0 是数学上未定义（除零），题目一般不测这个边界。

六、扩展：快速幂取模与矩阵快速幂

快速幂的思想能迁移到两个高频场景：

快速幂取模 x^n mod p：每步乘完立刻取模，防止溢出——res = res * x % p; x = x * x % p;。这是密码学（RSA）、组合数取模、哈希的基础。
矩阵快速幂：把「乘 x」换成「乘一个矩阵」，就能用 O(log n) 求线性递推的第 n 项。经典应用是求斐波那契第 n 项：构造矩阵 [[1,1],[1,0]] 的 n 次幂，即可 O(log n) 得到 F(n)，远快于 O(n) 递推。

只要一个运算满足结合律，就能套快速幂把「重复 n 次」降到 O(log n)。

七、递归式、合并证明与数字推演

这道题的分治闭环是：指数每次折半；偶数平方半次幂，奇数再乘一个底数，迭代版由指数二进制位决定是否乘入答案。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=T(floor(n/2))+Θ(1)=Θ(log n)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：3^13 中 13 的二进制为 1101，只在位为 1 时乘入 3、9、81 对应幂，13 次连乘降为约 4 轮。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

八、实现代价、退化条件与替代方案

实现边界是：负指数先转 long 再取反，避免 -Integer.MIN_VALUE 溢出；模乘还要防乘法溢出。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

九、常见误区与追问

误区：快速幂只是少写几行循环。 它把乘法次数从 n 降到 log n。
误区：奇数指数可以只算两次同一递归。 若重复调用 half 会重新计算，必须保存结果。
误区：先对 int 的 MIN_VALUE 取负。 该值没有正数 int 对应，会溢出。
追问：为什么二进制迭代正确？ n 的每个 1 位表示答案需要乘对应的 x^(2^i)。
追问：0 的负次幂如何处理？ 数学上无定义，接口需明确异常或特殊值。
追问：模快速幂怎样改？ 每次乘法和平方后取模，并选足够宽的中间类型。

十、加强记忆

快速幂 = 指数折半 + 平方加速：x^n=(x^(n/2))²（偶）或 x·(x^((n-1)/2))²（奇），把 O(n) 连乘降到 O(log n)。递归版要用变量存住 half 再平方（别递归两次，否则退化 O(n)）；迭代版把指数看成二进制，逐位判断、x 不断自乘。坑：负指数取倒数、INT_MIN 取负要用 long 防溢出。思想可扩展到快速幂取模、矩阵快速幂求斐波那契。

简化版

详细版