迭代过程中的辅助空间复杂度分析疑问

先看目标函数代码：

def ReverseStr(s, k):
    """
    s: list of characters (length n)
    k: integer
    """
    for i in range(0, len(s), 2*k):
        s = s[:i] + s[i:i+k][::-1] + s[i+k:]
    return s

核心疑问解答：前序迭代的子列表不会保留在内存中 #

Python的垃圾回收机制会自动处理无引用的对象：每一轮迭代结束后，上一次循环里创建的所有临时子列表（包括旧的s变量指向的原列表），因为没有其他变量引用它们，会被标记为垃圾并回收。也就是说，只有当前迭代过程中正在创建的临时对象和新的s列表会占用内存，不会出现前序迭代的子列表累积占用内存的情况。

空间复杂度计算 #

每次迭代中，会创建这些临时子列表：

• s[:i]：长度为i的子列表
• s[i:i+k]：最长k的子列表，反转后生成另一个最长k的子列表
• s[i+k:]：最长n-(i+k)的子列表
• 最终拼接出的新s列表：长度为n

整个过程中，任意时刻的最大内存占用是n + k——新列表占n空间，加上反转时的临时切片（最多k）。由于旧对象会被及时回收，不存在内存累积，所以函数的空间复杂度为O(n + k)。

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