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

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)时间内运行。研究论文通常通过给出用于分析的标准机器模型来做到这一点。该模型规定了低级操作（例如内存访问、算术和比较）所需的时间。

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

然而，像字符串排序这样简单的事情改变了这种情况。字符串比较本身具有可变成本。这取决于字符串的长度！因此，使用“好的”排序算法对字符串进行排序的时间复杂度为 O(nk log n)，其中 k 是字符串的长度。

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

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

但即便如此也存在复杂性。对指针进行排序后，按顺序触摸已排序的元素会以任意顺序在内存中跳跃。这可能会导致糟糕的内存层次结构（缓存）性能。结合记忆特征的分析本身就是一个大话题。