1. 递归实现
递归方法通过将问题分解为更小的子问题来实现。具体步骤如下：
-
如果指数 b 为 0，返回 1。
-
如果 b 是偶数，则递归计算 (a^2)b/2。
-
如果 b 是奇数，则递归计算 a⋅(a^2)(b−1)/2。
伪代码：
function fastPower(a, b):if b == 0:return 1if b % 2 == 0:half = fastPower(a, b // 2)return half * halfelse:return a * fastPower(a, b - 1)递归方法的时间和空间复杂度均为 O(logn)。
相关的例子
题目要求计算 3^10，递归方法会逐步分解为 3^5、3^2、3^1，最终结果为 59049。
public class FastPowerRecursive {public static long fastPower(long a, long b) {if (b == 0) return 1;if (b % 2 == 0) {long half = fastPower(a, b / 2);return half * half;} else {return a * fastPower(a, b - 1);}}public static void main(String[] args) {System.out.println(fastPower(3, 10)); // 输出 59049}
}代价分析：
-
时间复杂度：O(logn)，因为每次递归将指数减半。
-
空间复杂度：O(logn)，因为递归调用需要栈空间。
2. 非递归（迭代）实现
非递归方法通过循环处理指数的二进制位，逐步累乘结果。具体步骤如下：
-
初始化结果变量
res = 1和底数base = a。 -
当指数 b>0 时：
-
如果 b 的最低位是 1，则将当前的
base乘入结果。 -
更新
base为 base2。 -
将 b 右移一位（相当于除以 2）。
-
-
返回最终结果。
伪代码：
function fastPowerIterative(a, b):res = 1base = awhile b > 0:if (b & 1) == 1:res = res * basebase = base * baseb >>= 1return res迭代方法的时间复杂度为 O(logn)，空间复杂度为 O(1)。
相关的例子
题目要求计算 3^10，迭代方法会通过二进制分解逐步计算结果，最终得到 59049
public class FastPowerIterative {public static long fastPower(long a, long b) {long res = 1;long base = a;while (b > 0) {if ((b & 1) == 1) {res *= base;}base *= base;b >>= 1;}return res;}public static void main(String[] args) {System.out.println(fastPower(3, 10)); // 输出 59049}
}代价分析：
-
时间复杂度：O(logn)。
-
空间复杂度：O(1)。
3. 模运算优化
在实际应用中，尤其是处理大数时，通常需要结合模运算来防止溢出。以下是模运算的快速幂实现：
function fastPowerMod(a, b, mod):res = 1base = a % modwhile b > 0:if (b & 1) == 1:res = (res * base) % modbase = (base * base) % modb >>= 1return res这种方法在每次乘法后取模，确保中间结果不会过大。
相关例子：
假设题目要求计算 3^10mod100000，模运算优化方法会逐步计算并取模，最终结果为 59049
public class FastPowerMod {public static long fastPowerMod(long a, long b, long mod) {long res = 1;long base = a % mod;while (b > 0) {if ((b & 1) == 1) {res = (res * base) % mod;}base = (base * base) % mod;b >>= 1;}return res;}public static void main(String[] args) {System.out.println(fastPowerMod(3, 10, 100000)); // 输出 59049}
}代价分析：
-
时间复杂度：O(logn)。
-
空间复杂度：O(1)。
总结
-
递归实现：逻辑简单，但递归调用有额外开销。
-
非递归实现：效率更高，适合实际应用。
-
模运算优化：适用于大数运算，防止溢出。