Не зная устройства встроенных типов Python, нельзя оценить реальную сложность алгоритма: одна строка x in a для списка стоит O(n), а для множества O(1). Таблицы ниже опираются на документированное поведение CPython (страница TimeComplexity на python.org), а каждое утверждение мы проверим небольшим замером.
list
| Операция | Стоимость |
|---|---|
a[i], a[i] = x, len(a) | O(1) |
a.append(x), a.pop() | O(1) (append амортизированно) |
a.insert(i, x), a.pop(i), a.pop(0), del a[i] | O(n) — элементы сдвигаются |
x in a, a.index(x), a.count(x), a.remove(x) | O(n) |
a[i:j], a.copy() | O(j - i), O(n) — копия |
a.extend(b), a + b | O(len(b)), O(len(a) + len(b)) |
min(a), max(a), sum(a), a.reverse() | O(n) |
a.sort(), sorted(a) | O(n log n), на отсортированном входе O(n) |
from timeit import timeit
n = 100_000
data = list(range(n))
at_end = timeit(lambda: (data.append(0), data.pop()), number=2000)
at_front = timeit(lambda: (data.insert(0, 0), data.pop(0)), number=2000)
print("front is much slower than end:", at_front > 5 * at_end)front is much slower than end: True