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.

Answer 4

1
投票

平均情况下的时间复杂度为

O(nlog(n))

Answer 5

我无法发表评论，因为我没有足够的声誉，但从 Python 3.11 开始，Python 现在使用

powersort

-

Timsort

算法的优化。

这仍然是

O(n log n)

，但无论如何我想提一下它，以便更准确，并且对于任何看到这篇文章感到好奇的人。