舍伍德演演算法

設A是一個確定性演演算法，當它的輸入實例為x時所需的計算時間記為。設Xn是演演算法A的輸入規模為n的實例的全體，則當問題的輸入規模為n時，演演算法A所需的平均時間為

這顯然不能排除存在使得遠遠大於的可能性。

希望獲得一個隨機化演演算法B，使得對問題的輸入規模為n的每一個實例均有

這就是舍伍德演演算法設計的基本思想。當s(n)與相比可忽略時，舍伍德演演算法可獲得很好的平均性能。

Sherwood演演算法同類：

（1）線性時間選擇演演算法

（2）快速排序演演算法

有時也會遇到這樣的情況，即所給的確定性演演算法無法直接改造成舍伍德型演演算法。此時可藉助於隨機預處理技術，不改變原有的確定性演演算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德演演算法的效果。例如，對於確定性選擇演演算法，可以用下面的洗牌演演算法shuffle將數組a中元素隨機排列，然後用確定性選擇演演算法求解。這樣做所收到的效果與舍伍德型演演算法的效果是一樣的。

templatevoid Shuffle(Type a[],int n){ // 隨機洗牌演演算法 static RandomNumber rnd ; for(int i=0;i

1.舍伍德型演演算法的設計思想還可用於設計高效的數據結構。

2.如果用有序鏈表來表示一個含有n個元素的有序集S，則在最壞情況下，搜索S中一個元素需要計算時間。

3.提高有序鏈表效率的一個技巧是在有序鏈表的部分結點處增設附加指針以提高其搜索性能。在增設附加指針的有序鏈表中搜索一個元素時，可藉助於附加指針跳過鏈表中若干結點，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。

4.應在跳躍表的哪些結點增加附加指針以及在該結點處應增加多少指針完全採用隨機化方法來確定。這使得跳躍表可在O(logn)平均時間內支持關於有序集的搜索、插入和刪除等運算。

在一般情況下，給定一個含有n個元素的有序鏈表，可以將它改造成一個完全跳躍表，使得每一個k級結點含有個指針，分別跳過

個中間結點。第i個k級結點安排在跳躍表的位置處，。這樣就可以在時間內完成集合成員的搜索運算。在一個完全跳躍表中，最高級的結點是級結點。

完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運算，但不適應於集合動態變化的情況。集合元素的插入和刪除運算會破壞完全跳躍表原有的平衡狀態，影響後繼元素搜索的效率。

為了在動態變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中k級結點數維持在總結點數的一定比例範圍內。注意到在一個完全跳躍表中，50%的指針是0級指針；25%的指針是1級指針；的指針是k級指針。因此，在插入一個元素時，以概率引入一個0級結點，以概率引入一個1級結點，…，以概率引入一個k級結點。另一方面，一個i級結點指向下一個同級或更高級的結點，它所跳過的結點數不再準確地維持在。經過這樣的修改，就可以在插入或刪除一個元素時，通過對跳躍表的局部修改來維持其平衡性。

在一個完全跳躍表中，具有i級指針的結點中有一半同時具有級指針。為了維持跳躍表的平衡性，可以事先確定一個實數，並要求在跳躍表中維持在具有i級指針的結點中同時具有級指針的結點所佔比例約為p。為此目的，在插入一個新結點時，先將其結點級別初始化為0，然後用隨機數生成器反覆地產生一個間的隨機實數q。如果，則使新結點級別增加1，直至。由此產生新結點級別的過程可知，所產生的新結點的級別為0的概率為，級別為1的概率為級別為i的概率為

。如此產生的新結點的級別有可能是一個很大的數，甚至遠遠超過表中元素的個數。為了避免這種情況，用作為新結點級別的上界。其中n是當前跳躍表中結點個數。當前跳躍表中任一結點的級別不超過