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

Question

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

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

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

Answer 1

提供itemgetter(0)的是O(1)当与 一起使用时data，排序是O(n log n)平均的和最坏的情况。

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

Answer 2

sorted 与 sort 类似，不同之处在于前者从可迭代对象中构建一个新的排序列表，而 sort 则在原地进行排序。主要区别在于空间复杂度。

Answer 3

就是Timsort，Timsort是一种基于归并排序和插入排序的自适应排序算法，后来我以为它属于比较排序，据说没有比较排序可以保证小于lg(N! ) ~ N log N。