希尔排序效率的真实性拟合尝试——Sedgewick增量序列(1982)

Attempt at Credible Empirical Study of Shellsort——Sedgewick's Increment Sequence in 1982

为了对复杂性未知的希尔排序算法进行合理、可信的数值估计，提出拟合不变性结合拟合准确性和显著性的拟合思想和方法，并对采用Sedgewick增量序列4倡22i＋3倡2i＋1的希尔排序算法的平均比较次数进行了数值估计，从cnαlnβ（ n）形式开始，在规模为104～108的测试数据的不同区段分别拟合，根据拟合参数的变动特点，进行合理推断并再次拟合及验证，从而逐步分离和确定出α＝1， c＝1，β＝1．41，最终获得了对各区段拟合几乎不变的结果nln1．41（ n）．拟合方法本身的正确性用已知结果的排序数据进行了验证．

In order to estimate unknown complexity of Shellsort reasonably and credibly ,this paper sug-gested 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 ob-tained about to nln1.41（n）,which was originated from cnαlnβ（n）,with parameter inferring from its appear-ance in different data segments among size of 104 to 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 .