编程之禅
0%

快速幂算法

发表于 更新于 分类于 阅读次数： Disqus：

快速幂算法

看了不少题解，都讲的太复杂，而本人一直崇尚大道至简，于是萌生出写该题解的想法。

快速幂算法可以在 O(lgn) 内完一个数的 n 次幂计算，即实现C语言库函数 double pow(double x, double y)

递归

快速幂算法来源于二分法思想，每次丢掉一半的数据(我自己的理解)，这样在 O(lgn) 得出问题答案。

例如：计算 373

373 = 336* 336*3

336 = 36*36

36 = 33*33

33 = 31*31*3

31 = 3

可以看出非常符合递归的思想，当 n 为基数时，只需多乘一个 x。使用代码描述如下：

1
2
3
4
5
6
7
double quickMul(double x, long long n)
{
    if (n == 0)
        return 1;
    double y = pow(x, n / 2);
    return (n % 2 == 0) ? y * y : y * y * x;
}

时间复杂度：O(lg(n))

空间复杂度：O(lg(n))，即最大递归深度。

迭代

使用迭代就可以将空间复杂度降为 O(1)

每次迭代令 x = x*x，就可以让 n 减半，直至 n 为 0。

累乘所有 n 为奇数的项，就能得到答案。如下例所示：

27

7 3 1
21 22 24

只需把奇数对应的数累乘即可： 21 * 22 *24 = 27

373

73 36 18 9 4 2 1
31 32 34 38 316 332 364

只需把奇数对应的数累乘即可：31 * 38 * 364 = 373

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double myPow(double x, int n)
{
    if (n == 0)
        return 1;
    long N = n;
    double res = 1;
    if (N < 0)
    {
        x = 1 / x;
        N *= -1;
    }
    while (N)
    {
        if (N & 1) // 判断二进制最地位是否为1，或者判断是否为偶数，等价于 N%2
            res *= x;

        x *= x;
        N >>= 1; // 等于 N/=2;
    }
    return res;
}

可提交的代码

题目链接

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
public:
    double quickMul(double x, long long n)
    {
        if (n == 0)
            return 1;
        double y = pow(x, n / 2);
        return (n % 2 == 0) ? y * y : y * y * x;
    }
    double myPow(double x, int n)
    {
        long N = n;
        if (N < 0)
        {
            x = 1.0 / x;
            N *= -1;
        }
        return quickMul(x, 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
class Solution
{
public:
    double myPow(double x, int n)
    {
        if (n == 0)
            return 1;
        long N = n;
        double res = 1;
        if (N < 0)
        {
            x = 1 / x;
            N *= -1;
        }
        while (N)
        {
            if (N & 1) // 判断二进制最地位是否为1，或者判断是否为偶数，等价于 N%2
                res *= x;

            x *= x;
            N >>= 1; // 等于 N/=2;
        }
        return res;
    }
};