快速幂算法

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以**O(log N)**的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

思考一个问题， 2的10次方，怎么做？

方法一：最朴素的做法，就是 2 * 2 = 4, 4 * 2 = 8, 8 * 2 = 16… 共进行了 9次乘法运算。

**方法二 ** : 快速幂算法

2 的10次方 = 2的5次方 * 2的5次方;

2的5次方 = 2的2次方 * 2的2次方 * 2

使用这种方式， 我们计算 2的10次方进行了 5 次乘法运算

一，快速幂 + 递归

快速幂算法的本质是分治算法。 举个例子, 如果要计算 x ^ 64

x→ x^2 → x^4 → x^8 → x^16 → x^32 → x^64

从x 开始，依次对上一次的结果进行平方运算, 我们只需要进行 6 次运算就可以得到 x ^ 64的值。

而不需要线性的计算63次

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x 但如果我们从右往左看，分治的思想就十分明显了：

  • 当我们计算 x ^ n时，我们先计算 x ^ (n/2)
    • 如果 n 为偶数， 则 x = x ^ (n/2) * x ^ (n/2)
    • 如果 n 为奇数， 则 x = x ^ (n/2) * x ^ (n/2) * x
  • 递归边界条件， n == 0, 任何数(除0以外) 的0次方都是1.

代码如下 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 快速幂
double quickMul(double x, long N) {
    // 任何数(除0外) 的 0次幂都是1
    if (N == 0) return 1.0;
  	// 先计算 x 的 N / 2幂
    double y = quickMul(x, N / 2);
    // 如果 N 为偶数， 则 x 的 N次幂等于 y * y
    // 如果 N 为奇数， 则 x 的 N次幂等于 y * y * x
    return N % 2 == 0 ? y * y : y * y * x;
}

double myPow(double x, int n) {
    long N = n;
    // 如果 n < 0，结果为 1/快速幂
    // 如果 n >= 0, 结果为 快速幂
    return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

复杂度分析 :

时间复杂度 : O(log N) 分治计算，每次计算均折半，复杂度 O(log N)

空间复杂度 : O(log N) 递归使用栈空间, O(log N)

二，快速幂 + 迭代

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

double myPow(double x, int n) {
    long N = n;
    // 如果 n < 0，结果为 1/快速幂
    // 如果 n >= 0, 结果为 快速幂
    return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

double quickMul(double x, long N) {

    double ans = 1.0;
    //初始值为 x
    double current_product = x;
    // 在对 N 进行二进制拆分的同时计算答案
    while (N > 0) {
        if (N % 2 == 1) {
            // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
            ans *= current_product;
        }
        // 将上次结果不断地平方
        current_product *= current_product;
        // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
        N /= 2;
    }
    return ans;
}

复杂度分析 :

时间复杂度 : O(log N) 每次均折半查找

空间复杂度 : O(1) 没有使用额外的内存空间