快速幂（Fast Power）
📌 定义
快速幂是一种使用分治思想快速计算 a^n 的算法，将朴素算法的O(n)时间复杂度优化到O(log n)。
核心思路
利用幂运算的性质，将指数不断折半：
a^n = {
1, n = 0
a^(n/2) × a^(n/2), n为偶数
a^(n/2) × a^(n/2) × a, n为奇数
}
化简为：
a^n = {
1, n = 0
(a^(n/2))^2, n为偶数
(a^(n/2))^2 × a, n为奇数
}
示例：计算 2
2^10 = (2^5)^2
2^5 = (2^2)^2 × 2
2^2 = (2^1)^2
2^1 = (2^0)^2 × 2
2^0 = 1
只需要5次操作，而不是10次乘法
复杂度分析
| 指标 | 朴素算法 | 快速幂 |
|---|---|---|
| 时间复杂度 | O(n) | O(log n) |
| 空间复杂度 | O(1) | O(log n)递归 或 O(1)迭代 |
Go 代码
Go 实现
package main
import "fmt"
func quickPow(a, n int64) int64 {
if n == 0 {
return 1
}
half := quickPow(a, n/2)
if n%2 == 0 {
return half * half
} else {
return half * half * a
}
}
func quickPowIterative(a, n int64) int64 {
result := int64(1)
base := a
for n > 0 {
if n&1 == 1 {
result *= base
}
base *= base
n >>= 1
}
return result
}
func modPow(a, n, mod int64) int64 {
result := int64(1)
base := a % mod
for n > 0 {
if n&1 == 1 {
result = (result * base) % mod
}
base = (base * base) % mod
n >>= 1
}
return result
}
func main() {
fmt.Printf("2^10 = %d\n", quickPow(2, 10))
fmt.Printf("3^5 = %d\n", quickPow(3, 5))
}思路展开
二进制分解原理
将指数n用二进制表示：
n = b_k×2^k + b_(k-1)×2^(k-1) + ... + b_1×2 + b_0
例如：13 = 1101₂ = 8 + 4 + 1
a^13 = a^8 × a^4 × a^1
迭代过程：
n=13 (1101₂)
初始: result=1, base=a
第1轮: n&1=1, result=a, base=a^2, n=6 (110₂)
第2轮: n&1=0, result=a, base=a^4, n=3 (11₂)
第3轮: n&1=1, result=a^5, base=a^8, n=1 (1₂)
第4轮: n&1=1, result=a^13, base=a^16, n=0
结果: a^13
经典题目
基础应用
模运算
- 大数取模
- 费马小定理应用
- RSA加密
矩阵快速幂
- 斐波那契数 - LeetCode 509（矩阵快速幂优化）
- 线性递推优化
⚖️ 优缺点
优点
- ✅ 高效：O(log n)时间复杂度
- ✅ 简洁：代码实现简单
- ✅ 通用：适用于各种幂运算
缺点
- ❌ 溢出风险：大数运算需要处理溢出
- ❌ 浮点数精度：浮点数运算有精度问题
🎨 应用场景
- 大数取模：(a^n) % m
- 密码学：RSA加密解密
- 组合数学：计算组合数取模
- 矩阵快速幂：求斐波那契数列第n项
- 数论：费马小定理、欧拉定理
💡 快速幂的扩展
💡 位运算技巧
# 判断奇偶
n % 2 == 1 等价于 n & 1
# 除以2
n // 2 等价于 n >> 1
# 乘以2
n * 2 等价于 n << 1