快速幂算法

什么是快速幂算法

在进行指数运算时，例如2^{100}，常规方法是将其拆分为2 \times 2 \times \dots \times 2（共 100 个2 相乘），这种方法的时间复杂度是O(n)。当指数特别大时，这种方式会导致运算速度极低。

快速幂算法利用分治思想，可以将时间复杂度降至O(\log n)，极大提升运算效率。

快速幂算法的核心思想

分治策略简介

分治策略（Divide and Conquer）是一种算法设计思想，通过将一个复杂问题分解为多个规模较小的子问题递归求解，最后合并子问题的结果得到原问题的解。

分治策略的三个步骤：

1. 分解（Divide）：将问题划分为若干规模较小且结构与原问题相似的子问题。

2. 解决（Conquer）：递归地解决各个子问题。如果子问题足够简单（如规模为 1），直接求解。

3. 合并（Combine）：将子问题的解合并，得到原问题的解。

快速幂算法正是分治策略的典型应用，通过将指数逐步缩小（通常是减半），减少了重复运算。

快速幂的实现思路

假设我们要计算5^{10}，普通方法需要 10 步计算，但快速幂算法的分治思想可以将其优化：

-5^{10} = (5^2)^5

-5^{10} = 5 \times (5^2)^4

-5^{10} = 5 \times ((5^2)^2)^2

由此可见，原本需要 10 步的计算，通过分治只需 3 步即可完成。

快速幂的核心思路是：

1. 指数为奇数：将底数单独提出一次，使指数化为偶数。

2. 指数为偶数：将底数平方，同时指数减半。

3. 不断迭代：重复以上步骤，直到指数为 0。

快速幂算法的代码实现

以下是基于 Java 的快速幂算法实现，加入了模运算以应对结果可能过大的情况：

static int mod = 1000000007;
long pow(long a, int n) {
    long res = 1;
    while (n > 0) {
        // 如果指数是奇数
        if (n % 2 == 1) {
            res = res * a % mod;
        }
        // 底数平方，指数减半
        a = a * a % mod;
        n /= 2;
    }
    return res;
}

示例分析

以a=3, n=13 为例：

1. 初始值：res=1, a=3, n=13。

2. 第一次循环：n 为奇数，res=res \times a \mod mod = 1 \times 3 = 3，更新a=a \times a = 9, n=6。

3. 第二次循环：n 为偶数，跳过更新res，直接更新a=a \times a = 81, n=3。

4. 第三次循环：n 为奇数，res=res \times a \mod mod = 3 \times 81 = 243，更新a=a \times a = 6561, n=1。

5. 第四次循环：n 为奇数，res=res \times a \mod mod = 243 \times 6561 = 1594323，更新a=a \times a = 43046721, n=0。

6. 结束循环，返回结果1594323。

总结

快速幂算法通过分治思想将复杂问题化简，尤其在处理大数计算时具有显著优势。其核心在于指数每次减半，大大降低了运算次数。

希望这篇分享能对你有所帮助！如果你有任何问题或建议，欢迎在评论区留言交流！