快速幂(蓝桥杯)

1. 递归实现

递归方法通过将问题分解为更小的子问题来实现。具体步骤如下：

• 如果指数 b 为 0，返回 1。

• 如果 b 是偶数，则递归计算 (a^2)b/2。

• 如果 b 是奇数，则递归计算 a⋅(a^2)(b−1)/2。

伪代码：

function fastPower(a, b):
    if b == 0:
        return 1
    if b % 2 == 0:
        half = fastPower(a, b // 2)
        return half * half
    else:
        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 = 1
    base = a
    while b > 0:
        if (b & 1) == 1:
            res = res * base
        base = base * base
        b >>= 1
    return 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 = 1
    base = a % mod
    while b > 0:
        if (b & 1) == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        b >>= 1
    return 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)。

总结

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

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

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

原文地址：https://blog.csdn.net/juzihuaile/article/details/147208036

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！