algorithm - 为什么在平均情况下链排序 O(n sqrt n)？

Question

我找到了 strand sort对常量空间中的单向链表进行排序非常有吸引力，因为它比例如插入排序快得多。

我明白为什么它在最好的情况下是 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

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