问询该Python实现的快速排序空间复杂度及递归栈与辅助内存的关联规则
针对该Python快排实现的空间复杂度答疑
先附上讨论的目标实现:
def quick_sort(lst): if len(lst) < 2: return lst pivot_lst = lst[0] left_side = [el for el in lst[1:] if el < pivot_lst] right_side = [el for el in lst[1:] if el >= pivot_lst] return quick_sort(left_side) + [pivot_lst] + quick_sort(right_side)
1. 辅助列表分配的推导结果匹配性
你最初基于级数累加的推导,虽然逻辑上是统计了所有历史分配的列表总量(和空间复杂度的标准定义——执行过程中峰值同时存活的内存——不完全契合),但最终得到的两个场景结果刚好和真实的峰值占用完全匹配:
- 期望均匀分区场景:递归执行时会先深入左分区到底,每一层递归对应的临时列表(原始n长度、n/2长度、n/4长度……直到长度为1的子列表)在子递归返回前都不会被释放,这些同时存活的列表总元素数求和就是n + n/2 + n/4 + …≈2n,对应O(n)的临时列表占用,推导结果正确。
- 最坏极值分区场景:每次pivot选到列表最大/最小值时,只有一个分区非空,每一层递归生成的临时列表长度为n-1、n-2……1,这些列表同样要等子递归返回才会被释放,总元素数求和就是n + (n-1) + (n-2)+…+1,对应O(n²)的临时列表占用,推导结果也正确。
这里要特别说明:这个结果是该非原地实现特有的,和教材中常见的原地交换式快排不是一个逻辑——后者的临时分区空间是O(1),完全不会出现O(n²)的临时列表占用。实际运行时就能感受到差异:比如对已排序的列表跑这个实现,n=10000时临时列表的总存活元素数就已经达到千万级,对应内存几十MB;n=1e5时就会到GB级,本质就是临时列表的O(n²)占用导致的,和栈空间无关。
2. 递归栈帧的内存计入规则
递归调用的栈帧内存是必须计入总空间复杂度的,不能凭空忽略:
- 栈帧的总占用和递归深度直接挂钩:每个栈帧只需要存固定大小的局部变量(函数入参引用、pivot值、两个分区列表的引用),所以期望均匀分区下递归深度为O(log n),对应栈总占用就是O(log n);最坏极值分区下递归深度为O(n),对应栈总占用就是O(n)。
- 计算总内存时,需要把同一时刻存活的栈内存和堆上的临时列表内存全部相加:比如你举的例子,期望场景下临时列表是O(n),栈是O(log n),相加后总占用是O(n + log n),按照大O的渐近规则忽略低阶项,最终就是O(n),这个计算逻辑是完全正确的。
3. 辅助结构与栈空间的合并计算逻辑
大家常说“取两者空间复杂度的较大值作为最终结果”,本质是渐近分析的特性导致的,不是因为这两部分内存是互斥占用的:
- 当两个空间量的阶数不同时,高阶项会完全主导总占用,低阶项的影响可以忽略,最终结果和取较大值的结果完全一致。比如前述的O(n)临时列表 + O(log n)栈、O(n²)临时列表 + O(n)栈,不管是直接相加还是取较大值,得到的最终复杂度阶数都没有区别。
- 即使两个空间量是同阶的,比如临时列表占O(n)、栈也占O(n),相加后的总占用是2*O(n),按照大O忽略常数因子的规则,最终结果还是O(n),依然和取较大值的结果一致。
唯一需要注意的认知误区是:不要把“取较大值”误解成只算其中一部分内存——两者是同时占用内存的,只是渐近分析不需要纠结常数和低阶项,最终的阶数结果恰好和取较大值的结论重合。
内容的提问来源于stack exchange,提问作者user7247147
相关产品推荐
相关产品推荐

