




已阅读5页,还剩1页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法设计与分析分治—大整数乘法信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版问题描述:进行两个n位大整数的乘法运算。竖乘法:O(n2)
效率太低分治法:X=
Y=abcdXY=ac2n+(ad+bc)2n/2+bdX=a2n/2+bY=c2n/2+d复杂度分析:T(n)=O(n2)没有改进以乘法为基本操作分治法改进:减少子问题个数XY=ac2n+(ad+bc)2n/2+bd1.XY=ac2n+((a-b)(d-c)+ac+bd)2n/2+bd2.XY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd复杂度分析:T(n)=O(nlog3)=O(n1.59)注:考虑到a+c,b+d可能得到m+1位的结果,使问题的规模变大,故选择第1种方案。更快的算法:如果将大整数分成更多段,用更复杂的方式把它们组合起来,可以得到更优的算法;基于该思想出现了复杂的分治算法--快速傅利叶变换(FastFourierTransform)算法。测试选择题:本节课给出的大整数乘法的分治算法,在优化过程中所使用的方法是()
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《天子传奇win98版》剧情攻略
- 项目团支部介绍课件
- 韶关学院工程力学课件
- 2025年轻水堆核电站及配套产品项目合作计划书
- xx河流排水防涝设施建设项目规划设计方案(模板范文)
- 细胞生物学测试试题库含答案
- 2025年增味剂项目发展计划
- 现代商场超市连锁店星级服务培训 第三章 商品管理技能培训
- 卫星互联网行业市场分析1
- 卫生部突发中毒事件卫生应急预案
- 新闻发布会培训
- 主管护师竞聘汇报
- 公园突发事件应急管理预案
- 第4单元-单元素养测评(B)-2024-2025学年语文部编版四年级上册(含答案解析)
- 2025年内蒙古农村信用社招聘笔试参考题库含答案解析
- 2025年云南省文山州教育局直属事业单位招聘27人历年管理单位笔试遴选500模拟题附带答案详解
- GA/T 2150-2024出入境证件智能签注设备
- 初中数学课后作业设计问题及优化探讨
- 档案库房安全
- 医疗机构感染预防与控制基本制度解读
- 星级绿色建筑评价评分表
评论
0/150
提交评论