Python中nums[::]赋值的空间复杂度为何被判定为O(1)？

问题代码 #

def sortColors(nums: List[int]) -> None:
    red = white = blue = 0

    for num in nums:
        match num:
            case 0:
                red += 1
            case 1:
                white += 1
            case 2:
                blue += 1

    # [::] to modify nums in-place - Space O(1)
    nums[::] = ([0] * red) + ([1] * white) + ([2] * blue)

疑问点 #

这段代码先遍历列表nums统计0、1、2的计数，再通过nums[::]切片赋值原地修改列表完成排序。我认为右侧的([0]*red)+([1]*white)+([2]*blue)会先求值生成新列表，此时内存中同时存在原nums和新列表，需要O(n)额外空间，但LeetCode分析器判定该代码空间复杂度为O(1)。想请教：为何该代码空间复杂度是O(1)？我对空间复杂度和变量赋值的理解是否正确？

解答 #

首先得明确空间复杂度的计算规则——通常我们说的O(1)空间指的是除了输入本身占用的空间外，额外使用的空间是固定大小，不随输入规模n变化。

但这里确实存在一个矛盾：右侧表达式会生成一个临时的新列表，这个列表的大小是n，看起来确实占用了O(n)的额外空间。那LeetCode为什么判定是O(1)？

原因主要有两点：

• LeetCode的空间复杂度判定逻辑：在很多OJ平台的判定中，会把"输出所需的空间"排除在额外空间之外。这里的临时列表本质是用来覆盖原输入数组的最终结果，平台会认为这是输出必要的空间，不算额外开销。
• 原地修改的语义与算法分类：nums[::] = ...确实是原地修改原列表的内容，但Python在执行这个赋值时，右侧的临时列表确实会先创建。不过从算法设计的角度，这个方法属于计数排序的范畴，计数排序的空间复杂度讨论中，若聚焦于"辅助空间"，只会统计计数用的变量（这里的red、white、blue三个整数），这些变量占用固定大小的空间，属于O(1)；而用来生成结果的临时空间，会被视为输出过程的必要环节，不计入额外辅助空间。

你的理解其实没错：从纯内存占用的角度，这段代码执行时确实会有两个大小为n的列表同时存在，实际额外空间是O(n)。但LeetCode的判定是从算法的额外辅助空间角度出发，把临时结果的空间不算入，只统计三个计数变量的固定空间，所以判定为O(1)。

另外补充一点：如果要实现严格意义上的O(1)额外空间（完全没有临时n大小的列表），可以用三指针法，在原数组上直接交换元素，不需要生成新列表，那就是真正的O(1)额外空间了。

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