python排序的空间复杂度是多少? [英] What is the space complexity of the python sort?
问题描述
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)
这篇关于python排序的空间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!