已阅读5页，还剩10页未读， 继续免费阅读
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
一类算法复合的方法,问题描述,维护集合S，初始时为空。有N个操作需要依次处理B X 在S中插入一个整数XA Y 询问S中被Y除余数最小的数，如果有多个则任取一个1N40000，1X,YR=500000允许离线算法,初步分析,算法1：对询问中每个不同的Y，维护它对应的询问当前的答案时间复杂度为O(N2)，不能解决问题但当询问中出现的不同Y的个数比较少时会很快，时间复杂度可以写成O(不同Y的个数N),进一步分析,当遇到一个询问A Y时，要在S中寻找使得x mod Y最小的数x把这里的x写成kY+r，其中0rR0.5时，算法2已经可以接受了我们可以对这部分很少的Y的询问使用另一种算法算法1当询问中的不同的Y很少时会很快，所以这里的另一种算法可以选择算法1,算法3,设一个边界值K对YK的询问使用算法2 O(NR/K)对YK的询问使用算法1 O(NK)总时间复杂度O(NK+NR/K)将N和R看作常数，容易得出当K=R0.5时总时间复杂度最小，为O(NR0.5)算法3可以完全解决本题,我们解决本题的重点是：不使用统一的算法，而是同时使用这个问题的两种算法，分别解决问题中的两个互补的部分我的论文里还有另一个例子SPOJ RECTANGL这个问题同样可以通过同时使用两种不同的算法得到较好的解决,总结,一个问题往往可以被看作是由若干个相对并列的部分组成起来的通常对这些部分使用统一的算法而有时这个问题可以使用多种算法解决，并且当这些算法应用在问题中不同特征的部分时，会有不同的效果这时就可以将这些算法复合，对问题的不同部分，根据它们的特征分别选择使用对这个部分较优的算法,总结,两个算法合并起来后，很神奇地得到了一个更优的算法这是因为这两种算法具有互补的优势，而我们把问题分成了若干部分，对每一部分根据其特征使用较优的算法，就使得两种算法的优势得到了结合,总结,每个算法都有各自的优势和劣势如果我们取长补
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论