希尔排序增量序列

今天数据结构讲了希尔排序。

其中说到增量序列。

目前主流的增量序列有2个:

  • Hibbard增量序列:D(k)=2^k-1,这使得相邻元素互质。

 

其平均时间复杂度猜想为O(N^(5/4)),至今未能证明。

最坏情况的时间复杂度已被证明为Θ(N^(3/2)),注意这里不是大O,是Θ,即不是上界,而是真真正正的与N的1.5次方成正比。

  • Sedgewick增量序列:9*4^i-9*2^i+1或4^i-3*2^i+1,即{1,5,19,...}。

其平均时间复杂度猜想为O(N^(7/6)),最坏时间复杂度为O(N^(4/3)),至今均未能证明。