欢迎来到文档下载导航网!

考研复习资料大汇总.pdf

时间:2020-10-21|当前位置:首页 > 教育文档 > 研究生考试 > |用户下载:

考研复习资料大汇总.pdf

分治法——大整数的乘法 请设计一个有效的算法,可以进行两个n位大整数的乘法运算 2 ◆小学的方法:O(n ) 效率太低 ◆分治法: X =复杂度分析 a b  O(1) n1 T(n)  Y = c d 4T(n/2)+O(n)n1  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)n1  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 Type RandomizedSelect(Type a[],int p,int r,int k) { if (p==r) return a[p]; int i=RandomizedPartition(a,p,r), j=i -p+1; if (k<=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j); } 2 在最坏情况下,算法randomizedSelect需要O(n )计算时间 但可以证明,算法randomizedSelect可以在O(n)平均时间内 找出n个输入元素中的第k小元素。 分治法——线性时间选择 如果能在线性时间内找到一个划分基准,使得 按这个基准所划分出的2个子数组的长度都至少 为原数组长度的ε倍(0<ε<1是某个正常数),那 么就可以在最坏情况下用O(n)时间完成选择任 务。 例如,若ε=9/10 ,算法递归调用所产生的子 数组的长度至少缩短1/10。所以,在最坏情 况下,算法所需的计算时间T(n)满足递归式 T(n)≤T(9n/10)+O(n) 。由此可得T(n)=O(n)。 分治法——线性时间选择 ⚫将n个输入元素划分成n/5个组,每组5个元素,只可能 有一个组不是5个元素。用任意一种排序算法,将每组中的 元素排好序,并取出每组的中位数,共n/5个。 ⚫递归调用select来找出这n/5个元素的中位数。如果 n/5是偶数,就找它的2个中位数中较大的一个。以这个 元素作为划分基准。 设所有元素互不相同。在这种情况下, 找出的基准x至少比3(n-5)/10个元素 大,因为在每一组中有2个元素小于 本组的中位数,而n/5个中位数中又 有(n-5)/10个小于基准x。同理,基准 x也至少比3(n-5)/10个元素小。而当 n≥75时,3(n-5)/10≥n/4所以按此基 准划分所得的2个子数组的长度都至 少缩短1/4。 Type Select(Type a[], int p, int r, int k) { if (r-p<75) { 用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; 复杂度分析  C n75 }; T(n) 1  Cn+T(n/5)+T(3n/4)n75 2  for ( int i = 0; i<=(r-p-4)/5; i++ ) T(n)=O(n) 将a[p+5*i]至a[p+5*i+4]的第3小元素 与a[p+i]交换位置; //找中位数的中位数,r-p-4 即上面所说的n-5 上述算法将每一组的大小定为5 ,并选取75作为是否作递归 Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); 调用的分界点。这2点保证了T(n)的递归式中2个自变量之和 int i=Partition(a,p,r, x), n/5+3n/4=19n/20=εn,0<ε<1。这是使T(n)=O(n)的关键之 处。当然,除了5和75之外,还有其他选择。 j=i -p+1; if (k<=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j); } 动态规划——0-1背包问题 给定n 种物品和一背包。物品i 的重量是w ,其价值 i 为v ,背包的容量为C 。问应如何选择装入背包的物 i 品,使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。 n max

上一篇:(时间管理)考研规划考研资料考研时间安排.pdf

栏    目:研究生考试

下一篇:弹性力学试题及标准答案.docx

本文标题:考研复习资料大汇总.pdf

本文地址:https://www.365weibook.com/html/20201021/164998.html

    正常预览或下载提示:

    本页面文档预览是由服务器自动提取的部分内容,并不是文档乱码。如您需要预览全文或下载文档,请点击页面左侧(点击去预览文档全文或下载文档)按钮,进行全文预览或下载。

推荐下载

联系我们 | 广告投放 |网站地图

免责申明:本网站不提供任何形式的下载服务,因此与之有关的知识产权纠纷本网站不承担任何责任。

如果侵犯了您的权利,请与我们联系,我们将进行删除处理。