课程咨询 : 020-87532245 24小时热线:15622781509 咨询QQ:3061057839

广州C++培训 > 达内新闻 > C++的O(logn)的快速幂
  • C++的O(logn)的快速幂

    发布:广州C++培训      来源:达内新闻      时间:2017-02-13

  • 广州达内C++培训的小编这一期讲O(logn)的快速幂。

    快速幂原理解析与其他方法回顾

    一.回顾

    1.1.已知的方法

    关于求a的n次方,有几种做法呐?对于初学者来说有两种。如下所示

    1 void poww1(int a, int b){

    2    long long ans = 1;

    3    for(register int i = 0; i < b; i++)

    4        ans *= a;

    5    return ans;

    6 }

    1#include <cmath>//poww2

    2    ans = (long long) pow(a, b);//调用cmath库的pow函数,但是注意返回值不是longlong/int型,是double型

    观察poww1,一个明显的问题便是它的时间复杂度比较高,是O(n)的复杂度,即n次方需要乘n次才可得到结果,较慢。

    观察poww2,更加明显的问题在于其函数的返回值是个浮点数,这是一个定时炸弹,有可能使用pow(10, 4)时得到9999的答案,让你调试后欲哭无泪。

    1.2.测试对比

    测试程序如下:

    1 #include <iostream>

    2 #include <cstdio>

    3 #include <cmath>

    4 using namespace std;

    5 int main(){  

    6     int n = 0; 

    7     for(int i = 0; i <= 4; i++) 

    8         n += (i+1)*(int)pow(10, 5-i); 

    9     cout << n << endl; 

    10     return 0; 

    11 }

    使用Dev-C++ 5.4.0与Smart c++ 2013分别运行,得到测试数据:

    由于精度问题,结果不同。

    有人会说:"不要强转成int啊,用long long就不会丢失精度啦。"

    那么将循环改成——

    1 for(int i = 0; i <= 4; i++) 

    2    n += kong[i]*(long long)pow(10, 5-i);

    测试结果如下:

    根本就没有变哎!

    1.3.对比两种方法运行的时间与准确性

    利用循环次数更大的测试程序如下:

    1    int i; 

    2    long long n = 0; 

    3    for(i = 0; i <= 10; i++){

    4        n += (i+3)*(long long)pow(5, 11-i); 

    5    }

    6    cout << n << endl; 

    1 long long poww(int a, int b){

    2    long long ans = 1;

    3    for(int i = 0; i < b; i++)

    4        ans *= a;

    5    return ans;

    6 }

    7 int main(){ 

    8    int i; 

    9    long long n = 0; 

    10    for(i = 0; i <= 10; i++){

    11        n += (i+3)*(long long)pow(5, 11-i); 

    12    }

    13    cout << n << endl; 

    14    return 0; 

    15 }

    运行结果如下:

    (上下分别是方法二与方法一)

    1.4.结论

    两者优劣一目了然:方法一相对较快且保证在不超范围内一定正确,不过要多打几行代码;方法二短,但是坑。

    若选择以上两种方法,自己选吧。。。

    那么我们的目标便是继承方法一的优点,改良其缺点:即保持准确性的情况下降低时间复杂度。

    二.快速幂引理

    2.1.先看效果:

    答案一致,时间不到方法一的1/2,并且在当次方数极大的时候,时间会远小于方法一,原因便是因为其时间复杂度为O(logn)(logn通常指log2n)。

    2.2引理的数学形式

    引理:∀取X∈N*皆可被分解为形如X = 2^a+2^b+...+2^k(a != b!= …… != k);

    设2^0+2^1+2^2+…+2^n = m;……(1)式

    2^1+2^2+2^3+…+2^(n+1) = 2*m;……(2)式

    (2)式-(1)式= (1)式= 2^(n+1)-2^0 = 2^(n+1)-1……(*)

    当X != 2^m时

    ∵int X > 0;

    ∴X = 2^m - 1 - k(int k >= 0);

    if(x%2 == 1)k %2 == 0;

    else k%2 == 1;

    ∵2^m - 1 = 2^0 + 2^1 +…+2^(m-1);

    ∴若原式成立,则k可分解为2某些次方的和。

    当k%2 == 1时,必有2^0,减掉,k为偶数;

    那么现在X就缩小为了正偶数。

    观察2 4 8 16……我们会发现一点,即第i个数后面的数都2^i有作为因数,而它前面的数因数中则没有2^i,通过这个便可以确定k的分解。

    利用递归的思想……X缩小为4的倍数,8的倍数……

    2.3例子:

    举个例子: k = 17的分解,按照以下步骤。

    int cnt = 1;

    while (k){

    if(k%(2^cnt) != 0) {

    k得到新的分解: 2^(cnt-1);

    k -= 2^(cnt-1);

    //此时k%2(cnt) == 0

    cnt ++;

    }

    }

    17%2 == 1; =>17 = 2^0 + m;17-1 = 16;

    16%2 == 0; =>16/2 = 8

    ……

    1%2 == 1; =>17 = 2^0 +2^4;

    1/2 == 0终止循环;

    那么这种东东对做幂运算有什么用呢?

    答案便是——将幂按照此方法分解。

    例如:求6^11

    我们已知6^0 = 1 ,a = 6^1 = 6;

    11 = 2^0 + 2^1 + 2^3;

    所以6^11 == 6^1 * 6^2 * 6^8;

    我们还知道a^2 == 36;

    那么我们将上述分解指数的步骤加入乘法以获得最终解:

    curr = 6;ans = 1;

    11 % 2 == 1 => ans *= 6^0;curr = 6^2

    5 %2 == 1 => ans *= 6^2;curr = 6^4;

    2%2 == 0 =>curr = 6^8;

    1%2 == 0 ans *=curr; ans = 6^11;

    一共用了ceil(log(2)11) = 4步

    每次curr自我平方一次,以准备下一次的使用。而当k%2 == 1时,就意味着需要使用curr将指数进行分解。

    2.4.源代码

    那么给出源代码:

    1 void poww(int a, int b){

    2    int cnt = 0;

    3    long long curr = a,ans = 1, last;

    4    while (b){

    5        if(b%2)   ans *= curr;

    6        curr *= curr;

    7        b /= 2;

    8        cnt ++;

    9    }

    10    return ;

    11 }

    步骤与上面一模一样。

    由此,快速幂便完成了。

    了解详情请登陆广州达内C++培训官网(gz.c.tedu.cn)!

    推荐文章

上一篇:线段树模板中的区间修改和区间查询

下一篇:算法的泛化过程

最新开班日期  |  更多

c++--零基础周末班

c++--零基础周末班

开班日期:2月28日

c++--零基础全日制班

c++--零基础全日制班

开班日期:2月28日

c++--免费训练营

c++--免费训练营

开班日期:2月28日

c++--高薪就业班

c++--高薪就业班

开班日期:2月28日

  • 网址:http://gz.c.tedu.cn     地址:广州市天河北五山路 141 号尚德大厦 627
  • 课程培训电话: 020-87532245 24小时热线:15622781509 咨询QQ:3061057839     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56