舍伍德(Sherwood)算法是什么?

一、舍伍德(Sherwood)算法

舍伍德算法是概率算法的一種，該文在比較線性表的順序存儲與鏈式存儲的特點之后，提出了一種較優(yōu)的數(shù)據(jù)結(jié)構(gòu)——用數(shù)組模擬鏈表。理論上證明了采用舍伍德算法進行查找運算的時間復雜度為0(n^1/2)。

基本思想

設(shè)A是一個確定性算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實例的全體，則當問題的輸入規(guī)模為n時，算法A所需的平均時間為這顯然不能排除存在x∈Xn使得 tA(x)遠遠大于tA(n)的可能性。

希望獲得一個概率算法B，使得對問題的輸入規(guī)模為n的每一個實例均有

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

舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設(shè)法消除這種最壞行為與特定實例之間的關(guān)聯(lián)性。

延伸閱讀：

二、數(shù)值隨機化算法

數(shù)值隨機化算法常用于數(shù)值問題的求解，得到的往往是近似解，且近似解的精度隨計算時間的增加而不斷提高。在許多情況下，要計算出問題的精確解是不可能的或沒有必要的，因此用數(shù)值隨機化算法可以得到相當滿意的解。隨機數(shù)

隨機數(shù)在隨機化算法中扮演著十分重要的角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在隨機化算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。線性同余法是產(chǎn)生偽隨機數(shù)最常用的方法。由線性同余法產(chǎn)生的隨機序列a1,a2,a3,…,an滿足：a0 = d

an = (ban-1 + c)mod m? n = 1,2,…

式中，b>=0，c>=0，d>=m。d稱為該隨機序列的種子，如何選取該方法中的常數(shù)b、c和m直接關(guān)系到所稱生的隨機序列的隨機性能，這是隨機性能理論研究的內(nèi)容。從直觀上看，m應該取得充分大，因此可取m為機器大數(shù)，另應取gcd(m,d)=1，所以d可取為一素數(shù)。我們建立一個隨機數(shù)類RandomNumber，包含一個需由用戶初始化的種子randSeed。給定初始種子后，即可產(chǎn)生與之相應的隨機序列。種子randSeed是一個無符號整數(shù)，可由用戶選定也可用系統(tǒng)時間自動產(chǎn)生。函數(shù)Random()的輸入?yún)?shù)n<=65535是一個無符號整數(shù)，返回0~n-1范圍內(nèi)的隨機整數(shù)。函數(shù)fRandom()返回一個0-1之間的隨機實數(shù)。