快速幂(蓝桥杯)

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. 非递归（迭代）实现

非递归方法通过循环处理指数的二进制位，逐步累乘结果。具体步骤如下：

1. 初始化结果变量 res = 1 和底数 base = a。

2. 当指数 b>0 时：

   • 如果 b 的最低位是 1，则将当前的 base 乘入结果。

   • 更新 base 为 base2。

   • 将 b 右移一位（相当于除以 2）。

3. 返回最终结果。

伪代码：

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)。

总结

• 递归实现：逻辑简单，但递归调用有额外开销。

• 非递归实现：效率更高，适合实际应用。

• 模运算优化：适用于大数运算，防止溢出。