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

Question

python排序的空间复杂度是多少？我在任何地方都找不到关于此的任何权威文档

Answer 1

空间复杂度定义为根据 N 元素，算法需要多少额外空间。即使根据 docs , sort 方法对列表进行就地排序，它确实使用了一些额外的空间，如 description 中所述实现:

timsort can require a temp array containing as many as N//2 pointers, which means as many as 2*N extra bytes on 32-bit boxes. It can be expected to require a temp array this large when sorting random data; on data with significant structure, it may get away without using any extra heap memory.

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