- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
舍伍德算法
舍伍德算法
目录
舍伍德算法原理
舍伍德算法应用条件
舍伍德算法的具体应用
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,32
8
舍伍德算法具体应用实例
3. 继续查找直到循环结束,ij (i=5,j=4) 低区个数k 所以在低区子数组中。
3,8,2,5
4. 重复上述过程直到找到结果。
具体程序
9
舍伍德算法具体应用
10
谢谢!
文档评论(0)