Python排序的空间复杂度是多少？

Question

Python sort方法的空间复杂度是多少？我找不到任何关于它的明确文档。

- Kamal

Answer 1

空间复杂度是指算法在处理 N 个元素时需要额外使用的空间。虽然根据文档，sort 方法会就地排序列表，但它确实会使用一些额外空间，正如在实现说明中所述：

timsort可能需要一个临时数组，其中包含多达N//2个指针，这意味着32位盒子上最多有2*N个额外字节。当对随机数据进行排序时，可以预期需要这么大的临时数组；在具有显著结构的数据上，它可能不需要使用任何额外的堆内存。

因此，最坏情况下的空间复杂度为 O(N)，最好情况下为 O(1)

- damores

---

嗯，你肯定在对占用内存空间的东西进行排序。 - Olivier Melançon

没错，你肯定是对的，但是空间复杂度是指需要额外使用的内存，而不是数组本身。尽管如此，我看了一下实现描述，发现他们确实使用了一些额外的空间来实现算法。我的回答已经相应地更新了。 - damores

Answer 2

Python内置的排序方法是基于归并排序的改进版——Timsort，详细信息请参考https://zh.wikipedia.org/wiki/Timsort。

在平均情况下，Timsort与归并排序相当，其运行时间为O(n log n)，空间复杂度为Ω(n)。

- 23k

---

那并没有回答问题。 - juanpa.arrivillaga