Сложность алгоритма простыми словами

Автор: Казачкин Даниил Михайлович · Обновлено 23 августа 2026 г.

Сложность описывает рост работы при увеличении размера входа. В Python один проход по списку обычно требует порядка n шагов, два независимых прохода — 2n и относятся к тому же…

Сложность описывает рост работы при увеличении размера входа. В Python один проход по списку обычно требует порядка n шагов, два независимых прохода — 2n и относятся к тому же линейному росту, а вложенный полный перебор пар — порядка n².

Считаем фактические сравнения

numbers = [7, 2, 9, 4]
target = 9
checks = 0

for number in numbers:
    checks += 1
    if number == target:
        break

print(checks)

Ожидается 3: поиск остановился на третьем элементе. В худшем случае, когда значения нет, проверок будет len(numbers).

Время зависит не только от Big O

Маленькие данные скрывают разницу, а встроенные операции Python могут быть быстрее самописных благодаря реализации на C. Оценка роста не заменяет измерение, но помогает заранее исключить алгоритм, который делает миллиарды шагов. Не объявляйте программу «быстрой» по одному запуску без одинаковых входов.

Операция value in list выполняет последовательный поиск, а value in set обычно имеет постоянную среднюю стоимость. Создание множества само требует прохода и памяти, поэтому оно выгодно при множестве повторных проверок, а не обязательно при одной.

Эксперимент с двумя размерами

Напишите счётчик итераций для одного цикла длины n и для пары вложенных циклов n × n. Запустите с n = 10 и n = 100. Ожидаются 10/100 и 100/10000 итераций. Не измеряйте только секунды: сначала подтвердите математический рост числом операций. Затем объясните, почему два последовательных цикла по n не превращаются в n².

Оценка до оптимизации

Для задачи о повторных проверках присутствия реализуйте два варианта: каждый раз искать в списке и один раз построить множество. Посчитайте число элементов и число запросов, прежде чем ожидать ускорение. Измерьте обе версии через time.perf_counter на достаточно большом, одинаковом наборе, повторив запуск несколько раз. Не включайте печать в измеряемый участок. Сравните память и время подготовки множества. Итог должен быть условным: при одном запросе простая версия может быть разумнее, при тысячах запросов индекс окупается. Оптимизация начинается с модели нагрузки и измерения, а не с замены синтаксиса на более сложный.

Практикум: измерение двух способов проверки

Сравните тысячу запросов принадлежности к списку и к множеству из ста тысяч чисел. Отдельно измерьте построение множества и сами проверки через time.perf_counter. Повторите опыт несколько раз на одинаковых данных, не печатая внутри участка. Затем выполните только один запрос и объясните, почему подготовка множества может не окупиться. Запишите вывод условно: выбор зависит от числа элементов, количества запросов и памяти. Оценка сложности должна предшествовать измерению.

Контрольная точка

Какой параметр нагрузки изменяет решение сильнее всего: длина коллекции или число повторных запросов? Составьте грубую модель стоимости подготовки и дальнейшей проверки.

Частые вопросы

Микросекунды одного запуска доказывают скорость алгоритма?

Нет. На единичный замер влияют прогрев, система и фоновые процессы. Сначала сравнивают рост алгоритмов, затем повторяют измерение на репрезентативных данных и рассматривают устойчивую статистику.