Блог

Я понимаю, что амортизированная сложность добавления элемента в список равна O (1), но какова временная сложность добавления списка в список?

Для пояснения:

Добавление элемента в список

 list_ = []  
for _ in range(0,n):  
    list_.append(1)
 

Добавление списка в список

 list_ = []
list_.append([_ for _ in range(0,n)])
 

Еще раз ссылаясь на мой комментарий, «добавление» списка в список по-прежнему равно O (1), вы просто добавляете ссылку в список, «расширение» списка размера m будет стоить вам O (m), поскольку он должен пройти через другой список размера m, чтобыдобавьте каждый отдельный элемент.

 seq = [1, 2, 3]
new_seq = [4, 5, 6]

# Appending is O(1)
seq.append(new_seq)
print(seq) # [1, 2, 3, [4, 5, 6]]

seq = [1, 2, 3]
new_seq = [4, 5, 6]

# Extending is O(m), m = len(new_seq)
seq.extend(new_seq)

print(seq) #[1, 2, 3, 4, 5, 6]


list_ = []
list_.append([_ for _ in range(0,n)])
 

Для создания списка требуется O (n) времени [_ for _ in range(0,n)] , а затем O (1) времени, чтобы добавить ссылку на этот список в свой list_ . Всего O (n) для строки list_.append([_ for _ in range(0,n)]) .

Поскольку реализация .extend на самом деле лишь немного медленнее, чем добавление на месте, вы можете посмотреть источник .extend реализаций для ответа, например, здесь: https://github.com/python/cpython/blob/master/Objects/listobject.c

Как вы можете видеть, есть некоторые постоянные временные затраты, настройка результирующего списка с достаточным объемом памяти и тому подобное. И затем итератор, с помощью которого расширяется список, исчерпывается линейно, что означает, что временная сложность равна O (n).

list.append(item) это O(1) потому, что списки имеют произвольный доступ. list.extend(other_list) является O(k) , где k — размер other_list , предположительно, потому memcpy что это также операция линейного времени.

Если под «добавлением» вы подразумеваете, list.append(other_list) что сложность по-прежнему равна O (1), стоимость не меняется в зависимости от типа элемента.

В то время как, если вы имеете в виду конкатенацию на месте list.append(*other_list) , сложность равна O (n), где n — элементы второго списка.

Последний случай — это простая конкатенация list other_list , при которой вы создаете третий список, сложность равна O (m n), m и n — это два размера списков.