Сложность операций: O-нотация, посчитанная на встроенных типах

База: что говорит O-нотация

Здесь n — число элементов коллекции, а работа — число сравнений элементов (у append и insert — копирований ссылок), а не время.

Ответ уровня Junior на «что такое O(n)»: это то, как растёт время работы алгоритма с ростом размера входа; константы и младшие слагаемые отбрасывают. Строже: O(f(n)) — асимптотическая верхняя оценка в выбранной модели стоимости: начиная с некоторого n работа не больше c·f(n). Поэтому линейная функция формально и O(n), и O(n²); тесную оценку — растёт ровно как f(n) с точностью до множителя — пишут Θ(f(n)), и на собеседовании под «O(n)» обычно имеют в виду именно её. Это верно, и за этим ответом обычно идут уточнения: какая сложность у конкретных операций списка и множества, что значит «амортизированное» и где квадрат прячется в коде, который выглядит линейным. Механизмы ниже отвечают на них счётом.

Как устроена проверка: элементы — объекты, которые считают вызовы своих __eq__ и __lt__. Для перебора, двоичного поиска и сортировки число сравнений и есть мера работы. От скорости машины оно не зависит и совпало на CPython 3.11–3.14, но это наблюдение реализации для этих объектов, а не контракт языка: другие данные — например, совпадающие хеши — дают другой счёт. Вычисление хеша в счёт не входит, и одно сравнение — не одна машинная операция: у длинных строк и hash, и == проходят по символам (раздел «Глубже: цена одного сравнения»).

Механизм 1: поиск — O(n), O(1) и O(log n) в числах

Вывод bench/complexity/basics.py, раздел 1:

1) поиск: сколько сравнений, искомый элемент последний
         n   x in list  x in set  bisect  log2(n)
        10          10         1       3      3.3
       100         100         1       7      6.6
      1000        1000         1      10     10.0
     10000       10000         1      13     13.3
    100000      100000         1      17     16.6
   bisect на неотсортированном [5, 1, 4, 2, 3], ищем 1: индекс 0, а 1 стоит на месте 1 — ошибки нет

Три столбца — три вида роста:

• x in list — O(n). Перебор сравнивает элементы по очереди, и сравнений ровно n, когда искомый последний.
• x in set — O(1) в среднем. Множество вычисляет хеш, идёт в нужную ячейку и сравнивает элемент с теми, у кого тот же хеш. У Key из прогона хеши разных значений не совпадают, поэтому __eq__ вызвался один раз — при десяти элементах и при ста тысячах. Это наблюдение для этого набора, а не свойство множества: ниже — тот же поиск, когда хеш у всех один.
• bisect — O(log n). Двоичный поиск по отсортированному списку каждым сравнением отбрасывает половину. n выросло в десять тысяч раз, а сравнений стало на 14 больше — столбец идёт вровень с log2(n).

Если хеш у всех элементов один — вывод bench/complexity/basics.py, раздел 6:

6) множество, у всех элементов один и тот же хеш: вызовов __eq__
         n  обычные хеши  один хеш: поиск  один хеш: построение
        10             1               10                    45
       100             1              105                  5982
      1000             1             1336                605201
     10000             1            11672              57720235
   тот же опыт с хешем 0 вместо 1, n = 100: поиск — 114
   обычные хеши, искомый — тот же объект, а не равный ему: поиск — 0

С одним хешем на всех поиск последнего вызвал __eq__ 105 раз на ста элементах и 11 672 на десяти тысячах — порядка n: это худший случай множества, O(n). Вызовов даже больше n — значит, часть элементов множество сравнило повторно; точное число зависит от самого значения хеша: с нулём вместо единицы — 114. Построение такого множества стоит порядка n²/2 сравнений. А элемент, найденный по тождеству — тот же объект, а не равный ему, — __eq__ не вызывает вовсе. Поэтому «O(1) в среднем» не значит «одно сравнение», а сами счётчики __eq__ — наблюдение CPython, а не обещание языка.

bisect — модуль стандартной библиотеки, и его условие записано прямо в строке документации bisect_left: return the index where to insert item x in list a, assuming a is sorted (вернуть индекс, на который надо вставить x в список a, считая, что a отсортирован). Отсортированность — обязанность того, кто вызывает: на неотсортированном списке bisect вернёт неверный индекс без ошибки — последняя строка прогона выше. Поэтому O(log n) поиска стоит рядом с O(n log n) сортировки: двоичный поиск окупается, когда список сортируют один раз, а ищут в нём много раз.

И ещё одно: bisect_left возвращает позицию вставки, а не ответ «есть ли элемент». 17 сравнений в таблице выше — только __lt__ до этой позиции. Найден ли элемент, решает отдельная проверка: позиция внутри списка и элемент на ней равен искомому — i < len(a) and a[i] == x. Вывод bench/complexity/basics.py, раздел 7:

7) bisect: позиция вставки ещё не «нашли» — нужна проверка после неё
   ищем  199998 в 0, 2, 4, …, 199998: позиция  99999, __lt__ — 17, __eq__ — 1, найден: True
   ищем   77777 в 0, 2, 4, …, 199998: позиция  38889, __lt__ — 17, __eq__ — 1, найден: False
   ищем  200001 в 0, 2, 4, …, 199998: позиция 100000, __lt__ — 16, __eq__ — 0, найден: False

Для 77 777, которого в списке нет, bisect_left всё равно вернул позицию — там стоит 77 778; без проверки равенства это выглядело бы как находка. Для 200 001 позиция равна длине списка, и сравнивать не с чем — отсюда проверка границы.

То же в коротком примере, который можно скопировать. Полный файл bench/complexity/find.py:

import bisect
import sys
 
print("PY", sys.version.split()[0])
 
 
def contains(a, x):
    i = bisect.bisect_left(a, x)
    return i < len(a) and a[i] == x
 
 
a = [2, 4, 6, 8]
for x in (6, 5, 9):
    print(f"x = {x}: bisect_left -> {bisect.bisect_left(a, x)}, contains -> {contains(a, x)}")

Запуск — python3.13 bench/complexity/find.py; вывод на CPython 3.13.7 (на 3.11, 3.12 и 3.14 — тот же, кроме строки версии):

PY 3.13.7
x = 6: bisect_left -> 2, contains -> True
x = 5: bisect_left -> 2, contains -> False
x = 9: bisect_left -> 4, contains -> False

Для 6 и для 5 позиция одна и та же — 2; отличает их только проверка равенства.

Механизм 2: append — амортизированное O(1)

Список хранит ссылки на элементы в одном куске памяти. Когда место кончается, нужен кусок больше, и все ссылки, возможно, придётся скопировать — это O(n). Если бы так было на каждом append, n добавлений стоили бы O(n²). Поэтому CPython выделяет память с запасом; прогон ловит каждое перевыделение по изменению sys.getsizeof — вывод bench/complexity/basics.py, раздел 2:

2) append: сколько раз список перевыделял память
   первые ёмкости (мест под элементы): [4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128]
      1000 append — перевыделений: 28
     10000 append — перевыделений: 47
    100000 append — перевыделений: 66

Ряд ёмкостей совпадает с комментарием в исходниках CPython — 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... — и там же сказано, зачем он такой: запаса is enough to give linear-time amortized behavior over a long sequence of appends() (хватает, чтобы длинная последовательность append() в сумме занимала линейное время). Запас растёт вместе с размером, поэтому на сто тысяч append пришлось 66 перевыделений, а не сто тысяч.

Это и называется амортизированным O(1): отдельный append изредка дорогой — он может скопировать весь список, — но в сумме n добавлений стоят O(n), то есть O(1) в среднем на одно. Ответ «append — это O(1)» верен, но с оговоркой, которую ждут: в худшем случае отдельный вызов — O(n).

Механизм 3: рост времени — то же, но по часам

O-нотация предсказывает, во сколько раз вырастет время, если n вырастет в десять раз: O(1) — примерно никак, O(n) — примерно в десять. Замер на трёх размерах — вывод bench/complexity/cost.py (CPython 3.13.7):

нс на операцию, медианы 7 кругов
   операция                      1000       10000      100000     ×10    ×100
   list.append                   35.1        26.3        28.4     0.8     0.8
   list.insert(0, x)            308.2      2242.9     19988.0     7.3    64.9
   x in list                   5332.6     52136.7    643060.2     9.8   120.6
   x in set                      25.4        27.2        26.2     1.1     1.0
   sorted(), на элемент         106.7       127.0       220.3     1.2     2.1

• append и x in set — время на операцию не растёт: это O(1) (амортизированное и среднее; у x in set здесь целые без коллизий).
• insert(0, x) и x in list — растут почти в десять раз на каждые ×10: O(n). insert(0, x) сдвигает все элементы, x in list перебирает их.
• sorted() на элемент растёт медленно — в 1,2 раза на ×10: это множитель log n из O(n log n).

Числа не ложатся на предсказание точно. У insert(0, x) — 7,3 вместо 10, но это свойство замера: за тысячу вставок список дорастает до n + 1 000, и средняя длина — 1 500 и 10 500, отношение которых около 7. У sorted() на ×100 — 2,1 вместо ожидаемых по логарифму 1,7. O-нотация отбрасывает постоянные расходы и ничего не говорит о том, что происходит в железе; она описывает форму роста, а не точное время. Поэтому на собеседовании говорят «растёт линейно», а не «в десять раз медленнее».

Механизм 4: скрытый квадрат

Самый частый вопрос «оцените сложность» — про код, где цикл не виден. [x for x in a if x in b] выглядит как один проход по a. Но если b — список, каждый x in b — тоже проход. Вывод bench/complexity/basics.py, раздел 3:

3) скрытый квадрат: [x for x in a if x in b], общих элементов нет
         n    b — список   b — множество
       100         10000               0
      1000       1000000               0

n выросло в десять раз — сравнений стало в сто раз больше: это O(n²). С множеством b вызовов __eq__ нет вовсе: хеши элементов a не совпадают ни с одним хешем в множестве, а __eq__ вызывается только при совпадении хеша. Построение множества — O(n) в среднем, поиск — O(1) в среднем на элемент, итого O(n); при совпадающих хешах обе оценки хуже (раздел 6 выше).

Где ещё прячется квадрат: lst.remove(x) или lst.index(x) в цикле по другой коллекции — for x in to_delete: lst.remove(x), — lst.insert(0, x) в цикле, x in lst для отбора уникальных. Правило оценки одно — умножить число итераций цикла на стоимость операции внутри него.

Глубже: сортировка и n − 1 сравнений

Вывод bench/complexity/basics.py, раздел 4:

4) sorted(): сколько сравнений
         n  случайные   lg(n!)  n·log2(n)  отсортированные  обратные
      1000       8655     8529       9966              999       999
     10000     120184   118458     132877             9999      9999
    100000    1531824  1516704    1660964            99999     99999

На случайных данных сравнений около n·log2(n) — это O(n log n). Колонка lg(n!) — теоретический минимум: никакая сортировка сравнениями не может в среднем обойтись меньшим числом. Сортировка CPython на 3.13 отстаёт от него на 1–1,5 %.

А на уже отсортированных и строго убывающих данных в прогоне вышло ровно n − 1 сравнений, O(n). Это наблюдение на таком упорядоченном входе и этой реализации, а не обещание языка; объясняет его устройство сортировки: сортировка CPython ищет во входе готовые упорядоченные участки, убывающие разворачивает и сливает их; если весь вход — один такой участок, достаточно один раз пройти по нему. Поэтому ответ «sorted() работает за O(n log n)» верен для худшего и среднего случая, а лучший — O(n).

Глубже: цена одного сравнения

Весь урок считает сравнения, как будто каждое стоит одинаково. Для целых это близко к правде, для строк — нет: хеш и проверка равенства проходят по символам. Вывод bench/complexity/strkeys.py (CPython 3.13.7):

строковые ключи: нс на операцию, медианы 7 кругов
   операция                            10        1000      100000
   hash(новой строки)                35.3       431.8     29768.6
   hash(той же строки)               34.6        34.6        30.1
   a == b, разные объекты            21.3        36.0      2567.6

Хеш новой строки в сто тысяч символов — около 30 мкс, в десять символов — 35 нс; сравнение двух равных, но разных строк тоже растёт с длиной. Повторный хеш той же строки дёшев при любой длине: строка запоминает его в себе (поле hash в Include/cpython/unicodeobject.h:101, CPython 3.13.7). Поэтому «поиск в множестве — O(1)» — это O(1) по числу элементов, а цена одной проверки зависит от ключа: новую длинную строку надо захешировать, а равную ей, но другую — сравнить посимвольно.

Как отвечать на собеседовании

Короткий ответ: O-нотация описывает, как растёт работа с ростом входа; строго это верхняя оценка. x in list, insert(0, x), remove — O(n); x in set, d[key] — O(1) в среднем и O(n) в худшем случае, когда хеши совпадают; append — амортизированное O(1); bisect — O(log n); sorted() — O(n log n) в среднем и худшем случае. Сложность кода — это число итераций, умноженное на стоимость операции внутри.

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

На «оцените [x for x in a if x in b]». «Если b список — O(n·m): каждый in перебирает b. У меня на тысяче элементов вышел миллион сравнений. Сделать b множеством — и будет O(n + m)».

На «почему append — O(1), если список иногда копируется». «Он растёт с запасом, пропорциональным размеру. На сто тысяч append было 66 перевыделений. Дорогие вызовы редки, в сумме — O(n), то есть O(1) в среднем. Это и есть амортизированная сложность».

На «какая сложность у sorted()». «O(n log n) в среднем и худшем случае. На уже отсортированных данных — O(n): у меня было ровно n − 1 сравнений, сортировка CPython находит готовые участки».

На «почему двоичный поиск быстрый». «Каждое сравнение отбрасывает половину: на ста тысячах элементов — 17 сравнений вместо ста тысяч. Но список должен быть отсортирован, а сортировка — O(n log n), так что это выгодно при многих поисках. И bisect_left даёт позицию вставки — найден ли элемент, проверяю отдельно: i < len(a) and a[i] == x».

На «x in set — это одно сравнение?» «В среднем O(1), но не одно сравнение по определению. В моём прогоне у ключей без коллизий так и было, а когда хеш у всех ста элементов один, поиск вызвал __eq__ 105 раз — худший случай O(n). Это счётчик CPython, не гарантия языка».

Дальше спросят

5) словарь, у всех ключей один и тот же хеш: сравнений на поиск последнего ключа
   n =    10: обычные хеши — 1, один хеш на всех — 10
   n =   100: обычные хеши — 1, один хеш на всех — 100
   n =  1000: обычные хеши — 1, один хеш на всех — 1000

Частые заблуждения

История версий

Практика

Две задачи. Сначала ответьте, потом сверьтесь с настоящим выводом: в обеих правильный ответ взят из прогона скрипта, а не назначен.

n = 100
count = 0
for i in range(n):
  for j in range(i + 1, n):
      count += 1
print(count)

4950

10000

5000

100

Проверьте себя

Чем измерено

Числа этого урока получены этими скриптами. Каждый открывается прямо отсюда — вместе с записью прогона: на чём считали, что получилось и с каким разбросом.

Счёт сравнений — CPython 3.11.15, 3.12.3, 3.13.7 и 3.14.7; замеры времени — 3.13.7 и 3.14.7 на одной машине с двумя ядрами. Разделы 6–7 bench/complexity/basics.py, bench/complexity/strkeys.py и bench/complexity/find.py добавлены и запущены 14.10.2026 на linux/x86_64. Контракты и цитаты сверены 14.10.2026. Python 3.15 (вышел 9 октября 2026) урок не запускал.

• bench/complexity/basics.py
• bench/complexity/cost.py
• bench/complexity/strkeys.py
• bench/complexity/find.py
• bench/complexity/practice.py