實驗原理

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

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

實驗步驟

對于選擇問題而言,用擬中位數作為劃分基準可以保證在最壞的情況下用線性時間完成選擇。如果只簡單地用待劃分數組的第一個元素作為劃分基準，則算法的平均性能較好，而在最壞的情況下需要O(n^2)計算時間。舍伍德選擇算法則隨機地選擇一個數組元素作為劃分基準，這樣既保證算法的線性時間平均性能，又避免了計算擬中位數的麻煩。有時也會遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預處理技術，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。

關鍵代碼

template<class Type> Type select(Type a[], int l, int r, int k){while (true){if (l >= r){return a[l];}int i = l, j = l + rand() % (r - 1 + 1);//隨機選擇劃分基準Swap(a[i], a[j]);j = r + 1;Type pivot = a[l];//以劃分基準為軸做元素交換while (true){while (a[++i] < pivot);while (a[--j] > pivot);if (i >= j){break;}Swap(a[i], a[j]);}if (j - l + 1 == k){//第k小return pivot;}//a[j]必然小于pivot,做最后一次交換，滿足左側比pivot小，右側比pivot大a[l] = a[j];a[j] = pivot;//對子數組重復劃分過程if (j - l + 1 < k){k = k - j + l - 1;//右側：k-(j-l+1)=k-j+l-1l = j + 1;}else{r = j - 1;}} } template <class Type> inline void Swap(Type& a, Type& b){Type temp = a;a = b;b = temp; }

總結

以上是生活随笔為你收集整理的算法实验-Sherwood型线性时间选择问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。