广州C/C++培训
达内广州岗顶中心

18087159764

热门课程

C++的O(logn)的快速幂

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

广州达内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)!

上一篇:线段树模板中的区间修改和区间查询
下一篇:算法的泛化过程

无人零售策略发展情况

达内广州岗顶中心:马化腾4天减股套现17.75亿

2017产品经理的两个必答题

2大C语言扩展类制作步骤

选择城市和中心
贵州省

广西省

海南省