覆写函数输入的空间复杂度：辅助空间为O(N)还是O(1)？

先看问题中的函数：

def foo(nums):
    nums = sorted(nums)
    return nums

核心结论 #

这个函数的辅助空间复杂度是 O(N)，而非O(1)。

原因分析 #

1. 辅助空间复杂度的定义：计算的是算法执行过程中额外新增的临时空间，不包含输入数据本身占用的空间。
2. sorted()的行为：它会生成一个输入列表的全新副本，这个副本需要占用O(N)的空间，这部分是算法执行时额外分配的。
3. 覆写参数的本质：只是让变量nums从指向原输入列表，改为指向sorted()生成的新列表。原输入列表的空间属于输入本身的开销，而新列表的空间是额外新增的——哪怕原输入后续被垃圾回收，这也是语言运行时的内存管理行为，不影响复杂度分析的结论。

简单说：只要算法在执行过程中创建了和输入规模同量级的新空间，不管有没有覆写参数变量，这部分空间都要算入辅助空间复杂度。

内容的提问来源于stack exchange，提问作者LateGameLank