算法设计与分析 课件 9.2-概率算法 - 舍伍德算法.pptx

算法设计与分析

概率算法-舍伍德;当一个确定性算法的平均和最坏时间复杂度差别较大时，可在确定性算法中引入随机性将确定算法改造为概率算法。

这类通过引入随机性减少算法的最坏情形对应输入的出现次数的算法称为舍伍德算法。;对确定性算法A，记输入实例I的计算时间为tA(I)。设Dn是算法A的输入规模为n的全体实例，可能存在I∈Dn使得。

;defkth_small(a,b,e,k):#在a[b]~a[e]中找第k小元素

ifbeork1orke-b+1:

return-1

p=partition(a,b,e)

m=p-b

ifk==m+1:

returna[p]

ifkm+1:

returnkth_small(a,b,p-1,k)

returnkth_small(a,p+1,e,k-m-1);defpartition(a,b,e):#将a[b]~a[e]以基准数为标准分为三部分

i=b

j=e

x=a[b]

whileij:#从两边开始搜索与基准数进行比较

whileijanda[j]=x:

j-=1

ifij:

a[i]=a[j]

i+=1

whileijanda[i]x:

i+=1

ifij:

a[j]=a[i]

j-=1

a[i]=x

returni;舍伍德算法实现：选择第k小元素;优势：

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

关键：

与相应的确定算法相比，其时间复杂性并没有改进。;测试