Python 列表切片的空间复杂度

Question

我很难理解 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 是字符串时不同还是相同，例如ans = '12345...n'？

Answer 1

Python 严格遵守可能的副作用。就语言而言，就地执行任何操作都是不正确的。

您的操作

 arr[2:] = arr[2:][::-1]

是三个独立的切片操作：

• arr[2:]从 的所有元素（但前两个）创建一个新列表arr。
• ...[::-1]从创建一个新的，颠倒列表的所有元素的...。
• arr[2:] = ...替换with 的所有元素（但前两个）。arr...

每个切片操作基本上相当于原始 O(n) 复制操作。由于仅复制引用，因此元素的大小或类型无关紧要。

在您的完整示例中，这相当于 O(k) 循环中的三个 O(n) 切片操作：

ans = [i+1 for i in range(n)]   # O(n)
for i in range(k):              # O(k)
    ans[i:] = ans[i:][::-1]     # O(n)

总的来说，时间复杂度为 O(nk)。空间复杂度仅为 O(n)，因为临时切片可立即回收。你基本上得到了初始列表，加上一些临时副本。

它会与ans字符串时不同还是相同，例如ans = '12345...n'？

操作的复杂性没有改变——它们仍然是相同的原始操作。

实际上，CPython 实现会欺骗某些对象。例如，+=是用引用计数为1的字符串就地突变即使字符串是不可变的。但是，这不适用于您的切片使用。

一般来说，依赖内置优化对 Python 来说是个坏主意。

如果您担心空间，请从编写精益代码开始。例如，ans[i:][::-1]应该只是ans[i::-1]. 仅此一项就将所需的临时空间减半。