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

o2rvlv0m 于 2022-12-28 发布在 Java

关注(0)|答案(3)|浏览(139)

假设我有一个类：'

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）时间，问题是如果我对一个有两个属性的对象列表进行排序，那么对这个列表进行排序的时间复杂度是多少？

Java

来源：https://stackoverflow.com/questions/40700270/whats-the-time-complexity-of-sorting-a-list-of-objects-with-two-properties

3条答案

按热度按时间

drnojrws1#

@PaulMcKenzie在评论中的简短回答是在正确的轨道上，但对你的问题的完整回答更微妙。
很多人做了你做过的事情，把时间和其他效率的度量标准混淆了，当有人说“排序是O（n log n）”时，几乎所有情况下正确的是比较的次数*是O（n log n）。
我并不想卖弄学问。草率的分析在实践中会产生大问题。你不能声称任何排序都能在O（nlogn）时间，而不需要大量关于数据和运行算法的机器的额外陈述。研究论文通常通过给出用于分析的标准机器模型来做到这一点。该模型陈述了低级操作所需的时间--例如存储器访问、算术和比较。
在您的例子中，每个对象比较需要常量（2）的值比较，只要值比较本身是常量时间--实际上对于固定宽度的整数为真-- O（nlogn）是表示运行时间的一种精确方式。
然而，像字符串排序这样简单的事情却改变了这幅图景。字符串比较本身就有一个可变的成本。它取决于字符串的长度！所以用一个“好的”排序算法对字符串进行排序是O（nk log n），其中k是字符串的长度。
如果你对可变长度的数字排序（比如java BigInteger s），也是如此。
排序对复制成本也很敏感。即使可以在恒定时间内比较对象，排序时间也将取决于对象的大小。算法的不同之处在于对象需要在内存中移动多少次。有些算法接受更多的比较，以便执行更少的复制。实现细节如下：排序指针与对象可以改变渐近运行时间-时间交易的空间。
但即使这样也有复杂性。在指针排序后，按顺序触摸排序后的元素会以任意顺序在内存中跳跃。这可能会导致糟糕的内存层次（缓存）性能。结合内存特征的分析本身就是一个大主题。