先按 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)。

Answer 2

首先，您将比较每对的第一个元素和 sort.Takes NlogN。如果第一个元素相同，现在将比较第二个元素。这需要 NlogN。总共 2Nlogn 就是 NlogN

希望对您有所帮助！！

Answer 3

如果您对您的数据一无所知，则无法保证比 O(N log(N)) 更好：所有第一个元素可能相同，然后您将无法将第二个元素排序为正常。

这就是 O(N log(N)) 界限的含义：如果您必须对数据进行通用比较排序，则无法对此进行改进。句号。

如果您有更多信息，那么（正如您的直觉推理）您或许可以对此进行改进。例如，假设任何 x 作为一对中的第一个元素至少出现一次，大约有 log(N) 对以 x 作为它们的第一个元素。在这种情况下，你的第一遍可以更有效率：

d = {}
for x, y in L:
    xL = d.setdefault(x, [])
    xL.append(y)
xs_sorted = sorted(d.keys())

这是（大约）O(N)，因为 d.keys() 有 N / log(N) 个元素。接下来，您可以对每个 N / log(N) 子列表进行排序，每个子列表的大小为 log(N):

L_sorted = []
for x in xs_sorted:
    ys_sorted = sorted(d[x])
    for y in ys_sorted:
        L_sorted.append((x, y))

这是 O(N log(log(N)))，它控制运行时 - 但比 O(N log(N)) 好！

Answer 4

Nlog(N) 复杂度中有一个常数因子，它取决于计算机在决定顺序之前如何进行比较。例如，如果对字符进行排序，则 Nlog(N) 的复杂度将变为

Nlog(N) * length of maximum string size

Time complexity of sort by x1, then x2?