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

本文介绍了python排序的空间复杂度是多少?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

What space complexity does the python sort take? I can't find any definitive documentation on this anywhere

推荐答案

空间复杂度定义为算法根据N元素需要多少额外空间.并且即使根据 docs ，sort方法如中所述，它会在适当的位置对列表进行排序，但确实会占用一些额外的空间.实施说明:

Space complexity is defined as how much additional space the algorithm needs in terms of the N elements. And even though according to the docs, the sort method sorts a list in place, it does use some additional space, as stated in the description of the implementation:

timsort可能需要一个包含多达N//2个指针的临时数组，这意味着32位盒子上最多有2 * N个额外的字节.排序随机数据时，可能需要一个如此大的临时数组.在结构显着的数据上，它可能不需要使用任何额外的堆内存就可以消失.

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)

Therefore the worst case space complexity is O(N) and best case O(1)