隨機化快速選擇算法時間復雜度研究?

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

（東北石油大學計算機與信息技術學院 大慶 163318）

1 引言

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

2 算法復雜度分析

2.1 最壞時間復雜度

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

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

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

2.2 最好時間復雜度

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

2.3 期望時間復雜度

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

進行如下理論分析：

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

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

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

其中 +n表示經過n次比較。易知當n=1時，C(1)=1。

由以上的證明可知：隨機化的快速選擇算法的期望時間復雜度小于3n。

3 研究目標和實驗設計

3.1 研究平臺

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

3.2 研究目標

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

3.3 實驗設計

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

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

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

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

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

6）分別取n=512，1024，2048，4096，對于每個n分別采用3組隨機生成的數(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，隨機生成n個數(shù)，for k=1 to n，記錄每個n值下的最大時間復雜度和時間復雜度的中位數(shù)；

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

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

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

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

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

4 實驗結果分析

4.1 時間復雜度的研究

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

圖1 隨機實驗次數(shù)與相應結果的變化圖

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

4.2 時間復雜度的平均值

圖2 時間復雜度平均值曲線圖

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

4.3 時間復雜度的最大值

圖3 時間復雜度最大值曲線圖

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

圖4 時間復雜度最大值的補充曲線圖

從圖4中可以看到，當n在250～350之間的某個值時，最大值的擬合曲線超過了C(n)=3.3n，而一直在C(n)=3.4n的下方，并且非?？拷麮(n)=3.4n。為了研究該最大值是否還會有變化，我們又將n值進行擴大，做了一些針對性的實驗，但是該最大值的擬合曲線沒有更多變化，即期望時間復雜度的上界（最大值）小于3.4n，至于理論上的分析，還有待于進一步的研究。

4.4 時間復雜度的最小值

圖5 時間復雜度最小值曲線圖

從圖5中觀察可知，時間復雜度最小值的擬合曲線圖一直位于C(n)=n的上方，但是和C(n)=1.1*n在n很小時會有交點。因為當n=1時，C（1）=1，又因為每個元素至少被檢查一次，C(n)≥n，所以隨機化的選擇算法所期望的元素比較次數(shù)的下界為n。

5 結語

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

［1］鄒亮，徐建閩，朱玲湘.A～*算法改進及其在動態(tài)最短路徑問題中的應用［J］.深圳大學學報，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］段莉瓊，朱建軍，王慶社.改進的最短路徑搜索A*算法的高效實現(xiàn)［J］.海洋測繪，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～*算法的應用及編程［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ā)式搜索算法的面向對象設計實現(xiàn)［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］.三峽大學學報（自然科學版），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］.計算機科學，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］徐云，陳國良，張強峰，等.隨機算法異步并行化的效率分析［J］.軟件學報，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.