这个python排序方法的复杂性是什么？

Question

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

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

想知道这个python方法的运行时复杂性是什么？

Answer 1

设置itemgetter(0)是O(1)当用于data,排序是O(n log n)两者平均,并在最坏的情况下.

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

如果你知道`itemgetter(0)`的复杂性并且它不是'O(1)`那么你仍然可以解决整体的复杂性:`sorted`使`n`调用`itemgetter(0)`加上你的说. (3认同)
@MC：确实如此。然而，这与实际使用几乎无关。此外，*任何*排序算法都可以实现“O(n)”最佳情况。 (2认同)