首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >客户端基本不用的算法系列:快速幂

客户端基本不用的算法系列:快速幂

作者头像
用户2932962
发布2019-08-28 15:59:07
5140
发布2019-08-28 15:59:07
举报
文章被收录于专栏:程序员维他命程序员维他命

幂运算是我们平时写代码的时候最常用的运算之一。根据幂运算的定义我们可以知道,如果我们要求 xN 次幂,那么想当然的就会写出一个 N 次的循环,然后累乘得到结果。所以我们要求幂运算的复杂度仍旧是 O(N)?

那么有没有一种更快的方法呢?

这里给出一种在计算机领域常用的快速幂算法,将 O(N) 降为 O(logN)

我通过例子来讲解这个优化过程:

假设我们要算 xn 次幂,使用累乘来编写代码:

res = 1
for i in range(n):
    res *= x

好的,我们已经完成了 O(N) 的解法。

二进制拆分

为了优化这个算法,我们接下来进行数学推导:

我们继续思考当 N = 10 这个具体场景,我们可以把 10 写成二进制来表示 1010(BIN),然后我们模拟一次二进制转十进制的过程(复习一下大学知识)

我用下划线把二进制的 1010 标识出来,这样大家就可以发现二进制和十进制转换时的代数式规律。

继续回想刚才的场景,那么我们求 x10 次幂,则式子我们可以写成这样:

我们按照二进制低位到高位从左往右交换一下位置:

我们关注相邻的两项,如果我们不考虑幂指数的 *0*1 ,我们只看前半部分,会发现有这么一个规律:

也就是说,不考虑幂指数的 *0*1 右式,左式每次只要每次乘以自身,就是下一项的左式。在我们的例子中其实就是:

用编程思维来考虑这个问题,只要我们从 x 开始维护这么一个左式,每一次迭代都执行 x *= x,然后每次遇到右边是 *1 的情况,就记录一下 res *= x 是不是就能模拟咱们二进制拆分的计算思路了呢?

编程实现一下 x 的 10 次方

我们用上面的思路,通过代码来计算一下 2 的 10 次方,答案应该是 1024

#include <iostream>
using namespace std;

int main() {
    int n = 10; // 幂指数,下面通过二进制拆分成 1010
    int x = 2; // 底数
    int res = 1; // 累乘的答案
    while (n) {
                // 去除二进制的最低位,也就是上面推导中的右式,如果 n & 1 == 1,说明是 *1
        if (n & 1) {
                        // 如果是 *1,则根据我们观察出来的规律,对维护的结果做累乘
            res *= x;
        }
                // 转换到下一位
        x *= x;
                // 二进制右移一位,目的是取到下一个低位二进制
        n >>= 1;
    }
    cout << res << endl; // 1024
    return 0;
}

是不是发现非常的简单!我们至此已经实现了快速幂算法。我们将 n, x 做成参数,编写一个快速幂的方法:

#include <iostream>
using namespace std;

int qpow(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}

int main() {
    cout << qpow(2, 10) << endl; // 1024
    cout << qpow(4, 2) << endl;  // 16
    cout << qpow(5, 3) << endl;  // 125
    cout << qpow(10, 6) << endl; // 1000000
    return 0;
}

复杂度

通过上面对幂指数的拆分,发现快速幂只需要循环拆分的项数就可以完成整个幂运算。

我们不妨设求 x 的 N 次方,并且令 x 的所有二进制位都为 1,就可以得到下面这个等式:

那么其实,k 就是计算机需要计算的次数,也就是时间复杂度。套入公比是 1 的等比数列前 k 项和来反推 k 的大小:

好了,这就是快速幂的全部内容了。你可以使用这道题的知识来求解 LeetCode 372. Super Pow(点击原文直达) 。下一篇文我们来手把手 AC 这题

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-08-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员维他命 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 二进制拆分
  • 编程实现一下 x 的 10 次方
  • 复杂度
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档