java - 对具有两个属性的对象列表进行排序的时间复杂度是多少？

Question

假设我有一个类:`

public class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

`

我想像这样使用 Collections.sort() 对间隔列表进行排序:

Collections.sort(intervals, new Comparator<Interval>(){
    @Override
    public int compare(Interval o1, Interval o2) {
        if (o1.start == o2.start) {
            return o1.end - o2.end;
        }
        else {
            return o1.start - o2.start;
        }
    }
});

我知道使用内置排序函数对数组进行排序需要 O(nlogn) 时间，问题是如果我正在对具有两个属性的对象列表进行排序，那么对这个列表进行排序的时间复杂度是多少？谢谢!!

Answer 1

@PaulMcKenzie 在评论中的简短回答是正确的，但对您问题的完整回答更加微妙。

很多人都在做您做过的事情，并将时间与其他效率衡量标准混淆了。在几乎所有情况下，当有人说“排序是 O(n log n)”时，正确的是比较的数量是 O(n log n)。

我不是想学究气。草率的分析会在实践中造成大问题。如果没有大量关于数据和运行算法的机器的附加声明，您就不能声称任何排序都在 O(n log n) time 中运行。研究论文通常通过提供用于分析的标准机器模型来做到这一点。该模型规定了低级操作所需的时间 - 例如，内存访问、算术和比较。

在您的情况下，每个对象比较都需要常数 (2) 的值比较。只要值比较本身是常数时间——在实践中对于固定宽度的整数是正确的——O(n log n) 是表达运行时间的准确方法。

然而，像字符串排序这样简单的事情改变了这幅图景。字符串比较本身具有可变成本。这取决于字符串长度!所以用“好的”排序算法对字符串进行排序是 O(nk log n)，其中 k 是字符串的长度。

如果您要对可变长度数字进行排序(例如 java BigInteger)，则同上。

排序对复制成本也很敏感。即使您可以在常数时间内比较对象，排序时间也将取决于它们的大小。算法在对象需要在内存中移动多少次方面有所不同。有些人接受更多的比较以减少复制。实现细节:排序指针与对象可以改变渐近运行时间 - 时间交易的空间。

但即使这样也有并发症。对指针进行排序后，按顺序触摸排序的元素会以任意顺序在内存中跳跃。这会导致糟糕的内存层次结构(缓存)性能。结合内存特性的分析本身就是一个很大的课题。