0044算法笔记——【随机化算法】舍伍德(Sherwood)算法和线性时间选择问题

1、1、舍伍德(Sherwood)算法设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输匚(珀二乂尺I入规模为n时，算法A所需的平均时间为仁这显然不能排除存在xXn使得:J；"的可能性。希望获得一个随机化算法B,使得对问题的输入规模为的每一个实例均有门=，："：1-“：1。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。2、线性时间选择算法D随机划分选择基准对于选择问题而言,用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。如果只简单地用

2、待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏的情况下需要0(n"2)计算时间。舍伍德选择算法则随机地选择一个数组元素作为划分基准，这样既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。非递归的舍伍德型选择算法如下：cppviewplaincopy1. 随机化算法线性时间选择随机划分选择基准2. #include"stdafx.h"3. #include"RandomNumber.h"4. #include<iostream>5. usingnamespacestd;6.7.8.9.10.11.12.13

3、.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.template<classTypeTypeselect(Typea,intl,intr,intk);template<classTypeTypeselect(Typea,intn,intk);template<classTypeinlinevoidSwap(Type&a,Type&b);intmain()inta=5,7,3,4,8,6,9,1

4、,2;cout<<"原数组为："<<endl;for(inti=0;i<9;i+)cout<<ai<<""cout<<endl;cout<<"所给数组第7小元素为："<<select(a,9,7)<<endl;return0;/计算a0:n-1中第k小元素/假设an是一个键值无穷大的元素template<classTypeTypeselect(Typea,intn,intk)if(k<1|k>n)cout<&l

5、t;"请输入正确的k!"<<endl;return0;returnselect(a,0,n-1,k);/计算al:r中第k小元素template<classType>Typeselect(Typea,intl,intr,intk)staticRandomNumberrnd;while(true)if(l>=r)50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89

6、.90.91.92.93.returnal;inti=l,j=l+rnd.Random(r-l+1);/随机选择划分基准Swap(ai,aj);j=r+1;Typepivot=al;/以划分基准为轴做元素交换while(true)while(a+i<pivot);while(a-j>pivot);if(i>=j)break;Swap(ai,aj);if(j-l+1=k)/第k小returnpivot;/aj必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大al=aj;aj=pivot;对子数组重复划分过程if(j-l+1<k)k=k-j+l-

7、1;/右侧：k-(j-l+1)=k-j+l-1l=j+1;elser=j-1;94. 95.95. template<classType96. inlinevoidSwap(Type&a,Type&b)98. 99.Typetemp=a;100.a=b;101.102.b=temp;程序运行结果如图:原数组为=5734S691E匝氛鞍织曙邛远素为谙按任意键-:2)随机洗牌预处理有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。例如，对于确定性选择算法

8、，可以用下面的洗牌算法shuffle将数组a中元素随机排列，然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。cppviewplaincopy1. 随机化算法线性时间选择输入预处理，洗牌2. #include"stdafx.h"3. #include"RandomNumber.h"4. #include<iostream>5. usingnamespacestd;67. template<classType8. Typeselect(Typea,intl,intr,intk);9.9. template<c

9、lassType10. Typeselect(Typea,intn,intk);12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.template<classTypevoidShuffle(Typea,intn);template<classTypeinlinevoidSwap(Type&a,Type&b);intmain()inta=5,7,3,4

10、,8,6,9,1,2;cout<<"原数组为："<<endl;for(inti=0;i<9;i+)cout<<ai<<""cout<<endl;Shuffle(a,9);/洗牌cout<<"洗牌后数组为："<<endl;for(inti=0;i<9;i+)cout<<ai<<""cout<<endl;cout<<"所给数组第7小元素为："<<

11、select(a,9,7)<<endl;return0;/计算a0:n-1中第k小元素/假设an是一个键值无穷大的元素template<classTypeTypeselect(Typea,intn,intk)if(k<1|k>n)cout<<"请输入正确的k!"<<endl;return0;returnselect(a,0,n-1,k);/计算al:r中第k小元素template<classTypeTypeselect(Typea,intl,intr,intk)while(true)57.58.59.60.61.6

12、2.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.96.97.98.99.100.if(l>=r)returnal;inti=l;intj=r+1;Typepivot=al;/以划分基准为轴做元素交换while(true)while(a+i<pivot);while(a-j>pivot);if(i>=j)break;Swap(ai,aj);if(j-l+1=k)/第k小returnpivot;右侧比pivot大/aj必然小于pivot,做最后一次交换，满足左侧比pivot小,al=aj;aj=pivot;对子数组重复划分过程if(j-l+1<k)k=k-j+l-1;/右侧：k-(j-l+1)=k-j+l-1l=j+1;elser=j-1;template<classType>101.inlinevoidSwap(Type&a,Type&b)102.103.Typetemp=a;104.a=b;1