一、舍伍德(Sherwood)算法

舍伍德算法是概率算法的一種，該文在比較線性表的順序存儲與鏈式存儲的特點之后，提出了一種較優(yōu)的數(shù)據(jù)結(jié)構(gòu)——用數(shù)組模擬鏈表。理論上證明了采用舍伍德算法進行查找運算的時間復(fù)雜度為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)相比可忽略時，舍伍德算法可獲得很好的平均性能。

舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設(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應(yīng)該取得充分大，因此可取m為機器大數(shù)，另應(yīng)取gcd(m,d)=1，所以d可取為一素數(shù)。我們建立一個隨機數(shù)類RandomNumber，包含一個需由用戶初始化的種子randSeed。給定初始種子后，即可產(chǎn)生與之相應(yīng)的隨機序列。種子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ù)。