APP下载

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

2014-08-25胡圣荣

关键词:排序

胡圣荣

(华南农业大学 工程学院,广东 广州 510642)

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

胡圣荣

(华南农业大学 工程学院,广东 广州 510642)

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

排序;希尔排序;算法;拟合;拟合不变性

0 引言

自从1959年D.L.Shell提出希尔排序算法[1]以来,该类算法的理论分析一直都没有很好解决[2],有关研究大致有三方面:①理论上下限估计,如文献[3];②数值估计,如文献[4-6];③最优增量研究,如文献[7].一般地,对具体的增量序列,除少数特殊情况外都没有理论结果,通常进行数值估计,即采用大量随机输入,对输出结果平均后进行数据拟合.作者发现,这些数值估计,纯粹也只能看做已有数据的一个外在的经验公式,并不代表数据内部的真实变化规律.比如,增加新的数据点,特别是规模更大的新数据点后,新的拟合结果(公式中的有关系数等)一般会有明显变动,而实际的平均复杂性应该是规模的一个确定不变的函数关系.

本文试图从实验数……

登录APP查看全文

猜你喜欢

排序
排排序
作者简介
作者简介
作者简介(按文章先后排序)
恐怖排序
律句填空排序题的备考策略
节日排序
刻舟求剑
作者简介(按文章先后排序)
2010年