快速幂
快速幂（Fast Exponentiation）
使用传统算法计算的时间复杂度为，然而利用快速幂的算法时间复杂度为。
例如计算，将指数缩小到1只需要4步即可：
快速幂
C
#include <stdio.h>
long long fast_exponentiation(long long x, long long n) {
if (n == 0) {
return 1;
}
long long half;
if (n % 2 == 0) {
half = fast_exponentiation(x, n / 2);
return half * half;
} else {
half = fast_exponentiation(x, (n - 1) / 2);
return half * half * x;
}
}
int main() {
printf("%lld\n", fast_exponentiation(2, 18));
return 0;
}互动实验
快速幂：调用一次，复用两次
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
知识测验
题目
为什么示例先保存half，再返回half * half？
知识测验
题目
计算x¹³时，half=x⁶，应该如何组合？
知识测验
题目
示例的指数n降到0时返回什么？
动手练习
跟踪3的13次幂
按示例中的快速幂算法计算3¹³，指数为非负整数，n=0时返回1。
- 写出递归调用的指数序列。
- 按返回顺序记录n、half、所用的奇偶分支和返回值。
- 解释为什么同一层的half只需要计算一次。