sorted()函数的复杂度是多少？

Question

我有一个列表列表，我正在使用以下内容对它们进行排序

data=sorted(data, key=itemgetter(0))

想知道这个python函数的运行时复杂度是多少？

Answer 1

如果itemgetter(0)与data一起使用时为O(1)，则无论在平均情况下还是在最坏的情况下，排序都是O(n log n)。

有关Python中使用的排序方法的详细信息，请参阅Wikipedia。

Answer 2

排序类似于排序，不同之处在于前者从一个迭代器构建一个新的排序列表，而排序在原地进行排序。主要的区别将是空间复杂性。

Answer 3

它是Timsort，Timsort是一种基于合并排序和插入排序的自适应排序算法，因此我认为它属于比较排序，没有比较排序可以保证时间复杂度小于lg( N !) ~N log。