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排序的空间复杂度是多少?
发布评论