Java比较器的运行时复杂性是什么?

Question

我有一个自定义对象，可以说具有String name和int age的Person.java。假设我有100个不同的对象Person实例，我想用自定义比较器(S.T.(进行排序。最大的人会在最小的时候走。编写比较器本身很容易 - 只需实现"比较方法"，我会将对象放入List(或Queue会更好？(。但是，此比较方法的运行时间是什么？执行某些自定义排序方法本身的速度更快吗？

Answer 1

此比较方法的运行时间是什么？

这取决于您如何实现它(！(，但是，如果您只是在相应对象中比较age和/或name字段的值，则应是O(1)。

通常根据其执行的比较数来表示一种类型算法的复杂性。因此，如果所选的排序算法是O(NlogN)，并且您的Comparator是O(1)，我们可以预测 ¹ ，总体复杂性将为O(NlogN x 1)或O(NlogN)。

执行某些自定义排序方法本身会更快吗？

否。如果您实现自定义排序，它当然不会提高复杂性。(对于通用单线程排序，您不能比O(NlogN)做得更好。(

• 如果您将比较代码手动"分配"到您的自定义排序中，则您仍将执行相同的操作以比较字段并进行相同的次数。

• 更一般而言，Java 8和后来的内置sort(...)使用的算法是最新的算法。您不太可能没有大量成本(开发和/或可维护性(对它们进行改进。

---

这个问题闻到了"过早优化"。请阅读这意味着什么以及为什么它是(通常(是一件坏事。

---

^{1-我不声称这是一个适当的证明。尽管我认为适当的证据也会给出这个答案。}

Answer 2

我认为您正在使用JDK8或类似。

在大多数情况下，您只需要以下代码即可完成您描述的任务，并且表现非常好：

List<Person> list = new ArrayList<>();
list.add(p1);
list.add(p2);
// adding all elements
...
list.sort(comparator);

作为替代方案，如果实现了可比接口，则可以使用Collections.sort()方法。有关更多详细信息，请参见list.sort((和collections.sort((。

运行时间复杂性

list.sort(comparator);线具有

的运行时间复杂性

O(n) x O(log(n)) x C

我们应该考虑2个部分：

1. O(n) x O(log(n))：与排序算法有关，如list.sort((文档中所述，在最坏的情况下，我们可以期待 n*log(n)，这就是为什么我使用大 O，但是如果列表部分是部分分类的，则运行时间接近n。
2. C：与compareTo()实现的运行时间有关，如您所提到的，您只是在比较它们的年龄，这很简单，这不应该是一个问题。因此，此实现时间预计是恒定的，也就是O(1)。(这可能是您要的(

如果第二点是正确的，则总运行时间复杂性应表示为：

O(n) x O(log(n))