Какова сложность пространства?

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.

Вы можете достичь сложности пространства O (1), используя itertool.slice чтобы не делать копии:

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