12

我认为是 MergeSort，即 O(n log n)。

但是，以下输出不同意：

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

我正在按序列号对 4 个节点的节点列表进行排序，并且排序正在进行 6 次比较。我很困惑，因为 6 > (4 log(4))。谁可以给我解释一下这个？

PS它是mergesort，但我仍然不明白我的结果。

谢谢大家的回答。谢谢汤姆纠正我的数学。

4

4 回答 4

29

O(n log n) 并不意味着比较次数将等于或小于 n log n，只是所花费的时间将与 n log n 成正比。尝试用 8 个节点、16 个节点或 32 个节点进行测试，并检查时间。

于 2009-04-15T19:08:17.863 回答
24

你对四个节点进行了排序，所以你没有得到归并排序；排序切换到插入排序。

在 Java 中，Arrays.sort() 方法根据数据类型使用归并排序或经过调整的快速排序，当排序的数组元素少于七个时，为了提高实现效率，切换到插入排序。（维基百科，重点补充）

Arrays.sort 由 Collections 类间接使用。

最近接受的一个错误报告表明，Java 的 Sun 实现将在未来使用 Python 的timsort ： http ://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124

（上面链接的 timsort 专着非常值得一读。）

于 2009-04-15T19:19:08.603 回答
3

处理数据量 n 的算法 A(n) 在 O(f(n)) 中，对于某些函数 f，如果存在两个严格的正常数 C_inf 和 C_sup，使得：

C_inf 。f(n) < ExpectedValue(OperationCount(A(n))) < C_sup 。f(n)

有两点需要注意：

  • 实际的常量 C 可以是任何东西，并且取决于操作的相对成本（取决于语言、VM、架构或您对操作的实际定义）。例如，在某些平台上，+ 和 * 具有相同的成本，而在另一些平台上，后者的成本要慢一个数量级。

  • 基于您正在处理的数据的一些可能任意模型，归属为“in O(f(n))”的数量是预期的操作计数。例如，如果您的数据几乎完全排序，则合并排序算法将主要是 O(n)，而不是 O(n . Log(n))。

于 2009-04-15T19:20:48.973 回答
2

我写了一些您可能对 Java 排序算法感兴趣的东西，并对 Collections.sort() 进行了一些性能测量。目前的算法是一个带有插入排序的合并排序，一旦你达到一定大小的子列表（注意这个算法很可能会在 Java 7 中改变）。

您真的应该将 Big O 表示法作为算法整体扩展方式的指示；对于特定的排序，精确的时间会偏离这个计算预测的时间（正如你将在我的图表上看到的那样，组合在一起的两种排序算法各自具有不同的性能特征，因此排序的总时间是有点复杂）。

也就是说，作为粗略的指导，每次将元素数量增加一倍，如果将预期时间乘以 2.2，就不会太远了。（不过，对于包含几个元素的非常小的列表，这样做并没有多大意义。）

于 2009-04-15T19:51:29.460 回答