algorithm - 先按 x1 排序，然后按 x2 排序的时间复杂度？

Question

标准排序函数文献会告诉您排序通常(​​合并、快速)可以在 N log N 中完成。

例如，如果我有这个列表:[1,6,3,3,4,2]

会在NlogN时间内排序为:[1,2,3,3,4,6]

如果我有一个按第一个属性排序的列表，然后是第二个属性怎么办？

像这样:[(1,1),(6,3),(3,4),(3,1),(2,8)] 到这样: [(1,1),(2,8),(3,1),(3,4),(6,3)]

它的时间复杂度是多少？

我想出的是，如果所有第一个索引都相同，那么您只是再次执行 N log N，所以是一样的。如果有一堆不同的第一个索引，那么您正在重新排序一堆小集合。

Answer 1

合并排序(或快速排序)执行 O(N log N) 比较。它的时间复杂度是 O(N log N * time_to_compare_two_elements)。比较一对元素的时间复杂度是常数(如果比较两个元素的时间是常数)。因此，对数组进行排序的时间复杂度也是 O(N log N)。