Сложность создания списка с оператором concat в python

Question

Я начинаю изучать структуры данных + алгоритмы, и я столкнулся с проблемой.Вот функция, которую я тестирую:

def create_list_with_concat(n):
    l = []
    for i in range(n):
        l = l + [i]

Вот мой мыслительный процесс: я знаю, что оператор concat равен O(k), где k - это размер списка, добавляемого в исходный список.Поскольку в данном случае размер k всегда равен 1, поскольку мы добавляем по одному списку символов за раз, операция concat выполняет шаг 1.Поскольку цикл повторяется n раз, алгоритм будет выполнять n шагов - делая 1 шагов за итерацию.Следовательно, временная сложность алгоритма будет O(n).Фактическое время выполнения алгоритма будет выглядеть примерно так: T(n) = dn, где d - это время, необходимое для выполнения конкатенации.Для такой функции я ожидал бы, что верно следующее: когда вы увеличиваете размер ввода в 10 раз, вывод (время выполнения) увеличится в 10 раз, так как:

(x, dx) --> (10x, 10dx) --> 10dx/dx = 10

Однако, когда я проверяю алгоритм на реальных значениях и времени выполнения, это, похоже, не происходит.Вместо этого, когда я увеличиваю размер ввода в 10 раз, вывод (время выполнения) увеличивается в 100 раз, а когда я увеличиваю размер ввода в 100 раз, вывод увеличивается в 10000 раз.Эти выходные данные предлагают квадратичную функцию времени и O(n squared).

Вот мой полный код:

import timeit
def create_list_with_concat(n):
    l = []
    for i in range(n):
        l = l + [i]

t1 = timeit.Timer("create_list_with_concat(100)", "from __main__ import 
create_list_with_concat")
print("concat ",t1.timeit(number=1)*1000, "milliseconds")
t1 = timeit.Timer("create_list_with_concat(1000)", "from __main__ 
import create_list_with_concat")
print("concat ",t1.timeit(number=1)*1000, "milliseconds")
# OUTPUT
# concat  0.05283101927489042 milliseconds
# concat  2.8588240093085915 milliseconds

Большое спасибо за помощь.

Answer 1

Вот мой мыслительный процесс: я знаю, что оператор concat равен O (k) , где k - размер списка, добавляемого в исходный список.Поскольку размер k в этом случае всегда равен 1, поскольку мы добавляем по одному списку символов за раз, операция concat занимает 1 шаг.

Это предположение равно неправильно .Если вы напишите:

l + [i]

, вы создадите новый список, этот список будет иметь m + 1 элементов, с m количеством элементов в lучитывая, что список реализован как массив, мы знаем, что создание такого списка займет O (m) время.Затем мы присваиваем новый список l.

. Это означает, что общее количество шагов равно:

 n
---
\              2
/    O(m) = O(n )
---
m=0

, поэтому сложность по времени составляет * 1031.* O (n ² ) .

Однако вы можете повысить производительность, используя l += [i] или даже быстрее l.append(i), где стоимость амортизации для обоих l += [i] и l.append(i) O (1) , поэтому алгоритм равен O (n) , однако l.append(i), вероятно, будет немного быстреепотому что мы экономим на создании нового списка и т. д.

Answer 2

>>> spam = []
>>> eggs = spam
>>> spam += [1]
>>> eggs
[1]
>>> spam = []
>>> eggs = spam
>>> spam = spam + [1]
>>> eggs
[]

Есть разница в сложности между изменением списка и созданием нового.

Answer 3

Сложность по времени не O(N)

Сложность по времени операции concat для двух списков, A и B, составляет O(A + B).Это потому, что вы не добавляете в один список, а вместо этого создаете целый новый список и заполняете его элементами как из A, так и из B, что требует от вас итерации по обоим.

Следовательно, выполняя операцию l = l + [i] равно O(len(l)), оставляя вам N шагов для выполнения операции N, в результате чего общая сложность составляет O(N^2)

Вы путаете конкатат с append или extendфункция, которая не создает новый список, но добавляет к оригиналу.Если бы вы использовали эти функции, ваша временная сложность действительно составила бы O(N)

Дополнительное примечание:

Обозначение l = l + [i] может сбивать с толку, поскольку интуитивно кажется, что [i] простодобавлено к существующему l.Это не так!

l + [i] создает совершенно новый список, а затем указывает l на этот список.

С другой стороны, l += [i] изменяет исходный список и ведет себякак extend