算法设计与分析 课件 9.2-概率算法 - 舍伍德算法_第1页
算法设计与分析 课件 9.2-概率算法 - 舍伍德算法_第2页
算法设计与分析 课件 9.2-概率算法 - 舍伍德算法_第3页
算法设计与分析 课件 9.2-概率算法 - 舍伍德算法_第4页
算法设计与分析 课件 9.2-概率算法 - 舍伍德算法_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

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

文档简介

算法设计与分析概率算法-舍伍德信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版当一个确定性算法的平均和最坏时间复杂度差别较大时，可在确定性算法中引入随机性将确定算法改造为概率算法。这类通过引入随机性减少算法的最坏情形对应输入的出现次数的算法称为舍伍德算法。

对确定性算法A，记输入实例I的计算时间为tA(I)。设Dn是算法A的输入规模为n的全体实例，可能存在I∈Dn使得。目标：实现概率算法B，使得对规模为n的问题的每个实例均有。其中，s(n)与相比可忽略。defkth_small(a,b,e,k):#在a[b]~a[e]中找第k小元素ifb>eork<1ork>e-b+1:return-1p=partition(a,b,e)m=p-bifk==m+1:returna[p]ifk<m+1:returnkth_small(a,b,p-1,k)returnkth_small(a,p+1,e,k-m-1)例：选择第k小元素defpartition(a,b,e):#将a[b]~a[e]以基准数为标准分为三部分i=bj=e

x=a[b]whilei<j:#从两边开始搜索与基准数进行比较whilei<janda[j]>=x:j-=1ifi<j:a[i]=a[j]i+=1whilei<janda[i]<x:i+=1ifi<j:a[j]=a[i]j-=1a[i]=xreturni舍伍德算法实现：选择第k小元素defpartition(a,b,e):#将a[b]~a[e]以基准数为标准分为三部分i=bj=ek=b+randint(0,e-b)#随机选择基准元素a[b],a[k]=a[k],a[b]#将随机选择的基准元素与首位元素互换x=a[b]whilei<j:whilei<janda[j]>=x:j-=1ifi<j:a[i]=a[j]i+=1whilei<janda[i]<x:i+=1ifi<j:a[j]=a[i]j-=1a[i]=xreturni优势：

对所有实例的计算时间相对均匀，计算总能求得问题的一个解，且求得的解总是正确的。关键：

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论