考研复习资料大汇总.pdf
分治法——大整数的乘法
请设计一个有效的算法,可以进行两个n位大整数的乘法运算 2 ◆小学的方法:O(n ) 效率太低 ◆分治法: X =复杂度分析 a b O(1) n1 T(n) Y = c d 4T(n/2)+O(n)n1 2 T(n)=O(n ) 没有改进 X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 分治法——大整数的乘法 请设计一个有效的算法,可以进行两个n位大整数的乘法运算 2 ◆小学的方法:O(n ) 效率太低 ◆分治法: 复杂度分析 O(1) n1 n n/2 T(n)
XY = ac 2 + (ad+bc) 2 + bd 3T(n/2)+O(n)n1 log3 1.59 为了降低时间复杂度,必须减少乘法的次数。 T(n)=O(n ) =O(n )✓较大的改进
• XY = ac 2n + ((a-b)(d-c)+ac+bd) 2n/2 + bd
1. XY = ac 2n + ((a+b)(d+c)-ac-bd) 2n/2 + bd
细节问题:两个XY的复杂度都是O(nlog3) ,但考虑到a+c,b+d可
能得到m+1位的结果,使问题的规模变大,故不选择第2种方案。 分治法——循环赛日程表 设计一个满足以下要求的比赛日程表: (1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能赛一次; (3)循环赛一共进行n-1天。
按分治策略,将所有的选手分为两半,n个选手的比赛日程表
就可以通过为n/2个选手设计的比赛日程表来决定。递归地用
对选手进行分割,直到只剩下2个选手时,比赛日程表的制定
就变得很简单。这时只要让这2个选手进行比赛就可以了。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 分治法——线性时间选择
给定线性序集中n个元素和一个整数k,1≤k≤n,要求找
出这n个元素中第k小的元素 template
栏 目:研究生考试
下一篇:弹性力学试题及标准答案.docx
本文标题:考研复习资料大汇总.pdf
本文地址:https://www.365weibook.com/html/20201021/164998.html
您可能感兴趣的文档
- 10-21华东师范大学历年教育硕士333真题汇编推荐文档.docx
- 10-21口腔考研 复习必备集.docx
- 10-21完整2008年1月考研管理类联考真题及答案解析推荐文档.docx
- 10-21完整2016北京体育大学运动人体科学考研真题及答案详解版推荐文
- 10-21完整上海师范大学高数试题11.docx
- 10-21完整上海师范大学高数试题12.docx
- 10-21完整版2017年考研计算机统考408真题.docx
- 10-21完整版上海大学自然辩证法考试整理.docx
- 10-21有机化学考研复习笔记整理分专题汇总.docx
- 10-212012年-2015考研英语一真题与答案完整解析.docx
正常预览或下载提示:
本页面文档预览是由服务器自动提取的部分内容,并不是文档乱码。如您需要预览全文或下载文档,请点击页面左侧(点击去预览文档全文或下载文档)按钮,进行全文预览或下载。