| Операция | Результат | В среднем | В худшем случае |
|---|---|---|---|
x in s |
True, если в s есть элемент, равный x, иначе False | O(n) | |
x not in s |
False, если в s есть элемент, равный x, иначе True | O(n) | |
s + t |
Конкатенация s и t | O(len(s) + len(t)) | O(len(s) + len(t)) |
s * k или k * s |
Добавление s к самому себе k раз | O(len(s) * k) | O(len(s) * k) |
s[i] |
Взять i-ый элемент | O(1) | O(1) |
s[i] = x |
Установить i-ый элемент | O(1) | O(1) |
del s[i] |
Удалить i-ый элемент | O(n) | O(n) |
s[i:j] |
Взять срез s от i до j | O(j - i) | O(j - i) |
s[i:j:k] |
Взять срез s от i до j с шагом k | O((j - i) // k) | O((j - i) // k) |
s[i:j] = t |
Изменение среза | O(len(s) + len(t)) | O(len(s) + len(t)) |
del s[i:j] |
Удаление среза | O(n) | O(n) |
for x in s |
Итерация | O(n) | O(n) |
len(s) |
Длина s | O(1) | O(1) |
min(s) |
Минимальный элемент s | O(n) | |
max(s) |
Максимальный элемент s | O(n) | |
s.index(x[, i[, j]]) |
Индекс первого вхождения x в s (в диапазоне от i до j) | O(n) | O(n) |
s.count(x) |
Количество вхождений x в s | O(n) | O(n) |
s.append(x) |
Добавление элемента x в конец s | O(1) | O(1) |
s.sort() |
Сортировка | O(n log n) | O(n log n) |
s.extend(t) |
Добавление всех элементов t в в конец s | O(n + m) | O(n + m) |
s.pop() |
Вытащить последний элемент | O(1) | O(1) |
s.pop(i) |
Вытащить i-ый элемент | O(n - i) | O(n - i) |
s.insert(i, x) |
Вставить на i-ое место элемент x | O(n) | O(n) |
| Операция | Результат | В среднем | В худшем случае |
|---|---|---|---|
q.append(x) |
Добавить элемент x в конец дека | O(1) | O(1) |
q.appendleft(x) |
Добавить элемент x в начало дека | O(1) | O(1) |
q.pop() |
Вытащить последний элемент | O(1) | O(1) |
q.popleft() |
Вытащить первый элемент | O(1) | O(1) |
q.extend(t) |
Добавить все элементы t в конец дека | O(len(t)) | O(len(t)) |
q.extendleft(t) |
Добавить все элементы t в начало дека | O(len(t)) | O(len(t)) |
q.rotate(x) |
Сделать циклически сдвиг на x элементов | O(x) | O(x) |
q.remove(x) |
Удалить элемент x | O(n) | O(n) |
| Операция | Результат | В среднем | В худшем случае |
|---|---|---|---|
x in s |
Вхождение элемента x в s | O(1) | O(n) |
s | t |
Объединение множеств | O(len(s) + len(t)) | |
s & t |
Пересечение множеств | O(min(len(s), len(t))) | O(len(s) * len(t)) |
s1 & s2 & ... & sn |
Пересечение нескольких множеств | (n - 1) * O(l), l = max(len(s1), len(s2), ..., len(sn)) | |
s - t |
Разность множеств | O(len(s)) | |
s -= t |
Разность множеств, вычисляется в s | O(len(t)) | |
s ^ t |
Симметрическая разность | O(len(s)) | O(len(s) * len(t)) |
s ^= t |
Симметрическая разность, вычисляется в s | O(len(t)) | O(len(t) * len(s)) |
s.add(x) |
Добавить элемент x в s | O(1) | O(n) |
s.remove(x) |
Удалить элемент x из s, кидает ошибку, если элемента нет | O(1) | O(n) |
s.discard(x) |
Удалить элемент x из s, если он есть | O(1) | O(n) |
s.pop() |
Вытащить какой-то элемент из s | O(1) | O(n) |
s.clear() |
Удалить все элементы из s | O(n) | O(n) |
| Операция | Результат | В среднем | В худшем случае |
|---|---|---|---|
d[key] |
Взять элемент по ключу key | O(1) | O(n) |
d.get(key, default) |
Взять элемент по ключу key. Если его нет, взять default | O(1) | O(n) |
d[key] = value |
Присвоить элемент по ключу key | O(1) | O(n) |
del d[key] |
Удалить элемент по ключу key | O(1) | O(n) |
for key, value in d.items() |
Итерация | O(n) | O(n) |
key in d |
Проверка существования ключа key | O(n) | O(n) |