希爾排序效率的真實性擬合嘗試
——Sedgewick增量序列(1982)

胡圣榮

(華南農(nóng)業(yè)大學 工程學院，廣東 廣州 510642)

希爾排序效率的真實性擬合嘗試
——Sedgewick增量序列(1982)

胡圣榮

(華南農(nóng)業(yè)大學 工程學院，廣東 廣州 510642)

為了對復雜性未知的希爾排序算法進行合理、可信的數(shù)值估計，提出擬合不變性結合擬合準確性和顯著性的擬合思想和方法，并對采用Sedgewick增量序列4*22i+3*2i+1的希爾排序算法的平均比較次數(shù)進行了數(shù)值估計，從cnαlnβ(n)形式開始，在規(guī)模為104～108的測試數(shù)據(jù)的不同區(qū)段分別擬合，根據(jù)擬合參數(shù)的變動特點，進行合理推斷并再次擬合及驗證，從而逐步分離和確定出α=1,c=1,β=1.41，最終獲得了對各區(qū)段擬合幾乎不變的結果nln1.41(n).擬合方法本身的正確性用已知結果的排序數(shù)據(jù)進行了驗證.

排序；希爾排序；算法；擬合；擬合不變性

0 引言

自從1959年D.L.Shell提出希爾排序算法[1]以來，該類算法的理論分析一直都沒有很好解決[2]，有關研究大致有三方面：①理論上下限估計，如文獻[3]；②數(shù)值估計，如文獻[4-6]；③最優(yōu)增量研究，如文獻[7].一般地，對具體的增量序列，除少數(shù)特殊情況外都沒有理論結果，通常進行數(shù)值估計，即采用大量隨機輸入，對輸出結果平均后進行數(shù)據(jù)擬合.作者發(fā)現(xiàn)，這些數(shù)值估計，純粹也只能看做已有數(shù)據(jù)的一個外在的經(jīng)驗公式，并不代表數(shù)據(jù)內(nèi)部的真實變化規(guī)律.比如，增加新的數(shù)據(jù)點，特別是規(guī)模更大的新數(shù)據(jù)點后，新的擬合結果(公式中的有關系數(shù)等)一般會有明顯變動，而實際的平均復雜性應該是規(guī)模的一個確定不變的函數(shù)關系.

本文試圖從實驗數(shù)據(jù)中得到比較可信的有可能反映真實規(guī)律的擬合結果，介紹了擬合原理和方法，對Sedgewick增量序列(1982)的擬合結果具有很好的擬合不變性.

1 擬合思想與方法

1.1 擬合準確性

所見文獻一般是對測試數(shù)據(jù)，按一定的擬合式進行一次性的擬合，主要考察擬合的準確性.如對采用Hibbard序列2t-1，即1, 3, 7, 15, 31, …和Knuth序列(3t-1)/2，即1,4,13,40,121,…的希爾排序，Knuth采用cnα形式擬合，M.A.Weiss采用c1n5/4+c2n+c3n3/4+c4n2/4+c5n1/4+c6形式，后者比前者準確[5].Cotta用an2+bn和anb都能很好擬合Knuth序列[6].顯然，采用不同的擬合式必將得到不同的結果，其中總有可能找到比當前更準確的，特別地，采用插值多項式可通過所有樣點，但這顯然并不意味著“最準確”.

表1 快速排序的平均比較次數(shù) /106

那么，對同一數(shù)據(jù)的多種擬合，如何判斷誰更“真實”呢？作者在文獻[8]中提出過一個觀點：擬合準確性不一定代表真實性.以快速排序為例，表1為某快速排序算法(快速排序有多種實現(xiàn))對1000組隨機序列排序后的平均結果.

對此數(shù)據(jù)，發(fā)現(xiàn)很多擬合式都能很好地吻合，如y=cnα、cnαlnβ(n)ln[ln(n)]、cnαlnβ(n)、cnln(n)、cnαln(n)、cnln(n)等(轉換為適當形式后進行線性擬合).擬合后分別求出y-yi，依次為149.91、0.612 05、0.632 00、14.752、24.584、8.959 1，其中形式較復雜的cnαlnβ(n)ln[ln(n)]擬合誤差最小，而較接近理論結果的cnln(n)并不是很好.所以擬合“準確”不一定真實，反之，擬合不太精確的曲線，未必不真實.當然，準確性明顯較差的形式cnα優(yōu)先值得懷疑.

1.2 擬合顯著性

另一方面，從統(tǒng)計學觀點看，擬合還有一個顯著性的問題[9]，一般考察擬合參數(shù)的t值、P值和總體結果的R2、AdjustedR2、F值、SignificanceF等，其中t值和F值越大越好，P值和SignificanceF越小越好，R2越接近1越好.

這里進一步指出：擬合顯著性也不一定代表真實性.比如SignificanceF，上面6個擬合的結果分別為6.529 8E-16、7.046 8E-21、3.230 2E-25、1.882 8E-15、3.336 1E-21、8.389 4E-22，它們都很顯著，其中最顯著的是cnαlnβ(n)(此時α=0.992 20、β=1.194 8)，但它并不比cnlnβ(n)(此時β=1.0067)更真實，因為快速排序的理論結果為O(nln(n)).當然，擬合參數(shù)明顯不顯著的cnαlnβ(n)ln[ln(n)](其中l(wèi)n(c)、的P值為0.148 79和0.641 23較大，而其它幾個擬合式的參數(shù)P值至少在10-7以下)優(yōu)先值得懷疑(增加更多數(shù)據(jù)點擬合會顯著些).

1.3 擬合穩(wěn)定性

為了判斷擬合式的真實性，作者在文獻[8]提出擬合不變性的思想，即若該擬合式是真實的，則它在數(shù)據(jù)點的各子區(qū)間應該有幾乎相同的擬合結果.這是必要條件，但顯然沒有該特點的擬合，真實性值得懷疑.

為了獲得擬合不變的結果，需要將數(shù)據(jù)分段，再分別擬合.根據(jù)各段上擬合參數(shù)表現(xiàn)出的特點，進行合理推斷以去除數(shù)據(jù)的“毛刺”(波動)，得到簡化形式，然后再次擬合并驗證(參數(shù)是否穩(wěn)定、擬合是否顯著等).這個過程可能要反復多次，具體實施時還可結合擬合準確性和顯著性進行.按此思想，文獻[8]對采用Hibbard序列和Knuth序列的希爾排序，擬合結果分別為cn1.26ln-0.5(n)和cn1.25ln-0.5(n)，特別地，當規(guī)模n不是很大時，近似為(n1.26)和(n1.25)，這便是Knuth和M.A.Weiss的結果[5].

表2 希爾排序的平均比較次數(shù) /106

表3 區(qū)間分段情況

2 擬合過程

Sedgewick在1982年設計了一個增量序列4*22i+3*2i+1(i≥0)，即1, 8, 23, 77, 281, …，效果優(yōu)于Hibbard序列和Knuth序列，上界為O(n4/3)[2]，但具體平均情況未知.這里取該增量序列進行希爾排序.因測試規(guī)模大，測試序列長，為避免序列數(shù)據(jù)重復(C/C++系統(tǒng)的隨機函數(shù)rand()只生成0～327 67的隨機數(shù))，隨機序列的生成采用文獻[10]的長周期隨機函數(shù)，但與之不同的是，這里不通過改變種子來獲得不同序列，而是在長周期隨機序列中依次截取所需長度的子序列；測試組數(shù)也自動選?。鹤疃?06組，以當前規(guī)模總排序時間不超過1 min為準(該時間根據(jù)硬件條件設置)但最少10組.測試結果見表2.

區(qū)間分段如下：分別從低到高分4段、2段、1段，見表3所示.其中區(qū)段A、B、C、D可考察規(guī)模增加時擬合參數(shù)是否穩(wěn)定以及變化趨勢，其它幾段可考察數(shù)據(jù)點增加時擬合參數(shù)是否穩(wěn)定以及變化趨勢.

表4 分段擬合及參數(shù)的確定(表2數(shù)據(jù))

下面對各段分別擬合.由于增量序列有按幾何級數(shù)變化的特點或趨勢，根據(jù)文獻[8]的思想，擬合形式仍取為cnαlnβ(n)，擬合結果見表4中的基本形式.

從表4基本形式的結果看到，各區(qū)段上參數(shù)ln(c)變動較大、β次之，而α較穩(wěn)定，基本在1上下，于是推測α=1，重新擬合，結果見表4中α=1部分.這時參數(shù)β也較穩(wěn)定了，而ln(c)基本在0附近變動(即c接近1)，再次推測c=1后重新擬合，結果見表4最后一行.這時參數(shù)β非常穩(wěn)定，約1.408～1.409.

以上區(qū)間分段似乎較特殊，實際上其它分段結果都類似，如改變段的開始、改變段的長度等(數(shù)據(jù)略).另外，對數(shù)據(jù)序列細化，如1，1.778，3.162，5.623，10，…，以及其它數(shù)據(jù)序列，如1，2，4，6，8，10，…，結果也類似(數(shù)據(jù)略，故本文表2僅取了少量數(shù)據(jù)).

至于擬合的顯著性，表4涉及的3個擬合式(即cnαlnβ(n)、cnlnβ(n)、nlnβ(n))都很顯著，如對全段擬合的SignificanceF分別為3.075 7E-20、2.100 4E-15、5.069 4E-23.

綜合以上分析，表2數(shù)據(jù)的最終擬合結果為y=nln1.41(n).

表5 直接插入排序的平均比較次數(shù) /106

表6 分段擬合及參數(shù)的確定(表5數(shù)據(jù))

3 擬合方法的驗證

下面用已知結果的數(shù)據(jù)來驗證一下上述擬合方法.對表1快速排序的不變性擬合略為繁瑣一些，它需要兩項形式y(tǒng)=cnαlnβ(n)+n才能穩(wěn)定，這種情況擬另文介紹.作者發(fā)現(xiàn)，簡單排序都能一項穩(wěn)定擬合.以直接插入排序為例，數(shù)據(jù)見表5.該排序效率低，規(guī)模大時排序時間太長，故測試時所取數(shù)據(jù)組數(shù)依次遞減：規(guī)模量級為102、103、104、105、106時分別取10 000、1 000、1 000、100、1組.仍從cnαlnβ(n)形式開始，擬合結果見表6.

具體過程是，先由基本形式的擬合結果估計α=2；令α=2重新擬合后估計β=0；最后令α=2,β=0再擬合，結果參數(shù)c非常穩(wěn)定，約0.250最后結果為0.250 n2，而理論結果是n(n-1)/40.25 n2.這個過程與表4幾乎一樣.

4 結論

希爾排序的平均復雜性是規(guī)模n的某個確定函數(shù)，如果擬合結果是真實的，則它在各數(shù)據(jù)區(qū)段上應該有幾乎相同的擬合結果.擬合不變性思想對判斷或推測擬合真實性提供了一種值得嘗試的可行的方法.

對采用Sedgewick增量序列4*22i+3*2i+1的希爾排序算法，本文的擬合結果nln1.41(n)具有很好的擬合不變性和顯著性，雖仍屬經(jīng)驗估計，但很可能比其它結果更接近真實.

下一步的工作是探討合適的其它擬合式及組合擬合式，因為作者的工作表明擬合式cnαln(n)對其它幾個測試序列不像本文這樣穩(wěn)定(即使增量類似，但Pratt序列[2-3]除外，對其擬合時很穩(wěn)定并能得到理論值cnln2(n)[3]，數(shù)據(jù)略).當然，也可能出現(xiàn)幾個擬合式都較穩(wěn)定如何分辨的問題.另一個要做的工作是對穩(wěn)定擬合結果的理論證明.

[1]ShellDL.Ahigh-speedsortingprocedure[J].CommunicationsoftheACM,1959,2(7):30-32.

[2]SedgewickR.AnalysisofShellsortandRelatedAlgorithms[J].EuropeanSymposiumonAlgorithms,1996:1-11.

[3]JiangT,LiM,VitányiP.Alowerboundontheaverage-casecomplexityofShellsort[J].JACM,2000,47(5):905-911.

[4]SandersP,FleischerR.Asymptoticcomplexityfromexperiments?Acasestudyforrandomizedalgorithms[C]//AlgorithmEngineering,SpringerBerlinHeidelberg,2001:135-146.

[5]WeissMA.ShortNoteEmpiricalstudyoftheexpectedrunningtimeofShellsort[J].TheComputerJournal,1991,34(1):88-91.

[6]CottaC,MoscatoP.Amixedevolutionary-statisticalanalysisofanalgorithm'scomplexity[J].AppliedMathematicsLetters,2003,16(1):41-47.

[7]CiuraM.Bestincrementsfortheaveragecaseofshellsort[J].Lecturenotesincomputerscience,2001:106-117.

[8]胡圣榮.關于排序效率的數(shù)值估計[J].廣州城市職業(yè)學院學報,2008,2(1):61-64.

[9]何曉群，劉文卿.應用回歸分析[M].北京：中國人民大學出版社，2001.

[10]胡圣榮.關于排序算法的隨機輸入序列[J].武漢理工大學學報,2006,28(9):105-107.

責任編輯：時凌

AttemptatCredibleEmpiricalStudyofShellsort——Sedgewick′s Increment Sequence in 1982

HU Shengrong

(College of Engineering,South China Agricultural University,Guangzhou 510642,China)

In order to estimate unknown complexity of Shellsort reasonably and credibly,this paper suggested combination of fitting invariability with fitting precision and significance, and accordingly the average number of comparisons of Shellsort with Sedgewick′s increment sequence 4*22i+3*2i+1 was obtained about tonln1.41(n),which was originated fromcnαlnβ(n),with parameter inferring from its appearance in different data segments among size of 104to 108,refitting and validating , the values ofα=1,c=1,β=1.41 were determined progressively. The correctness of the fitting method proposed was verified by data with known complexity.

sort; shellsort; algorithm;fit;fitting invariability

2014-05-26.

胡圣榮(1967- )，男，博士，教授，主要從事計算機數(shù)值計算相關問題研究.

TP311.12

A

1008-8423(2014)02-0218-04