python - Python sorted() 函数空间复杂性

Question

我知道 sort() 是 O(1) 空间，因为排序已经到位。但是， sorted() 函数返回一个包含已排序元素的新列表。既然 sorted() 返回一个带有排序元素的新数组，这是否意味着使用 sorted() 函数的算法需要 O(n) 空间来执行？sorted() 与创建一个数组并复制所有元素，然后在该新数组上运行 sort() 是否相同？

for i in sorted(some_list):
    // do something

标签： pythonalgorithmsortingtime-complexityspace-complexity

Answer 1

sorted()使用 Timsort：https ://en.wikipedia.org/wiki/Timsort ，它具有 O(n) 空间复杂度。