Списки, словари и множества в Python
1. Списки
Список (list)
Для начала вспомним операции работы со списками.
| Операция | Пример | Трудоемкость | Замечания |
| Взятие индекса | l[i] | O(1) | |
| Сохранение элемента | l[i] = 0 | O(1) | |
| Длина | len(l) | O(1) | |
| Добавление в конец | l.append(5) | O(1) | |
| Извлечение с конца | l.pop() | O(1) | |
| Очистка списка | l.clear() | O(1) | Аналогично l = [] |
| Срез(Slice) | l[a:b] | O(b-a) | |
| Расширение | l.extend(A) | O(len(A)) | Зависит только от длины A |
| Создание | list(A) | O(len(A)) | Зависит от длины A (итерируемый объект) |
| Проверка ==, != | l1 == l2 | O(N) | |
| Присваивание в срез | [a:b] = ... | O(N) | |
| Удаление элемента | del l[i] | O(N) | |
| Поиск элемента | x (not) in l | O(N) | Поиск работает за O(N) |
| Копирование списка | l.copy() | O(N) | То же самое что l[:], который O(N) |
| Удаление из списка | l.remove(..) | O(N) | |
| Извлечение элемента | l.pop(i) | O(N) | O(N-i): l.pop(0):O(N) (см. выше) |
| Экстремумы | min(l)/max(l) | O(N) | Поиск работает за O(N) |
| Обращение | l.reverse() | O(N) | |
| Итерирование | for v in l: | O(N) | |
| Сортировка | l.sort() | O(N Log N) | |
| Перемножение | k*l | O(k N) | 5*l будет за O(N), len(l)*l будет O(N**2) |
У разработчиков типа данных list Python было много вариантов каким сделать его во время реализации. Каждый выбор повлиял на то, как быстро список мог выполнять операции. Одно из решений было сделать список оптимальным для частых операций.
Индексирование и присваивание
Две частые операции - индексирование и присваивание на позицию индекса. В списках Python значения присваиваются и извлекаются из определенных известных мест памяти. Независимо от того, насколько велик список, индексный поиск и присвоение занимают постоянное количество времени и, таким образом их трудоемкость O(1).
Pop, Shift, Delete
Извлечение элемента(pop) из списка Python по умолчанию выполняется с конца, но, передавая индекс, вы можете получить элемент из определенной позиции. Когда pop вызывается с конца, операция имеет сложность O(1) , а вызов pop из любого места - O(n). Откуда такая разница?
Когда элемент берется из середины списка Python, все остальные элементы в списке сдвигаются на одну позицию ближе к началу. Это суровая плата за возможность брать индекс за O(1), что является более частой операцией.
По тем же причинам вставка в индекс - O(N); каждый последующий элемент должен быть сдвинут на одну позицию ближе к концу, чтобы разместить новый элемент. Неудивительно, что удаление ведет себя таким же образом.
Итерирование
Итерирование выполняется за O(N), потому что для итерации по N элементам требуется N шагов. Это также объясняет, почему оператор in, max, min в Python является O(N): чтобы определить, находится ли элемент в списке, мы должны перебирать каждый элемент.
Срезы
Чтобы получить доступ к фрагменту [a: b] списка, мы должны перебрать каждый элемент между индексами a и b. Таким образом, доступ к срезу - O(k), где k - размер среза. Удаление среза O(N) по той же причине, что удаление одного элемента - O(N): N последующих элементов должны быть смещены в сторону начала списка.
Умножение на int
Чтобы понять умножение списка на целое k, вспомним, что конкатенация выполняется за O(M), где M - длина добавленного списка. Из этого следует, что умножение списка равно O(N k), так как умножение k-размера списка N раз потребует времени k (N-1).
Разворот списка
Разворот списка - это O(N), так как мы должны переместить каждый элемент.