ACM | 算法 | 快速幂
2019-12-04 16:00:48来源:博客园 阅读 ()
ACM | 算法 | 快速幂
快速幂
? 幂运算:\(x ^ n\)
? 根据其一般定义我们可以简单实现其非负整数情况下的函数
定义法:
int Pow (int x, int n) {
int result = 1;
while(n--) {
result *= x;
}
return result;
}
? 不难看出此时算法的时间复杂度是\(O(n)\),一旦n取较大数值,计算时间就会大大增加,极其容易出现超时的情况。
快速幂:
? 首先要在此列举两个前提:
计算机是通过二进制进行存储数据的,对二进制数据可以直接进行操作。
\(2^n+2^n=2*2^n=2^{n + 1}\)
? 对于\(x ^ n\),其中n可以表示为m位的二进制形式,即\(n=n_12^0+n_22^1+n_32^3+\cdots+n_m2^{m-1}\)
? 那么\(x ^ n=x ^ {n_12^0+n_22^1+n_32^3+\cdots+n_m2^{m-1}}\)
? 即\(x^n=x ^ {n_12^0}*x^{n_22^1}*x^{n_32^3}*\cdots*x^{n_m2^{m-1}}\)
? 根据前提1,计算机可以直接对二进制格式存储的数据进行读取,那么我们就可以对\(n\)一个个读取再对其进行累乘。
? 当取到第\(a\)位时,其乘数有通项公式:\(x^{n_a2^{a-1}}\)
? 通过标准库math,用代码实现:
int Pow (int x, int n) {
int result = 1;
int a = 1;
while(n) {
if(n & 1) result *= round( pow(x, 1 << (a - 1)) );//round的作用在于double转int时防止丢失精度,对1进行位运算是一种计算2的n次幂的快速方法
n >>= 1;
a++;
}
return result;
}
? 但实际上这个调用了标准库的代码并没有实现快速幂,因为仍然是采用pow()进行的运算
此处由 \(2^n+2^n=2*2^n=2^{n + 1}\)
即\((x ^ {2 ^ {n}} )^2=x ^ {2 ^ {n}} *x ^ {2 ^ {n}} = x ^ {2^n+2^n} = x ^ {2*2^n} =x ^ {2 ^ {n + 1}}\)
因此我们可以通过对前项进行二次幂运算得到后项
先得到首项\(f(1)=x^{2^{1-1}}=x\)
即令int f = x
具体实现:
int Pow (int x, int n) {
int result = 1;
int f = x;
while(n) {
if(n & 1) result *= f;
f *= f;
n >>= 1;
}
return result;
}
不难发现此时算法的时间复杂度由其次数的二进制位数而决定,即\(O(m)\)也就是\(O(log_2n)\)
另外因为此算法常常用于计算大数,所以int类型最好都换成long long类型,防止溢出。
原文链接:https://www.cnblogs.com/uzuki/p/11986478.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 前缀和 2020-05-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash