python排序需要多少空间复杂度？我在任何地方都找不到这方面的任何明确文档
空间复杂度定义为算法需要多少额外空间N元素。并且尽管根据docs https://docs.python.org/3/library/stdtypes.html#list.sort, the sort方法就地对列表进行排序，它确实使用了一些额外的空间，如描述 https://github.com/python/cpython/blob/master/Objects/listsort.txt实施情况：
timsort 可能需要一个包含多达 N//2 个指针的临时数组，这意味着在 32 位框上有多达 2*N 的额外字节。在对随机数据进行排序时，预计需要这么大的临时数组；对于具有重要结构的数据，它可能会在不使用任何额外堆内存的情况下消失。
因此最坏情况的空间复杂度是O(N)和最好的情况O(1)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
