Предположим, что мы два списка A = [a1, a2, ..., an] (п элементов), и B = [b1, b2, ..., bm] (м элементов), и мы используем «+» в Python, чтобы объединить два списка в один, таквремя выполнения слияния двух списков в Python
C = A + B;
Мой вопрос: какова продолжительность выполнения этой операции? Мое первое предположение - O(n+m), не уверен, что Python умнее этого.
При объединении двух списков с A + B вы создаете совершенно новый список в памяти. Это означает, что ваша догадка верна: сложность O(n + m) (где n и m - это длины списков), так как Python должен идти по обоим спискам, чтобы построить новый список.
Вы можете увидеть, как это происходит в функции list_concat в source code for Python lists:
static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
/* ...code snipped... */
src = a->ob_item;
dest = np->ob_item;
for (i = 0; i < Py_SIZE(a); i++) { /* walking list a */
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
src = b->ob_item;
dest = np->ob_item + Py_SIZE(a);
for (i = 0; i < Py_SIZE(b); i++) { /* walking list b */
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
/* ...code snipped... */
Если вам не нужен новый список в памяти, это часто хорошая идея, чтобы воспользоваться тем, что списки mutable (и это где Python - умный). Использование A.extend(B) - это O(m), что означает, что вы избегаете накладных расходов на список копирования a.
Сложность операций с различными списками перечислены here в вики Python.
Копирование списка: O(n) (с n - количество элементов), а расширение - O(k) (при этом n - это число элементов во втором списке). Исходя из этих двух фактов, я думаю, что это не может быть меньше O(n+k), так как это операция копирования и продления, и, самое меньшее, вам нужно будет скопировать все элементы обоих списков.
Источник: Python TimeComplexity
Моя первая догадка
O(n+m), не уверен, если Python умнее, чем это. не
Ничто может быть умнее, чем при возвращении в копию. Хотя даже если A, B были неизменяемыми последовательностями, такими как строки; CPython по-прежнему делает полную копию вместо сглаживания одной и той же памяти (это упрощает реализацию коллекции мусора для таких строк).
В некоторых конкретных случаях, операция может быть O(1) в зависимости от того, что вы хотите сделать с результатом, например, itertools.chain(A, B) позволяет перебрать все элементы (это не делает копию, изменение A, B влияет на Поддавшись элементы). Или если вам нужен произвольный доступ; вы можете эмулировать его с использованием подкласса Sequence, например WeightedPopulation, но в общем случае копия и, следовательно, время выполнения O(n+m) неизбежны.
Добавление двух списков * будет * быть O (n + m), потому что каждый список Python реализован как массив C фиксированного размера. Когда вы добавляете два списка, вы выделяете память для нового массива и копируете каждый элемент каждого списка членов в массив. Использование append() и extend() улучшит производительность до O (m), но если вы * должны * создать третий список и сохранить исходные два, нет очевидного способа улучшить O (n + m). – dylrei