为什么在一般情况下,链排序为O(n sqrt n)？

Question

我发现链排序非常有吸引力,可以在常量空间中对单个链表进行排序,因为它比插入排序更快.

我明白为什么它是O(n)最好的情况(列表已经排序),O(n^2)在最坏的情况下(列表反向排序).但为什么O(n sqrt n)在一般情况下呢？如果算法不是基于二分法并且具有多项式最佳情况和最坏情况性能,那么平均情况就是O(n^m),m最佳情况和最差情况的指数(m = (1 + 2) / 2 = 3/2,O(n sqrt n) = O(n^(3/2)))的算术平均值在哪里？

Answer 1

对链排序的原始参考是http://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 ...据此，它是O(n^2)。链排序是作为 J 排序的一个组成部分提出的，它声称其时间复杂度为 O(n lg n)。平均复杂度为 O(n^2) 是有道理的，因为在随机数据中，一半的链长度为 1，并且 O((n/2)^2) = O(n^2)。