Понять Big O раз и навсегда

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] # Мы сразу берем то, что нужно.

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

$O(\log N)$ — Логарифмическое время: Разделяй и властвуй

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

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

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

$O(N \log N)$ — Линейно-логарифмическое время: Быстрые сортировки

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

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

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

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

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

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, время выполнения складывается. Называть это — ошибка, потому что массивы могут быть совершенно разных размеров.
Вложенные циклы = $O(A \times 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 — $\Theta$ ).

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

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

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

Уровень 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()?

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

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

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

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

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

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

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

Заключение

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

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

Нет циклов и рекурсий? Поздравляю, скорее всего, это .
Один цикл (или несколько, но друг за другом)? Это . Всё хорошо, алгоритм масштабируется предсказуемо.
Цикл внутри цикла по одним и тем же данным? Это . Внимание, красная тревога! Если данных будет больше пары тысяч, начнутся тормоза.
Используете встроенные методы сортировки? Заложите в уме сложность $O(N \log N)$ .
Используете оператор in (или contains) внутри цикла? Помните: поиск по массиву (list) — это скрытый цикл, то есть . Если завернуть его в ваш цикл, получите . Поиск по хэш-таблице (dict или set) — это . Замена массива на множество часто спасает продакшен!
Константы? Отбрасываем. $O(100 \times N + 5000)$ — это всё тот же . Смотрите только на самое «узкое» место алгоритма.

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

ссылка на оригинал статьи https://habr.com/ru/articles/1030772/