这个python排序方法的复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14434490/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the complexity of this python sort method?
提问by Read Q
I have a list of lists and I am sorting them using the following
我有一个列表列表，我正在使用以下方法对它们进行排序
data=sorted(data, key=itemgetter(0))
Was wondering what is the runtime complexity of this python method?
想知道这个 python 方法的运行时复杂度是多少？
采纳答案by NPE
回答by blackmath
sorted is like sort except that the first builds a new sorted list from an iterable while sort do sort in place. The main difference will be space complexity.
sorted 就像 sort ，除了第一个从一个可迭代对象构建一个新的排序列表，而 sort 进行就地排序。主要区别在于空间复杂度。
回答by Lerner Zhang
It is the Timsort, and Timsort is a kind of adaptive sorting algorithm based on merge sort and insertion sort, then I thought it belongs to the comparison sort, and it's said, no comparison sort can guarantee a time complexity smaller than lg(N!) ~ N log N.
就是Timsort，Timsort是一种基于归并排序和插入排序的自适应排序算法，后来我认为它属于比较排序，据说，没有比较排序可以保证时间复杂度小于lg(N! ) ~ N log N。
