为什么链排序在平均情况下是 O(n sqrt n) ？
我发现链排序对于在恒定空间中对单链表进行排序非常有吸引力，因为它比例如插入排序。
我明白为什么在最好的情况下是 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) ））？
I found strand sort very appealing to sort singly linked lists in constant space, because it is much faster than for example insertion sort.
I see why it is O(n) in the best case (the list is already sorted) and O(n^2) in the worst case (the list is reversely sorted). But why O(n sqrt n) in the average case? If algorithm is not based on bisection and has polynomial best-case and worst-case performance, is the average case just O(n^m), where m is arithmetic mean of best-case's and worst-case's exponents (m = (1 + 2) / 2 = 3/2, O(n sqrt n) = O(n^(3/2)))?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对链排序的原始参考为 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)。
The original reference to Strand sort is http://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 ... according to that, it is O(n^2). Strand sort was presented as a component of J sort, which it claims is O(n lg n). That the average complexity is O(n^2) makes sense since, in random data, half the strands will be of length 1, and O((n/2)^2) = O(n^2).
在您链接到的维基百科页面上，平均案例性能为 O(n lg n) 并引用了此 Stack Overflow 页面。这很奇怪，因为这个页面上没有任何地方提到这一点。
无论如何，为了进一步说明乌尔里希所说的，平均情况分析很复杂，因为它必须考虑数据的平均表示方式，这并不是微不足道的。
来自维基百科：
On the Wikipedia page that you linked to, the average case performance is O(n lg n) with a citation to this Stack Overflow page. Which is weird because nowhere on this page does it say that.
Anyway, to further what Ulrich was saying, average-case analysis is complicated because it has to take into account how the data is represented on average, which is not trivial.
From Wikipedia: