最新要闻
- 新车一超过60km/h就耳朵疼 车主:找了20多个人开都如此
- Win11新版最快5月推送:微软确认Moment 3更新
- 【全球热闻】富二代开保时捷碰瓷:专挑开豪车酒驾的敲诈 “赚了”30多万
- 聚焦:五粮液董事长曾从钦:在“时与势”中勇担使命,在“稳与进”中拓展空间,在“个与众”中升级维度
- 今年1号台风“珊瑚”下周或生成 预计2023年登陆我国的台风至少6个
- 夏日必备!楠木之舟EVA拖鞋19.9元:轻盈高回弹
- 男士洗脸专属大牌 妮维雅控油、祛痘洗面奶大促:不到20
- 世界最新:ChatGPT火爆 元宇宙房产崩盘!林俊杰买虚拟地产浮亏91%
- 岚图汽车1V4 “开火”保时捷、蔚来、奥迪、极氪!结果尴尬:无一车企回应
- 环球实时:4月09日10时江苏南通疫情最新消息 4月09日10时江苏南通今日确诊人数
- 【天天播资讯】为啥国产电动车在欧洲不好卖?海外汽车大V给出5点原因
- 环球热讯:今天国际护胃日 年轻人为啥会被胃癌盯上?胃病转向胃癌有5个信号
- 全球今头条!通用自动驾驶汽车撞上公交车 300辆无人出租车被召回
- 沙尘暴蓝色预警来了:北方将迎沙尘天气!官方分享防御指南
- “码农”劳动争议频发 厘清责任依法“护体”
- 焦点快播:存碰撞风险!特斯拉美国召回422辆Model 3:前悬架连杆有隐患
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
【全球聚看点】快速幂算法
快速幂算法
设计一个算法计算\(x^n\)的值。
(资料图片仅供参考)
根据定义最常见也最能瞬间想到的是如下的算法:
// 递归写法public int pow1(int x, int n) { if (n == 0) return 1; if (n == 1) return x; return x * pow1(x, n - 1);}// 循环写法public int pow2(int x, int n) { int y = 1; while (n) { y *= x; n--; } return y;}
但上面的算法的时间复杂度是\(O(n)\)
下面采用快速幂算法来解决这个问题。
在解决它之前先来看一下原理:
\[x^{n}=x^{n-a}x^a\]所以我们可以对本身要求的\(x^n\)对半分来求,只求一半的数,然后乘以自己本身就可以达到\(x^n\)
但是会出现的情况就是,对半分的时候会出现小数的情况,所以一定要分奇数和偶数的情况。
如果n分半了之后是偶数,那就直接对半分,如果是奇数则在对半分之后还要乘以一个x。
所以可以有下面的规律:
f(x, n) = { f(x, n/2)*f(x, n/2), // 当n为偶数 x*f(x, n/2)*f(x, n/2) // 当n为奇数}
所以得出快速幂算法1:
public int qPow1(int x, int n) { if (n == 0) return 1; if (n == 1) return x; if (n % 2 == 1) return x*f(x, n/2)*f(x, n/2); return f(x, n/2)*f(x, n/2);}
但是上面的算法明显没有任何增进,因为f(x, n/2)
要算两次,那和之前的\(O(n)\)的算法没什么区别。所以使用一个中间变量去接受一下,就可以提高算法效率。
public int qPow1(int x, int n) { if (n == 0) return 1; if (n == 1) return x; int t = f(x, n/2) if (n % 2 == 1) return x * t * t; return t * t;}
上面的快速幂算法还是比较好理解的,下面的快速幂算法就比较的炫技了我觉得,但是也就那样(原理还是上面的,只是不是对半分而已,而是根据进制数来分)。
下面采用二进制数来分。
假设我们要计算的是\(x^{10}\),那么10的二进制数是1010,所以有如下公式及变换:
\[x^{10}=x^{(10)_{10}}=x^{(1010)_2}=x^{1*2^3+0*2^2+1*2^1+0*2^0}=x^{8+2}=x^8x^2\]即
\[x^{10}=x^8x^2\]和上面第一种快速幂的算法类似,只不过上一种采用的分法是:
\[x^{10}=x^5x^5\]那么不管怎样分,最后肯定会被分到1,因为\(x^0=1\),其实上面的分法都隐藏了一个\(x^0\),即:
\[x^{10}=x^8x^2x^0\]所以状态是怎么转移的,即每一次迭代都是怎样变化的。初始化\(t=x^{2^0}=x^1=x\),那么下一代的变化是\(x^{2^1}\),它是由\(x^{2^0*2}\)变化而来,因为采用的是二进制。所以指数部分要想从\(2^0\)变换到\(2^1\)就需要乘以一个2.那也就是说,\(x\)变到\(x^2\).那么迭代变化过程就是\(t=t*t\).
\(x^{2^0*2}=(x^{2^0})^2\)
所以得到第二种快速幂算法代码:
public int qPow2(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 2) { case 1: y = y * t; // 这里不要写break case 0: t = t * t; } n = n / 2; } return y;}
那么这个采用二进制的方法分,当然也有三进制的,四进制的,五进制的等等。十六进制就不要搞了,因为不是进制越高就越快。
通过我对上面的二进制写法的快速幂就可以看出来我还会有其他进制的写法。那么下面就来看一下三进制的写法,然后四进制的就顺其自然就明白了。
那么三进制的推导过程也是和二进制的推导过程是类似的。假设计算的是\(x^{10}\).
\[x^{10}=x^{(10)_{10}}=x^{(101)_3}=x^{1*3^2+0+3^1+1*3^0}=x^9x\]所以从二进制的分法和三进制的分法可以看出,不管怎么分都是可以合起来达到10.只要能达到10的说明采用什么进制分法都是可以的。但并不是说采用的进制越高就越好。
那么初始化\(t=x^{3^0}=x\),那么下一代的变化是\(x^{3^1}\),它是由\(x^{3^0*3}\)变化而来,因为采用的是三进制。所以指数部分要想从\(3^0\)变换到\(3^1\)就需要乘以一个3.那也就是说,\(x\)变到\(x^3\).那么迭代变化过程就是\(t=t*t*t\).
\(x^{3^0*3}=(x^{3^0})^3\)
对比一下二进制和三进制的区别,所以四进制往后的就不需要我一个个推导了吧。
直接得出算法代码:
public int qPow3(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 3) { case 2: y = y * t; // 这里不要写break case 1: y = y * t; // 这里不要写break case 0: t = t * t * t; } n = n / 3; } return y;}
直接得出四进制版本的代码:
public int qPow4(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 4) { case 3: y = y * t; // 这里不要写break case 2: y = y * t; // 这里不要写break case 1: y = y * t; // 这里不要写break case 0: t = t * t * t * t; } n = n / 4; } return y;}
直接得出五进制版本的代码:
public int qPow5(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 5) { case 4: y = y * t; // 这里不要写break case 3: y = y * t; // 这里不要写break case 2: y = y * t; // 这里不要写break case 1: y = y * t; // 这里不要写break case 0: t = t * t * t * t; } n = n / 5; } return y;}
以此类推。。。就不写了。
可以去测试一下:
public class Main { public static void main(String[] args) { System.out.println("计算2的10次方:"); int x = 2, n = 10; Solution s = new Solution(); showMessage("pow1: ", s.pow1(x, n)); showMessage("pow2: ", s.pow2(x, n)); showMessage("qPow1: ", s.qPow1(x, n)); showMessage("qPow2: ", s.qPow2(x, n)); showMessage("qPow3: ", s.qPow3(x, n)); showMessage("qPow4: ", s.qPow4(x, n)); showMessage("qPow5: ", s.qPow5(x, n)); } public static void showMessage(String str, int result) { System.out.println("---------------------"); System.out.println(str + result); System.out.println("---------------------"); }}class Solution { public int pow1(int x, int n) { if (n == 0) return 1; if (n == 1) return x; return x * pow1(x, n - 1); } public int pow2(int x, int n) { int y = 1; while (n > 0) { y = y * x; n--; } return y; } public int qPow1(int x, int n) { if (n == 0) return 1; if (n == 1) return x; int t = qPow1(x, n / 2); if (n % 2 == 1) return x * t * t; return t * t; } public int qPow2(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 2) { case 1: y = y * t; // 这里不要写break case 0: t = t * t; } n = n / 2; } return y; } public int qPow3(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 3) { case 2: y = y * t; // 这里不要写break case 1: y = y * t; // 这里不要写break case 0: t = t * t * t; } n = n / 3; } return y; } public int qPow4(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 4) { case 3: y = y * t; // 这里不要写break case 2: y = y * t; // 这里不要写break case 1: y = y * t; // 这里不要写break case 0: t = t * t * t * t; } n = n / 4; } return y; } public int qPow5(int x, int n) { int y = 1; int t = x; while (n > 0) { switch (n % 5) { case 4: y = y * t; // 这里不要写break case 3: y = y * t; // 这里不要写break case 2: y = y * t; // 这里不要写break case 1: y = y * t; // 这里不要写break case 0: t = t * t * t * t * t; } n = n / 5; } return y; }}
终端输出:
计算2的10次方:---------------------pow1: 1024------------------------------------------pow2: 1024------------------------------------------qPow1: 1024------------------------------------------qPow2: 1024------------------------------------------qPow3: 1024------------------------------------------qPow4: 1024------------------------------------------qPow5: 1024---------------------
然后来分析一下它们的执行效率。
一般的\(O(n)\)就不说了,肯定是比\(O(log_2n)\)差的。主要是看是不是进制越高就越好?先给出答案,并不一定是。看着qPow5好像可以更快收到答案,但我们忘了看\(t=t*t*t*t*t\)这段代码和它上面的那一坨。然后再放大一点看,如果我采用的是十进制的写法。那会发现状态转移是\(t=t*t*t...(10个t)\)那和一般的pow有什么区别?所以,从这一点可以看出来并不是进制越高就越好。就好像是用\(x^8x^2\)和\(x^2x^8\)比效率一样。都是一样的嘛,如果外层循环少了,那里面的乘法就多了。所以得找个平衡的点。那这个平衡的点一般也就是对半的时候(并不是所有情况都是),所以我们折腾了那么久又回到了二进制的版本。因为计算机底层是二进制,所以我们就采用二进制的版本,然后再采用代码上的语法优化,这样应该是更好一点,因为其它进制的版本可优化的点并不多。下面给出二进制优化的版本。
public int qPow2(int x, int n) { int y = 1; int t = x; while (n > 0) { if (n % 2 == 1) y *= t; t *= t; n >>= 1; } return y;}
因为Java语法本身的原因在做位运算的时候不能像C/C++一样可以用非零当作真。所以if (n % 2 == 1) y *= t;
并不改变。但如果是C/C++的话可以采用下面的版本:
int qPow2(int x, int n) { int y = 1; while (n) { if (n & 1) y *= t; t *= t; n >>= 1; } return y;}
快速幂算法就先到这里结束了。
关键词:
世界热资讯!ASP.NET Core MVC 从入门到精通之接化发(一)
【全球聚看点】快速幂算法
私有化部署chatGPT,告别网络困扰
新车一超过60km/h就耳朵疼 车主:找了20多个人开都如此
Win11新版最快5月推送:微软确认Moment 3更新
【全球热闻】富二代开保时捷碰瓷:专挑开豪车酒驾的敲诈 “赚了”30多万
聚焦:五粮液董事长曾从钦:在“时与势”中勇担使命,在“稳与进”中拓展空间,在“个与众”中升级维度
今年1号台风“珊瑚”下周或生成 预计2023年登陆我国的台风至少6个
夏日必备!楠木之舟EVA拖鞋19.9元:轻盈高回弹
男士洗脸专属大牌 妮维雅控油、祛痘洗面奶大促:不到20
世界最新:ChatGPT火爆 元宇宙房产崩盘!林俊杰买虚拟地产浮亏91%
岚图汽车1V4 “开火”保时捷、蔚来、奥迪、极氪!结果尴尬:无一车企回应
环球实时:4月09日10时江苏南通疫情最新消息 4月09日10时江苏南通今日确诊人数
让民生福祉更有“数”——中国电子政务论坛聚焦数字政府建设
【天天播资讯】为啥国产电动车在欧洲不好卖?海外汽车大V给出5点原因
环球热讯:今天国际护胃日 年轻人为啥会被胃癌盯上?胃病转向胃癌有5个信号
全球今头条!通用自动驾驶汽车撞上公交车 300辆无人出租车被召回
沙尘暴蓝色预警来了:北方将迎沙尘天气!官方分享防御指南
“码农”劳动争议频发 厘清责任依法“护体”
焦点快播:存碰撞风险!特斯拉美国召回422辆Model 3:前悬架连杆有隐患
新资讯:朱晓彤 总算升职了!将在特斯拉墨西哥工厂获得一张新床
环球资讯:有人用ChatGPT月入十万了!70+款免费AI工具大搜罗
每日热门:sip消息拆包原理及组包流程
每日聚焦:超2250万台(套)各型装备投入春耕—— 农机化支撑粮食稳产增产
微头条丨小米14曝光:屏幕边框窄到没朋友 华星供货
贝克汉姆回复王濛大胆表白 感谢你的赞美:后者曾公开表示因为帅喜欢他
【天天时快讯】选台式机还是游戏本?13代酷睿旗舰处理器性能PK
环球报道:传音Tecno Camon 20 Premier曝光:天玑1200、五边形镜组
天天看点:广东白云技师学院短训班专业设置_广东白云技师学院
今日热讯:Vulnhub Bravery靶机 Walkthrough
焦点观察:69岁成龙说我还能打还能跳:是个奇迹
1999元神机诞生!Redmi Note 12 Turbo成了:用户好评率接近100%
天天快消息!Golang常用库之UUID
如何成为一名优秀的工程师?顶级程序员的5点建议
全球报道:曾称失控都是踩错单踏板!网友晒特斯拉新OTA 想要的制动恢复两档可选
全球播报:女子乘高铁把脚放前排乘客头上:狡辩称”鞋底不脏“
天天快资讯丨碱性食物有哪些_十大碱性食物排名
.Net Core Console&Generic HostBuilder
用阳光代替WiFi信号连网 沙特科学家这成果亮了
世界热点!【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(下)
世界速讯:电影《龙马精神》上映!刘德华清唱生日快乐歌祝福成龙
全球微动态丨连休5天!五一劳动节期间高速公路免费通行
口感自然 富含矿物质:依能天然苏打水2.3元(京东4元)
每日热议!博主带秤在淄博连逛10家店无缺斤少两:他很佩服
天天速递!投资者为何对苹果AR/VR设备没有信心?原因揭开
常州市天宁区人民检察院对一起拟不起诉案件公开听证
java -- 异常处理、Collection、Iterator迭代器、泛型
CentOS7-实现全网备份脚本
【天天报资讯】装机成本降了! 微星A620M-E主板到手799元:锐龙7 7800X3D绝配
关注:国宝熊猫回家记:丫丫要回来了
四川一麦田成网红打卡地:遭游客踩踏
windows提权
4799元 AOC新款27英寸电竞显示器上架:360Hz高刷、1ms响应
环球热议:没用的知识增加了!一图了解劳斯莱斯全部车型:最贵1.8亿
【天天速看料】王者荣耀镜取什么名字(王者镜的名字好听)
贵了2块钱 海底捞回应火锅小料涨价:门店自主定价
天天短讯!撤档一年半后 《超能一家人》定档7月21日:沈腾爆笑喜剧大片
时讯:科大讯飞刘聪:中国造大模型或在某些领域超越ChatGPT
世界视讯!pWnOS2
当前热文:python中shutil和shutil库的用法
Spring源码阅读系列--全局目录
今热点:郑州这些户籍室“周末无休”,周六日也能办理业务→
高校凌晨发录取通知要求半小时回复引热议 专家:不合理 好比半夜鸡叫
一口鲜气!春光0糖椰汁狂促:优惠30元到手仅需19.9
热资讯!定制纪念礼品瓷盘
MQ——消息积压如何处理
全球观点:Python 元编程
C++ 并发编程实战 第二章 线程管控
全球微速讯:gazebo小车模型(附带仿真环境)
今日快讯:哪吒纯电GT跑车遭贬低 CEO回应:就喜欢看不惯又干不掉我的样子
快资讯丨歪风盛行:日本将严惩暗拍空姐行为 违者将判处5年以下监禁或26万
999元起 中兴远航40上架:紫光展锐T760、10W快充
今日要闻!花枝招展
世界头条:浙江宁波空中突发巨响 官方回应:超高速飞行产生的音爆
当前观察:中兴Axon Pad官宣:四等宽窄边 支持一触互联
前沿资讯!百度:目前文心一言无官方App!已起诉苹果公司
世界百事通!海南航空恢复伦敦至长沙直航航线
啥事不干年薪130万:科技公司为何愿意“养闲人”?
今日最新!马斯克回应特斯拉降价:很多人有需求但买不起 只有降价才能满足需求
环球观速讯丨男子路边违停被查!司机竟掏出“联合国机动车驾驶证”
全球即时看!“云溪学子看云溪 云腾溪涌产业新”云溪区举行首届工业研学活动
环球观热点:《系列一》-- 4、xml配置文件解析之[默认]命名空间[标签]的解析
天天热推荐:面试题百日百刷-HBase中HTable API有没有线程安全问题,在程序是单例还是多例?
IPX6级防水防刮:宏碁墨尔本背包169元抄底(三种款式)
焦点快播:博主发薅高铁商务座羊毛攻略 20元享超VIP服务网友效仿:12306回应怒赞
环球快消息!平台回应机票一分钟三次变价:实时价格变动正常
英雄之光|陈旧的记录本 是他牵挂群众最温暖的见证
世界即时看!你的工资不能低于这数!31省份最低工资公布:时薪达标没
世界最资讯丨山东推出399元高铁环游套票:有效期5天、全省免费换乘
每日热议!DIY万能钥匙!主板检测灯你不得不懂
【焦点热闻】09款奥迪A4L标准型改装泪眼/导航作业
最新资讯:Docker-compose 到 Kubernetes 的迁移工具!
世界速看:全新深红配色亮相!iPhone 15 Pro超高清外观渲染图首曝:钛金属边框、Type-C接口
世界资讯:诈骗网红梅尼耶的MCN游良文化被申请破产:小刚学长等多位网红受骗
焦点速读:Java性能权威指南(第2版)读后总结与感想
动态:大学招聘体育老师 要求得过奥运冠军引热议:官方回应专业技能很重要
复星旅文2022年收入137.78亿元 徐晓亮:要尽快追回过去三年失去的业绩
【天天报资讯】K8S圣经12:SpringCloud+Jenkins+ K8s Ingress 自动化灰度发布
回顾、信号、flask-script、sqlalchemy介绍和快速使用、创建操作数据表
今日快看!ASP.NET Core MVC 从入门到精通之初窥门径