我发现strand sort非常有吸引力，可以在常量空间中对单个链表进行排序，因为它比例如插入排序要快得多 .
我知道为什么它是 O(n) 在最好的情况下（列表已经排序）和 O(n^2) 在最坏的情况下（列表反向排序） . 但为什么 O(n sqrt n) 在平均情况下呢？如果算法不是基于二分法并且具有多项式最佳情况和最差情况性能，那么平均情况是 O(n^m) ，其中 m 是最佳情况的算术平均值's and worst-case' s指数（ m = (1 + 2) / 2 = 3/2 ， O(n sqrt n) = O(n^(3/2)) ）？
2 回答
对Strand排序的原始引用是http://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 ...根据它，它是O（n ^ 2） . Strand sort作为J sort的一个组件呈现，它声称是O（n lg n） . 平均复杂度为O（n ^ 2）是有意义的，因为在随机数据中，一半的线将具有长度1，并且O（（n / 2）^ 2）= O（n ^ 2） .
在您链接到的Wikipedia页面上，平均案例性能为O（n lg n），并引用此Stack Overflow页面 . 这很奇怪，因为在这个页面上没有任何地方可以这么说 .
无论如何，为了进一步说明Ulrich的观点，平均案例分析很复杂，因为它必须考虑数据的平均表示方式，这不是微不足道的 .
From Wikipedia: