我很难理解 Python 列表切片的空间复杂度。
对于像
arr[2:] = arr[2:][::-1]
新的空间是否为切片分配(就像在不可变字符串中所做的那样),还是在同一数组上执行操作?
对于像这样的内容:
ans = [i+1 for i in range(n)]
for i in range(k):
ans[i:] = ans[i:][::-1]
空间复杂度会是什么?当答案是一个字符串时,它与答案是
ans = '12345...n'
时会不同吗?我很难理解 Python 列表切片的空间复杂度。
对于像
arr[2:] = arr[2:][::-1]
for i in range(k):
ans[i:] = ans[i:][::-1]
ans = '12345...n'
时会不同吗?Python非常严格地遵守可能的副作用。就语言而言,在任何情况下,进行任何就地操作都是不正确的。
您的操作
arr[2:] = arr[2:][::-1]
arr[2:]
从arr
中的所有元素(除了前两个)创建一个新列表。...[::-1]
从...
中的所有元素创建一个新的反转列表。arr[2:] = ...
用...
替换arr
中的所有元素(除了前两个)。ans = [i+1 for i in range(n)] # O(n)
for i in range(k): # O(k)
ans[i:] = ans[i:][::-1] # O(n)
操作的复杂性不会改变-它们仍然是相同的原始操作。如果
ans
是一个字符串,例如ans = '12345 ... n'
,那么结果会不同吗?
如果您担心空间问题,请从编写简洁的代码开始。例如,ans [i:] [::-1]
应该简单地是ans [i :: -1]
。这可以将所需的临时空间减少一半。
id(...)
。 - Patrick Artner