Big O простыми словами

Короткий ответ. Big O отвечает на один вопрос. Вход вырос вдвое, что стало с работой? При O(1) работа не меняется, при O(log n) растёт на один шаг, при O(n) удваивается, при O(n²) растёт вчетверо. Константы отбрасывают, потому что на больших входах важна только скорость роста.

Вся идея Big O в этом. Остальное нотация.

Пять форм

Удвой вход, и:

• O(1): работа не меняется. Обращение по индексу. Взятие по ключу.
• O(log n): работа выросла на один шаг. По миллиону это 20 шагов. По двум миллионам 21.
• O(n): работа удвоилась. Один проход по всему.
• O(n log n): чуть больше, чем удвоилась. Любая нормальная сортировка.
• O(n²): работа выросла в четыре раза. Все пары.

Пять строк. Они покрывают почти всё, что встретится до университетского уровня. Какую из них разрешает размер входа, собрано в таблице сложности алгоритмов.

Каждый термин отсюда есть в глоссарии.

Полная таблица по структурам данных это Big-O cheat sheet.

Почему константы выбрасывают

Цикл, который делает три действия на элемент, это O(n). Ровно как и тот, что делает одно.

Ощущается неправильно. В три раза медленнее это в три раза медленнее.

Big O отвечает на другой вопрос. Как это ведёт себя при неограниченном росте входа?

Тройка остаётся тройкой всегда. Переход от n к n² убегает.

При миллионе это 3 миллиона шагов против триллиона. Константа перестаёт быть интересной.

Как считать по своему коду

Три правила закрывают почти всё.

Цикл по входу это n. Цикл внутри цикла это n². Вложенность умножает.

Деление пополам это log n. Каждый проход выбрасывает половину оставшегося.

Деление пополам работает как бинарный поиск. Поэтому же быстры сбалансированные деревья.

Последовательные шаги складываются, а сложение оставляет большее. Сортировка плюс проход это n log n плюс n. То есть n log n.

Ловушка это скрытый цикл.

Метод, который сканирует строку внутри цикла, делает всё квадратичным. Вторых скобок на экране нет.

Вызвал что-то внутри цикла, спроси, сколько оно стоит.

С памятью так же

Тот же вопрос про память. Вход вырос вдвое, сколько ты хранишь дополнительно?

Пара переменных это O(1). Копия входа это O(n). Таблица всех пар это O(n²).

На практике память кончается именно на ней.

Интервьюеры спрашивают обе оценки. Ответишь только про время, потеряешь заработанный балл.

Сказать оценку памяти это разговор вслух.

Где нотация врёт

Две честные оговорки.

На малых размерах побеждают константы.

Сортировка вставками обгоняет быструю примерно до 20 элементов. Настоящие реализации на дне переключаются на неё.

Раскладка в памяти тоже важна. Проход по массиву быстрее прохода по списку той же длины.

Оба O(n). Один лежит в кеше, другой нет.

Big O выбирает алгоритм. Измерение выбирает реализацию. Нужны оба, и отвечают они на разные вопросы. Калькулятор Big O замерит твою функцию на растущих входах и назовёт её класс.

Где это в треке

В AlgoPath сложность стоит на шаге 08 «Почему одни способы быстрее», до всех паттернов.

Дальше каждый шаг называет свою цену и ждёт, что ты её прочитаешь.

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

Первые 33 шага бесплатные.