EPI 5.10置换算法O(1)空间复杂度及列表赋值方式疑问

第一个问题：列表推导式是否导致O(N)空间复杂度？ #

你观察得非常准确：[a + len(perm) for a in perm]确实会创建一个全新的长度为N的列表，这一步的空间开销是O(N)。那为什么原算法声称是O(1)空间复杂度呢？

这里要区分核心逻辑的额外空间和输入恢复的临时空间：

• 算法的核心置换逻辑（循环处理数组A的部分）是纯原地操作，只用到了next、temp这几个常数级别的临时变量，额外空间确实是O(1)。
• 最后一步的列表推导式是用来恢复输入的perm数组——因为前面的循环把perm里的元素都减去了len(perm)做标记，这一步要把它还原成初始状态。很多时候，这类原地算法会把“恢复输入的临时空间”排除在额外空间的计算之外，毕竟如果业务场景不需要保留原始perm，这一步完全可以去掉，核心逻辑就真的是纯O(1)额外空间了。

如果严格抠定义，这一步确实有O(N)的临时空间，但通常我们说这个算法是O(1)空间，指的是它没有额外开辟和输入规模相关的空间来存储结果或中间状态，只是用了常数级别的临时变量。

第二个问题：perm[:] = ... vs perm = ...的区别 #

这两者的本质差异是修改原列表对象，还是重新绑定变量：

• 用perm = [a + len(perm) for a in perm]：这会生成一个新列表，然后把函数内部的局部变量perm指向这个新对象。但函数外部传入的那个原始perm列表完全不受影响——因为函数里的perm只是个引用，重新赋值只是换了这个引用指向的对象，和原对象没有关系。
• 用perm[:] = [a + len(perm) for a in perm]：这是原地修改原始列表的内容，会把新列表的元素逐个替换到原来的perm列表里。这样函数外部的那个perm列表也会被还原成初始状态，因为我们操作的是同一个列表对象。

举个直观的例子：

def reassign(perm):
    perm = [x + 1 for x in perm]

def in_place_modify(perm):
    perm[:] = [x + 1 for x in perm]

original = [0,1,2]
reassign(original)
print(original)  # 输出 [0,1,2]，原列表没变化
in_place_modify(original)
print(original)  # 输出 [1,2,3]，原列表被修改了

回到原算法，它需要在置换完成后把perm还原成初始状态（毕竟调用者可能还要复用这个数组），所以必须用perm[:] = ...来原地修改，否则外部的perm会一直是被标记后的负数数组，这显然不符合预期。

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