舍伍德（Sherwood）算法学习笔记.pdfVIP

舍伍德（Sherwood）算法学习笔记

⼀.概念引⼊

设A是⼀个确定性算法，当它的输⼊实例x时所需的计算时间记tA(x)。设Xn

是算法A的输⼊规模n的实例的全体，则当问题的输⼊规模n时，算法A所需的平均

时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得⼀个随机化算法B，使得

对问题的输⼊规模n的每⼀个实例均有。这就是舍伍德算法设计的基本思想。当s(n)

与tA(n)相⽐可忽略时，舍伍德算法可获得很好的平均性能。

概率算法的⼀个特点是对同⼀实例多次运⽤同⼀概率算法结果可能同。舍伍德算

法(O(sqrt(n))，综合了线性表和线性链表的优点)总能求的问题的⼀个正确解，当⼀个

确定性算法在最坏情况和平均情况下差别较⼤时可在这个确定性算法中引⼊随机性将

之改造成⼀个舍伍德算法；引⼊随机性不是为了消除最坏，⽽是为了减少最坏和特定

实例的关联性。⽐如线性表a的查找若是找10(独⼀⽆⼆)，如果在a[0]则O(1),若是最

后⼀个则O(n)，可见时间与输⼊实例有关，此时可引⼊随机性将之改造成⼀个舍伍德

算法。

有时候⽆法直接把确定性算法改造为舍伍德算法，这时候对输⼊洗牌。

下⾯是洗牌算法源代码：

importjava.util.Random;

publicclassShuffle{

publicstaticvoimain(String[]args){

inta[]=newint[]{1,2,4,5,8};

/*

*Collections.shuffle(list)参数只能是list

*/

myShuffle(a);

for(inti:a){

//犯了个低级错误，输出了a[i]，结果数组下标越界异常

System.out.print(i+);

}

System.out.println();

}

privatestaticvoimyShuffle(int[]a){

intlen=a.length;

for(inti=0;ilen;i++){

Randomr=newRandom();

//直接Random.nextInt(len)提⽰静态⽅法⾥⽆法引⽤

intj=r.nextInt(len);

//Collections.swap(list,i,j)必须是list类型

if(i!=j){//原来没加这个条件

inttemp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

}

⼆.舍伍德思想解决迅雷2010年校招--发牌

问题描述：52张扑克牌分发给4⼈，每⼈13张，要求保证随机性。已有随机整数

⽣成函数rand()，但开销较⼤。请编写函数实现voiddeal(inta[],intb[],intc[],intd[])，

扑克牌⽤序号0-51表⽰，分别存在⼤⼩13的a，b,c,四个数组中，要求尽可能⾼

效。

importjava.util.Random;

publicclassPoker{

/*

*这道题确实不怎么明⽩，直接初始化后洗牌算法不得了

*不过解答只是替换nextInt，直接线性同余了，交换次数也减少了

*交换次数是随机产⽣的

*/

//为⽅便swap和deal函数使⽤

staticintarray[]=newint[52];

publicstaticvoidmain(String[]args){