You need to enable JavaScript to run this app. 问询该Python实现的快速排序空间复杂度及递归栈与辅助内存的关联规则
优惠活动
大模型
产品
解决方案
定价
更多

问询该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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 07:36:09