1. Введение

Бывало такое: пишешь фичу, проверяешь на локалке — всё летает за миллисекунды. С чистой совестью катишь в прод. А через месяц объемы данных вырастают, приходят реальные юзеры, и всё ложится. Процессор в сотке, логи забиты таймаутами, поддержка в огне.

Смотришь в код — вроде всё логично и красиво. Откуда тормоза?

Всё дело в масштабировании. Алгоритм, который легко переваривает 100 элементов, на миллионе записей может запросто превратиться в тыкву.

Именно для понимания таких моментов и нужна нотация Big O. И нет, это не академическая муть, которую зубрят только ради прохождения алгоритмической секции на собесе и сразу забывают. Это практический навык. Он нужен, чтобы еще на этапе написания кода понимать: «ага, вот этот кусок при росте нагрузки убьет нам сервер».

Ниже я на пальцах объясню, как оценивать сложность своих алгоритмов. Никакой зубодробительной математики и душных теорем. Только суть, чтобы раз и навсегда разобраться, почему код тормозит и как начать писать оптимально.

(Небольшая ремарка: умение писать быстрый код отлично дополняет навык писать код поддерживаемый. Если вы кодите на Python и хотите уверенно проектировать архитектуру приложений, залетайте на мой бесплатный курс «ООП Python: Часть 1» на Stepik. Спойлер: там тоже всё объясняется на пальцах).

А теперь погнали разбираться с классами сложности!

Уровень 1: Детский сад (Основы на пальцах)

Что такое Big O простыми словами?

Главная ошибка новичков — думать, что сложность алгоритма измеряется в секундах. Забудьте про секунды и миллисекунды. Ваш процессор мощнее моего, а код может быть написан на быстром C++ или на более медленном Python. Секунды не объективны.

Нотация Big O измеряет не время работы, а скорость роста этого времени (или потребления памяти) при увеличении объема входящих данных.

Грубо говоря, Big O отвечает на один простой вопрос: «Насколько всё станет хуже, если я подсуну скрипту не 10 элементов, а миллион?»

Аналогии из жизни

Чтобы было совсем понятно, давайте отвлечемся от кода:

• — Константное время. Представьте, что вы скачиваете фильм по прямой ссылке, чтобы посмотреть его вечером. Само действие «получить доступ к файлу» занимает фиксированное время. И совершенно неважно, посмотрите вы этот фильм один раз, десять или сто — на процесс скачивания (получения данных) это никак не повлияет. Время на выполнение задачи всегда одинаковое и не зависит от ваших дальнейших аппетитов.

• — Линейное время. А теперь вы решили прочитать книгу. Если в ней 100 страниц, вы справитесь за пару вечеров. Если 1000 страниц — уйдет пара недель. Время, которое вы потратите, растет строго пропорционально объему книги. Данных (страниц) стало в 10 раз больше — времени потребовалось в 10 раз больше. Это и есть линейный рост.

Главное правило клуба Big O

При оценке алгоритмов нас всегда интересует только худший сценарий развития событий (Worst-case scenario).

Представьте, что вы ищете конкретный договор в стопке из 500 бумаг. Вы можете вытянуть его первой же попыткой. Это лучший случай, здесь сложность . Радоваться можно, но закладываться на такое везение в архитектуре приложения нельзя.

Мы всегда должны исходить из того, что нужная бумага окажется в самом низу стопки, и нам придется перебрать все 500 штук (). Сервера ложатся именно от худших сценариев, а не от того, что в среднем всё работает нормально. Поэтому Big O — это всегда оценка «потолка» проблемы и общей тенденции роста нагрузки.

Уровень 2: Базовый лагерь (Основные классы сложности)

Для примеров возьмем старый добрый Python — он читается как псевдокод и понятен всем.

— Константное время

Идеальный алгоритм. Время выполнения вообще не зависит от того, сколько у вас данных. У вас в массиве 10 элементов или 10 миллиардов — операция выполнится за один и тот же шаг.

def get_first_element(items):
    return items[0] # Мы сразу берем то, что нужно. 

Сюда же относится чтение значения из хэш-таблицы (словаря) по ключу. Если ваш алгоритм работает за , можете смело просить повышение.

— Логарифмическое время: Разделяй и властвуй

Представьте, что вы ищете слово «Яблоко» в толстом бумажном словаре. Вы же не читаете его с первой страницы? Вы открываете словарь ровно посередине. Видите букву «М». Понимаете, что «Я» дальше, и смело отбрасываете всю первую половину книги. Потом открываете посередине оставшуюся часть… и так далее.

С каждым шагом объем данных уменьшается в два раза. Это и есть . Самый популярный пример — бинарный поиск по отсортированному массиву.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target: 
            return mid
        elif arr[mid] < target: 
            low = mid + 1
        else: 
            high = mid - 1
    return -1

Даже если в массиве миллиард элементов, бинарный поиск найдет нужное (или убедится, что его нет) всего за ~30 шагов. Это магия, которую нужно использовать при любой возможности.

— Линейное время: Честный трудяга

Сложность растет прямо пропорционально данным. Если элементов стало в 10 раз больше, алгоритм будет работать в 10 раз дольше. Типичный представитель — обычный цикл for.

Например, чтобы найти самое большое число в неотсортированном массиве, нам придется честно заглянуть в каждую ячейку:

def find_max(items):
    max_val = items[0]
    for item in items: # Проходим по всему массиву от начала до конца
        if item > max_val:
            max_val = item
    return max_val

— Линейно-логарифмическое время: Быстрые сортировки

Именно с такой сложностью работают нормальные сортировки «под капотом» языков программирования (Merge Sort, Timsort, Quick Sort в среднем случае).

Почему мы не можем сортировать за ? Чтобы отсортировать массив, нам недостаточно просто один раз посмотреть на каждый элемент. Нам нужно сравнивать их между собой. Математически доказано, что для универсальной сортировки сравнениями — это абсолютный предел скорости.

Грубо говоря, алгоритм разбивает массив на части () и делает проход по элементам ().

— Квадратичное время: Убийца серверов

Здесь начинаются проблемы. Если вы видите цикл внутри цикла по одним и тем же данным — у вас квадратичная сложность. Классический пример — сортировка пузырьком.

def bubble_sort(items):
    n = len(items)
    for i in range(n):
        for j in range(n - i - 1): # Вложенный цикл!
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]

Почему это страшно? Если у вас 1 000 элементов, алгоритм сделает 1 000 000 операций. Если 100 000 элементов — 10 миллиардов операций. То, что на тесте с десятком строк работало мгновенно, на реальных данных повесит базу или бэкенд намертво.

и — Экспонента и факториал: “Всё плохо, переписываем”

Это алгоритмы, время работы которых улетает в космос даже на микроскопических объемах данных.

часто встречается при неправильной рекурсии. Например, “наивный” расчет чисел Фибоначчи:

def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2) # Вызываем функцию дважды на каждый шаг

Уже при n = 50 этот код заставит ваш процессор дымиться, потому что количество вызовов удваивается на каждом шаге. (Решается добавлением кэширования — мемоизацией, что снижает сложность до ).

— это полный перебор всех возможных комбинаций. Например, классическая задача коммивояжера (найти кратчайший маршрут через N городов), решаемая “в лоб”.

Если ваш код в продакшене работает за или — вы либо гений, который решает NP-полную задачу для науки, либо вы ошиблись и этот код нужно срочно переписывать, пока не пришли пользователи.

Уровень 3: Продвинутый (Нюансы, на которых валятся джуны)

Здесь заканчивается базовая теория и начинается суровая реальность. Именно на этих правилах чаще всего сыпятся на технических собеседованиях и во время код-ревью.

Отбрасывание констант

Допустим, у вас есть массив, и вы проходите по нему циклом дважды: сначала чтобы найти минимум, а потом — максимум. Казалось бы, сложность . А если перед этим алгоритм делает 500 каких-то подготовительных операций с фиксированным временем? Выглядит как .

Но в мире Big O мы всегда отбрасываем константы. Правильный ответ в обоих случаях: .

Почему? Потому что Big O показывает тенденцию роста на бесконечности. Если у вас 10 миллионов пользователей, умножение на 2 или прибавление 500 не меняют сути — график времени выполнения всё равно останется прямой линией (линейная сложность). Для процессора разница между и — это доли миллисекунды, на архитектуру приложения это не влияет.

Отбрасывание менее значимых терминов

Представьте код: сначала идет двойной вложенный цикл по массиву, а затем обычный одинарный цикл по тому же массиву. Математически это .

Но по правилам Big O это превращается просто в . Мы оставляем только доминирующий фактор.

Давайте посчитаем: если , то . Одиночный цикл добавит к этому миллиону всего 1000 операций. Это жалкие 0.1% от общего времени работы. А если будет равно миллиону? Доля одиночного цикла станет вообще статистической погрешностью. Именно поэтому при анализе сложности мы смотрим только на самое «тяжелое» место в алгоритме.

Сложение vs Умножение (когда массивов несколько)

Классическая ловушка для новичков. Что делать, если на вход функции приходят два разных массива, и мы итерируемся по обоим?

• Два цикла подряд = . Если вы сначала прошлись по массиву A, а затем (независимо) по массиву B, время выполнения складывается. Называть это — ошибка, потому что массивы могут быть совершенно разных размеров.

• Вложенные циклы = . Если цикл по массиву B находится внутри цикла по массиву A, мы умножаем. Для каждого элемента из A мы полностью пробегаем массив B. Если в A 100 элементов, а в B 100 000, алгоритм сделает 10 миллионов шагов.

Best, Average и Worst case: суровая правда о Quick Sort

Обычно, когда говорят про Big O, имеют в виду худший сценарий (Worst case). Мы должны быть уверены, что при самом неудачном стечении обстоятельств сервер не взорвется. Но на практике разработчики часто оперируют средним временем работы (Average case, в академической среде обозначается как Big Theta — ).

Самый яркий пример — алгоритм быстрой сортировки (Quick Sort). В среднем (и в лучшем) случае он работает за отличные . Именно поэтому он так популярен и лежит под капотом многих встроенных функций сортировки в языках программирования.

Но у него есть темная сторона. Если вы скормите базовому алгоритму Quick Sort уже отсортированный массив, а опорный элемент (pivot) будет выбираться неудачно, алгоритм скатится в худший сценарий — .

Понимание этой разницы отличает джуна от мидла. Джун скажет: «Quick Sort — это всегда ». Мидл ответит: «В среднем да, но в худшем случае мы получим , поэтому нужно с умом выбирать опорный элемент».

Уровень 4: Мастер (Для тех, кто хочет знать всё)

Пространственная сложность (Space Complexity): Не процессором единым

До сих пор мы говорили только про время работы процессора. Но оперативная память (RAM) — ресурс не менее ценный, и она имеет свойство заканчиваться в самый неподходящий момент.

Нотация Big O абсолютно так же применяется для оценки того, сколько дополнительной памяти «сожрет» ваш алгоритм при росте объема данных. Это называется Space Complexity.

Представьте, что вам нужно перевернуть массив (сделать reverse).

• Плохо (Space ): Вы создаете внутри функции новый пустой массив, проходитесь циклом по старому с конца в начало и копируете элементы в новый. Вы только что удвоили потребление памяти. Если исходный массив весил 1 ГБ, ваш скрипт попросит у системы еще 1 ГБ.

• Хорошо (Space ): Вы делаете это алгоритмом In-place («на месте»). Вы берете первый и последний элементы текущего массива и просто меняете их местами, сдвигаясь к центру. Вам понадобилась всего одна дополнительная переменная для временного хранения значения при обмене. Сколько бы данных ни было — 10 штук или 10 миллионов — алгоритм потребует фиксированный минимум памяти.

На серверах с жесткими лимитами (например, в AWS Lambda или дешевых контейнерах) понимание разницы между и по памяти буквально спасает от падений с ошибкой Out of Memory.

Амортизационная сложность (Amortized Time

Это настоящая жемчужина теории сложности. Концепт, который объясняет то, что на первый взгляд кажется противоречием.

Возьмем обычный динамический массив (тот самый list в Python, ArrayList в Java, vector в C++). Мы привыкли считать, что добавление элемента в конец массива с помощью метода push() или append() работает мгновенно — за константное время .

Но давайте заглянем под капот. На уровне железа динамический массив — это непрерывный кусок памяти фиксированного размера. И когда-нибудь этот кусок заполняется до краев. Что происходит в этот момент при вызове push()?

1. Система выделяет где-то в памяти новый кусок, обычно в 2 раза больше старого.

2. Программа берет все существующие элементы и по одному переносит их в новый массив.

Это копирование занимает честное линейное время — . Получается, иногда push() работает долго! Так почему же во всей документации пишут, что сложность добавления в динамический массив — ? Нам врут?

Нет. Здесь вступает в игру амортизационная сложность.

Да, операция расширения очень дорогая (). Но фокус в том, что по мере роста массива она происходит всё реже и реже.

Представьте аналогию: каждый день вы покупаете кофе за 2 доллара (это наша быстрая операция ). Но раз в месяц вам нужно купить проездной на метро за 60 долларов. В день покупки проездного ваши траты резко улетают в космос (наша тяжелая операция ). Однако, если мысленно «размазать» стоимость проездного по всем дням месяца, окажется, что в среднем ваши ежедневные расходы выросли всего на пару долларов.

В программировании то же самое. Если распределить (амортизировать) затраты времени на одно редкое копирование по тысячам мгновенных вставок, то математически доказано: «в среднем по больнице» стоимость одного добавления остается константной — .

Понимание таких нюансов — это именно то, что отличает разработчика, который просто пишет код, от инженера, который понимает, как этот код работает на уровне железа.

Заключение

Чек-лист: как анализировать свой код (шпаргалка)

Чтобы не гадать, сломается ли ваш код под нагрузкой, просто пробегитесь по этому чек-листу перед тем, как делать коммит:

• Нет циклов и рекурсий? Поздравляю, скорее всего, это .

• Один цикл (или несколько, но друг за другом)? Это . Всё хорошо, алгоритм масштабируется предсказуемо.

• Цикл внутри цикла по одним и тем же данным? Это . Внимание, красная тревога! Если данных будет больше пары тысяч, начнутся тормоза.

• Используете встроенные методы сортировки? Заложите в уме сложность .

• Используете оператор in (или contains) внутри цикла? Помните: поиск по массиву (list) — это скрытый цикл, то есть . Если завернуть его в ваш цикл, получите . Поиск по хэш-таблице (dict или set) — это . Замена массива на множество часто спасает продакшен!

• Константы? Отбрасываем. — это всё тот же . Смотрите только на самое «узкое» место алгоритма.

Анонсы новых статей, полезные материалы, а так же если в процессе у вас возникнут сложности, обсудить их или задать вопрос по этой статье можно в моём Telegram-сообществе. Смело заходите, если что-то пойдет не так, — постараемся разобраться вместе.