舍伍德算法完整版本_第1页
舍伍德算法完整版本_第2页
舍伍德算法完整版本_第3页
舍伍德算法完整版本_第4页
舍伍德算法完整版本_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

舍伍德算法目录舍伍德算法原理舍伍德算法应用条件舍伍德算法的具体应用3舍伍德算法原理设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得的可能性。希望获得一个概率算法B，使得对问题的输入规模为n的每一个实例均有这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。4舍伍德算法应用条件当一个确定行算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。该算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。5舍伍德算法具体应用

6舍伍德算法具体应用

7舍伍德算法具体应用实例找出数组a中第k小的元素a[6]={5,8,2,15,32,3}k=3,l=1,r=6随机找到一个数字15.交换a[0]与15。15，8，2，5，32，3进行划分数组。i=4,j=5

15，8，2，5，3，328舍伍德算法具体应用实例3.继续查找直到循环结束，i>j(i=5,j=4)低区个数>k所以在低区子数组中。

3，8，2，54.重复

人人文库> 全部分类> 生活休闲 > 家居装修

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论