空间复杂度是多少？

Question

我不确定以下函数的空间复杂度是多少？是O(n)还是O(1)

# Do rotation
def foo(arr):
    arr[:] = arr[5:] + arr[:5]

Answer 1

arr[5:]和arr[:5]中的每一个都会构建一个新列表，然后加入到另一个新列表中，该列表将就地分配给arr。arr[5:]和连接表都需要O(n)的空间复杂度，因此总的空间复杂度为O(n)。

Answer 2

这取决于arr的类型，但假设它是一个list，那么它就是O(n)，因为RHS上的两个切片都创建了新的list对象，尽管是暂时的。这两个元素被连接到第三个新列表中，然后将其元素复制到arr引用的现有列表中。

您可以通过使用itertool.slice来避免制作副本，从而实现O(1)的空间复杂度：

def foo(arr):
    arr[:] = chain(islice(arr, 5, None), islice(arr, 5))