劉顯德 于瑞芳 李盼池 劉曉明

（東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 大慶 163318）

1 引言

算法是計(jì)算機(jī)科學(xué)的靈魂，某些經(jīng)典的算法往往只有很少幾行，但是卻能解決很多大問(wèn)題。隨機(jī)算法可以分為三大類，即Las Vegas型算法、Monte Carlo型算法和Sherwood型算法［1］。Las Vegas型算法建立的那些隨機(jī)算法總是或者給出正確的解，或者算法求解失敗，但是再次運(yùn)行算法就有成功的可能［2］。而Monte Carlo型算法總是給出解，但是偶爾可能會(huì)產(chǎn)生非正確的解。Sherwood型算法的思想方法在于在原有的確定型算法基礎(chǔ)上，引入隨機(jī)化因素，改變問(wèn)題的輸入或求解順序，設(shè)法消除算法的時(shí)間復(fù)雜度與輸入實(shí)例之間的關(guān)系［3］。文獻(xiàn)［4］提出了用Java來(lái)設(shè)計(jì)算法的一種方法，文獻(xiàn)［5］提出了一種改進(jìn)的隨機(jī)算法，可以使得算法執(zhí)行比較的期望次數(shù)減少到小于3n，文獻(xiàn)［6］提出Las Vegas算法可以看成是Monte Carlo算法當(dāng)錯(cuò)誤概率為零時(shí)的情況，文獻(xiàn)［7］提出應(yīng)用分段線性分布模型來(lái)模擬隨機(jī)算法運(yùn)行時(shí)間分布的一種方法，文獻(xiàn)［8～10］研究了隨機(jī)算法異步并行化問(wèn)題。本文研究的隨機(jī)化快速選擇算法即屬于Sherwood型算法。

2 算法復(fù)雜度分析

2.1 最壞時(shí)間復(fù)雜度

在最壞情況下，隨機(jī)數(shù)發(fā)生器在 j次循環(huán)時(shí)選擇第 j個(gè)元素，j=1，2，…，n，這樣只有一個(gè)元素被拋棄，由于把A分成A1，A2和A3所需要的比較次數(shù)恰好為n，所以算法在最壞情況下所做的元素比較的總次數(shù)是

設(shè)隨機(jī)數(shù)發(fā)生器在某個(gè)閉區(qū)間產(chǎn)生的隨機(jī)數(shù)滿足均勻分布，則發(fā)生這種最壞情況概率為

另一種最壞情況是隨機(jī)數(shù)發(fā)生器在 j次循環(huán)時(shí)選擇第 n-j+1個(gè)元素，j=1，2，…，n，這種最壞情況僅僅是理論上存在，實(shí)際中幾乎不可能發(fā)生。

2.2 最好時(shí)間復(fù)雜度

算法的最好時(shí)間復(fù)雜度為C(n)=n，若隨機(jī)數(shù)發(fā)生器第1次隨機(jī)選擇的元素恰好是待查找的第k小元素，則經(jīng)過(guò)算法的第3步共n次元素比較，將元素分為三個(gè)部分，再經(jīng)過(guò)第4步的判斷，即查找成功。因此最好時(shí)間復(fù)雜度為C(n)=n，發(fā)生這種最好情況的概率為1/n。

2.3 期望時(shí)間復(fù)雜度

在本文中，運(yùn)用概率論分析方法，通過(guò)理論分析和實(shí)驗(yàn)研究?jī)煞N途徑，從更小的信息粒度意義上深入研究這個(gè)隨機(jī)算法，給出其期望復(fù)雜度的三種情況，即最好情況、最壞情況和平均情況，分別得到最好情況的緊下界、最壞情況的一個(gè)比較緊致的上界，更重要的是，得到了平均情況的一個(gè)數(shù)學(xué)緊上界，作為本文一個(gè)重要理論研究成果。

進(jìn)行如下理論分析：

設(shè)有數(shù)組 A[i…j]，取定 k∈[i，j]作為分割點(diǎn)，記Xj-i+1表示經(jīng)過(guò)這一次分割所得到的余下的數(shù)組長(zhǎng)度（條件）期望值。則分割后，余下的數(shù)組為如下序列之一：A[i…k-1]，A[k]，A[k+1…j]。設(shè)分割點(diǎn)k∈[i，j]滿足均勻分布，則落在以上3個(gè)區(qū)間內(nèi)的概率與區(qū)間長(zhǎng)度成正比，即分別為：（k-i）/（j-i+1），1/（j-i+1），（j-k）/（j-i+1）。

則將 A[i…j]一次分割后，余下數(shù)組長(zhǎng)度（條件）期望值是

這說(shuō)明在計(jì)算期望時(shí)間復(fù)雜度時(shí)，一次遞歸可以去掉至少1/3的元素，剩余元素的個(gè)數(shù)期望值不超過(guò)上次元素個(gè)數(shù)的2/3。于是，可得：

其中 +n表示經(jīng)過(guò)n次比較。易知當(dāng)n=1時(shí)，C(1)=1。

由以上的證明可知：隨機(jī)化的快速選擇算法的期望時(shí)間復(fù)雜度小于3n。

3 研究目標(biāo)和實(shí)驗(yàn)設(shè)計(jì)

3.1 研究平臺(tái)

本文使用C++語(yǔ)言作為編程語(yǔ)言，采用Matlab進(jìn)行數(shù)據(jù)處理編程。

3.2 研究目標(biāo)

由于隨機(jī)化選擇算法中采用了隨機(jī)算法，對(duì)于同一個(gè)k，當(dāng)隨機(jī)算法生成的基準(zhǔn)元素不同時(shí)，所得到的結(jié)果相差很大，因此在計(jì)算相應(yīng)時(shí)間復(fù)雜度時(shí)，這是首先要解決的一個(gè)問(wèn)題?？紤]k變化時(shí)的情況，從更小信息粒度意義上深入研究這個(gè)隨機(jī)算法，給出其期望復(fù)雜度的最好情況、最壞情況和平均情況，進(jìn)而期望找到算法時(shí)間復(fù)雜度的一個(gè)比較緊致的上界，最好是其緊上界，作為對(duì)該算法復(fù)雜度的一個(gè)最佳描述。

3.3 實(shí)驗(yàn)設(shè)計(jì)

1）隨機(jī)生成n個(gè)數(shù)（先取n=100），for k=1 to n，執(zhí)行算法，記錄每次的比較次數(shù)C（n，k），分析C（n，k）變化趨勢(shì)；

2）重復(fù)步驟1），對(duì)比觀察得到的實(shí)驗(yàn)數(shù)據(jù)，分析其中規(guī)律；

3）生成n（先取n=100）個(gè)元素的數(shù)組A［i］，其中A［i］=i，構(gòu)成升序數(shù)組，for k=1 to n，記錄每次的比較次數(shù)C（n，k），分析C（n，k）的變化趨勢(shì)；

4）分別取 n=512，1024，2048，4096，然后重復(fù)步驟3），觀察一系列圖，發(fā)現(xiàn)其中變化規(guī)律；

5）重復(fù)步驟3）和步驟4），但是其中的A［i］=n-i+1，構(gòu)成降序數(shù)組，其它不變，觀察其變化規(guī)律；

6）分別取n=512，1024，2048，4096，對(duì)于每個(gè)n分別采用3組隨機(jī)生成的數(shù)組，一組升序數(shù)組A［i］=i，一組降序數(shù)組A［i］=n-i+1作為輸入數(shù)組，for k=1 to n，記錄每次的比較次數(shù)；

7）分別取 n=128，256，512，1024，2048，4096，8192，隨機(jī)生成n個(gè)數(shù)，for k=1 to n，記錄每個(gè)n值下的最大時(shí)間復(fù)雜度和時(shí)間復(fù)雜度的中位數(shù)；

8）重復(fù)有限次實(shí)驗(yàn)7，獲得每個(gè)n值下的多組最大時(shí)間復(fù)雜度和時(shí)間復(fù)雜度的中位數(shù)。對(duì)于每個(gè)n，保留其中最大時(shí)間復(fù)雜度中的最大值以及時(shí)間復(fù)雜度的中位數(shù)；

9）取n=1000，隨機(jī)生成n個(gè)數(shù)，分別取子序列長(zhǎng)度為5，7，9，13，17，for k=1 to n記錄每次的比較次數(shù)C（n，k），保留其中每個(gè)子序列長(zhǎng)度下最大的C（n，k）；

10） 分 別 取 n=5000，10000，20000，50000，100000，200000，重復(fù)步驟9）；

11）取n=100，隨機(jī)生成n個(gè)數(shù)，for k=1 to n，每次確定n和k值以后，分別運(yùn)行程序1，10，100，記錄每組運(yùn)行的統(tǒng)計(jì)平均值與隨機(jī)實(shí)驗(yàn)次數(shù)之間的變化規(guī)律；

12）在步驟11）的數(shù)據(jù)分析基礎(chǔ)上，取n=2，3 to 100，每次隨機(jī)生成n個(gè)數(shù)，for k=1 to n，對(duì)于每個(gè)k運(yùn)行程序次，記錄每次比較次數(shù)的統(tǒng)計(jì)平均值 ，觀察記錄 關(guān)于參數(shù)k的最小、最大與平均值情況，作為當(dāng)前輸入規(guī)模為n時(shí)的最好、最壞與平均時(shí)間復(fù)雜度的度量。

4 實(shí)驗(yàn)結(jié)果分析

4.1 時(shí)間復(fù)雜度的研究

隨機(jī)化的選擇算法中因?yàn)殡S機(jī)算法的存在，導(dǎo)致該算法每次執(zhí)行所得到的比較次數(shù)相差較大。因此取m次重復(fù)實(shí)驗(yàn)結(jié)果的平均值作為其時(shí)間復(fù)雜度。為了驗(yàn)證這個(gè)m值取多大合適，我們進(jìn)行了如下實(shí)驗(yàn)：取數(shù)組n的大小為100，即n=100，然后對(duì)于每個(gè)k，分別進(jìn)行1，10，100，1000，10000次的重復(fù)隨機(jī)實(shí)驗(yàn)，得到其每次實(shí)驗(yàn)的時(shí)間復(fù)雜度C(n，k)，然后分別取其平均值 。以為縱坐標(biāo)，k為橫坐標(biāo)得到圖1。

圖1 隨機(jī)實(shí)驗(yàn)次數(shù)與相應(yīng)結(jié)果的變化圖

正如圖1中所看到的，當(dāng)隨機(jī)實(shí)驗(yàn)重復(fù)次數(shù)為1次時(shí)，所得到的曲線是雜亂無(wú)章的，如波浪般。當(dāng)隨機(jī)實(shí)驗(yàn)重復(fù)次數(shù)為10次時(shí)，所得曲線仍是上下起伏的，但是起伏程度明顯低于隨機(jī)實(shí)驗(yàn)重復(fù)次數(shù)為1次時(shí)的曲線。當(dāng)隨機(jī)實(shí)驗(yàn)次數(shù)為100次時(shí)，所得曲線已經(jīng)趨向于平緩，但是也有一些漲落。當(dāng)隨機(jī)實(shí)驗(yàn)次數(shù)為1000次，10000次時(shí)，實(shí)驗(yàn)所得曲線已經(jīng)非常的平滑，兩者基本相同。換言之，平均值逐漸收斂。

4.2 時(shí)間復(fù)雜度的平均值

圖2 時(shí)間復(fù)雜度平均值曲線圖

從圖2中可以看出，時(shí)間復(fù)雜度平均值的圖象在n較小時(shí)有一定的彎曲，但是隨著n的增大，圖象就開(kāi)始呈現(xiàn)為線性變化，而且一直在C(n)=3n的下方，實(shí)驗(yàn)數(shù)據(jù)完全符合我們的理論模型。換言之，我們通過(guò)理論推導(dǎo)并進(jìn)行實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證的方式，得到了該算法期望時(shí)間復(fù)雜度函數(shù)的緊上界3n。

4.3 時(shí)間復(fù)雜度的最大值

圖3 時(shí)間復(fù)雜度最大值曲線圖

從圖3中可以看出時(shí)間復(fù)雜度最大值的擬合曲線在C(n)=3.3n的下方，但是，隨著n的增大，其最大值曲線是否會(huì)發(fā)生變化。為了研究其具體情況，我們又進(jìn)行了更多的實(shí)驗(yàn)，將問(wèn)題規(guī)模n擴(kuò)大，再重復(fù)上面的實(shí)驗(yàn)，然后繪制相應(yīng)的最大值曲線圖，得到圖4。

圖4 時(shí)間復(fù)雜度最大值的補(bǔ)充曲線圖

從圖4中可以看到，當(dāng)n在250～350之間的某個(gè)值時(shí)，最大值的擬合曲線超過(guò)了C(n)=3.3n，而一直在C(n)=3.4n的下方，并且非常靠近C(n)=3.4n。為了研究該最大值是否還會(huì)有變化，我們又將n值進(jìn)行擴(kuò)大，做了一些針對(duì)性的實(shí)驗(yàn)，但是該最大值的擬合曲線沒(méi)有更多變化，即期望時(shí)間復(fù)雜度的上界（最大值）小于3.4n，至于理論上的分析，還有待于進(jìn)一步的研究。

4.4 時(shí)間復(fù)雜度的最小值

圖5 時(shí)間復(fù)雜度最小值曲線圖

從圖5中觀察可知，時(shí)間復(fù)雜度最小值的擬合曲線圖一直位于C(n)=n的上方，但是和C(n)=1.1*n在n很小時(shí)會(huì)有交點(diǎn)。因?yàn)楫?dāng)n=1時(shí)，C（1）=1，又因?yàn)槊總€(gè)元素至少被檢查一次，C(n)≥n，所以隨機(jī)化的選擇算法所期望的元素比較次數(shù)的下界為n。

5 結(jié)語(yǔ)

經(jīng)過(guò)上面的實(shí)踐研究，我們對(duì)隨機(jī)化的快速選擇算法有了更好的認(rèn)識(shí)。通過(guò)實(shí)踐獲得相應(yīng)的實(shí)驗(yàn)數(shù)據(jù)，對(duì)大量實(shí)驗(yàn)數(shù)據(jù)進(jìn)行匯總處理，然后將其繪制成曲線，通過(guò)分析實(shí)驗(yàn)數(shù)據(jù)和觀察相應(yīng)的曲線，發(fā)現(xiàn)了一些規(guī)律。由于該算法中存在隨機(jī)函數(shù)，因此其不確定性相對(duì)較大，即實(shí)驗(yàn)結(jié)果會(huì)有較大波動(dòng)，但是通過(guò)大量的隨機(jī)實(shí)驗(yàn)，發(fā)現(xiàn)多次隨機(jī)實(shí)驗(yàn)平均值會(huì)隨著實(shí)驗(yàn)次數(shù)的增多而逐漸收斂，從而降低實(shí)驗(yàn)誤差，為實(shí)驗(yàn)成功進(jìn)行提供了基礎(chǔ)保證。當(dāng)n處于一定的范圍內(nèi)，計(jì)算得到了該算法時(shí)間復(fù)雜度數(shù)據(jù)，并在此基礎(chǔ)上，分析了其平均值、最大值以及最小值。綜上得到如下結(jié)論：ffffbc

［1］鄒亮，徐建閩，朱玲湘.A～*算法改進(jìn)及其在動(dòng)態(tài)最短路徑問(wèn)題中的應(yīng)用［J］.深圳大學(xué)學(xué)報(bào)，2007，24（1）：32-36.

ZOU Liang，XU Jianmin，ZHU Xiangling.Improvement of A*Algorithm and its Application in Shortest Path Problem in Dynamic Networks［J］.Journal of Shenzhen University Science and Engineering，2007，24（1）：32-36.

［2］段莉瓊，朱建軍，王慶社.改進(jìn)的最短路徑搜索A*算法的高效實(shí)現(xiàn)［J］.海洋測(cè)繪，2004，24（5）：20-22.

DUAN Liqiong，ZHU Jianjun，WANG Qingshe.Fast Real?ization of the Improved A*Algorithm for Shortest Route［J］.Hydrographic Surveying and Charting，2004，24（5）：20-22.

［3］樊莉，孫繼銀，王勇.人工智能中A～*算法的應(yīng)用及編程［J］.微機(jī)發(fā)展，2003，13（5）：33-35.

FAN Li，SUN Jiyin，WANG Yong.Application and Pro?gramming of A*Algorithm in AI［J］.Microcomputer De?velopment，2003，13（5）：33-35.

［4］夏永鋒，曹元大.啟發(fā)式搜索算法的面向?qū)ο笤O(shè)計(jì)實(shí)現(xiàn)［J］.微機(jī)發(fā)展，2005，15（7）：11-13.

XIA Yongfeng，CAO Yuanda.Implementation and Design Heuristic Searching Algorithm by Object-Oriented Method［J］.Microcomputer Development，2005，15（7）：11-13.

［5］周鵬.一種改進(jìn)的隨機(jī)選擇算法［J］.三峽大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，29（5）：470-473.

ZHOU Peng.An Improved Randomized Selection Algo?rithm［J］.Journal of China Three Gorges University（Natu?ral Sciences），2007，29（5）：470-473.

［6］賀紅，馬紹漢.隨機(jī)算法的一般性原理［J］.計(jì)算機(jī)科學(xué)，2002，29（1）：90-92.

HE Hong，MA Shaohan.The General Principles of Ran?domized Algorithms［J］.Computer Science，2002，29（1）：90-92.

［7］徐云，陳國(guó)良，張強(qiáng)峰，等.隨機(jī)算法異步并行化的效率分析［J］.軟件學(xué)報(bào)，2003，14（5）：871-876.

XU Yun，CHEN Guoliang，ZHANG Qiangfeng，et al.Effi?ciency Analysis of Asynchronic Parallelization of Random?ized Algorithms［J］.Journal of Software，2003，14（5）：871-876.

［8］Gu J，Purdom PW，F(xiàn)ranco J，Wah BW.Algorithms for satisfiability（SAT） problem：A survey［J］.DIMACS Se?ries in Discrete Mathematics and Theoretical Computer Science，American Mathematical Society，1997（35）：19-151.

［9］Gomes C，Selman B，Kautz H.Boosting combinatorial search through randomization［M］.Proceedings of the AAAI-98.Madison：AAAI Press，1998：430-437.

［10］Gomes C，Selman B，Crato N，Kautz H.Heavy-Tailed phenomena in satisfiability and constraint satisfaction problems［J］.Journal of Automated Reasoning，2000（24）：67-71.