一、舍伍德(Sherwood)算法

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

基本思想

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

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

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

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

延伸閱讀：

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

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

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

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

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