1. Задача
В первых уроках ты освоил основные инструменты: переменные (коробки для данных), циклы (повторение шагов) и выбор «если/иначе». Применять их можно так, что программа работает быстро, а можно так, что медленно. Big-O помогает отличить одно от другого.
Пока данных мало, быстрый и медленный способ одинаково мгновенны. Когда данных много, медленный способ может работать днями, а быстрый всё ещё заканчивает за миг.
В прошлом уроке ты искал имя среди миллиона двумя способами. Первый листал по одной странице: это до миллиона взглядов. Второй каждый раз отбрасывал половину: это около двадцати взглядов. Задача одна, а разница огромная.
Теперь дадим этим скоростям имя, чтобы говорить о них, не рисуя каждый раз таблицу. Это имя Big-O (читается «биг-о», то есть «большое O»). За этой записью стоит один вопрос: когда входных данных становится больше, насколько быстро растёт работа?
2. Простыми словами
Big-O показывает, насколько больше работы прибавится, когда данных станет больше.
Секунды и часы здесь не важны. Задай себе один вопрос: если данных станет вдвое больше, во сколько раз вырастет работа?
Пример с вечеринкой. Если каждый гость жмёт руку каждому, то при вдвое большем числе гостей рукопожатий станет примерно вчетверо больше. Для 10 гостей это 45 рукопожатий, для 20 гостей уже 190. Такая работа растёт быстро. А чтобы взять из списка гостей пятое имя по его номеру, хватит одного взгляда, хоть в списке 10 имён, хоть 10 000. Такая работа почти не растёт.
Big-O даёт каждому виду роста короткое имя. С ним медленный план видно заранее, ещё до того, как ты начнёшь его писать.
3. Идея
Big-O даёт росту имя. Обозначим размер входа буквой n: это просто «сколько у тебя элементов». Big-O говорит, как растёт работа, когда растёт n. Почти всё в этом курсе покрывают четыре имени:
- O(1): константа. Работа одна и та же при любом
n. Прочитатьlist[5]значит сделать один шаг, хоть в списке 10 элементов, хоть 10 миллионов. - O(log n): логарифм, то есть сколько раз
nможно разделить пополам, пока не останется 1. Работа почти не растёт. Это деление пополам из прошлого урока: миллион элементов, около двадцати шагов. - O(n): линейный рост. Ты смотришь на каждый элемент один раз, поэтому работа растёт вместе с данными. Вдвое больше данных, вдвое больше работы.
- O(n2): квадрат. Для каждого элемента ты снова проходишь по всем элементам. Для 1 000 элементов это 1 000 × 1 000 = миллион шагов. Вдвое больше данных, вчетверо больше работы. Такой способ начинает тормозить очень быстро.
Секундомер для этого не нужен. На быстром компьютере медленный способ просто станет чуть менее медленным. Big-O ещё до запуска говорит, какие способы справятся, когда данных станет много.
4. Прочитай ограничение, потом выбери форму
Здесь Big-O начинает приносить пользу. В условии задачи почти всегда сказано, насколько большим может быть вход. Это число подсказывает, какие способы подойдут:
| ограничение говорит | что можешь себе позволить |
|---|---|
n до нескольких тысяч |
O(n2): вложенный цикл (цикл внутри цикла) успеет |
n до миллиона |
O(n log n) или O(n): один проход, сортировка, поиск по ключу (Map, о нём позже) |
n до миллиарда |
O(log n) или формула: даже просмотреть каждый элемент уже не успеешь |
Таблицу можно читать и в обратную сторону, чтобы заранее поймать ошибку. Пусть n равно миллиону, а твой план это цикл внутри цикла. Миллион на миллион это триллион шагов, в отведённое время такая программа не уложится. Значит, ограничение ещё до первой строки кода говорит: нужен один проход по данным, два вложенных цикла не годятся.
Пример. Ночная задача обрабатывает 500 000 строк лога (журнала, куда программа записывает события). Вложенный цикл даст 500 000 × 500 000 = 250 миллиардов шагов, это безнадёжно. Сортировка с одним проходом даст около 500 000 × 19 ≈ 9,5 миллиона шагов, это нормально (19 здесь это log2 от 500 000). Значит, цель: O(n log n), и любую идею на O(n2) можно отбросить.
5. Где это встречается
Опытный инженер проверяет рост работы первым делом, когда задача «вдруг затормозила» после роста данных. Та же проверка нужна и в других случаях:
- оценить запрос к базе данных до того, как выкатить его в продакшен (рабочую систему, которой пользуются люди);
- решить, строить отчёт сразу или отправить его в фоновое задание;
- заметить на код-ревью (проверке кода коллегами) случайный вложенный цикл по большой таблице, пока он не уронил продакшен.
Прочитать размер входа и подобрать под него способ занимает пять секунд. Эта привычка спасает от того, чтобы написать не тот алгоритм и узнать об этом уже в продакшене. Весь остальной курс учит держаться на дешёвой стороне этой таблицы.
На LeetCode
Каждая задача на LeetCode пишет, каким большим может быть вход, поэтому сначала прочитай это ограничение. Если n не больше нескольких сотен или тысяч, хватит цикла внутри цикла, и эти задачи с ним проходят.
n не больше 100, поэтому проверка всех пар двумя вложенными циклами займёт около 5 000 шагов.
n не больше 500, поэтому сравнить каждое число со всеми остальными стоит 250 000 шагов, и это легко проходит.
n не больше 10^4, поэтому перебор всех пар, около 50 миллионов проверок, ещё проходит, а урок 18 решает её за один проход.
Почини сам (Tier 2)
В этом уроке ты ищешь ошибку в готовом коде. В редакторе есть функция predictComplexity(n). Она получает размер входа и возвращает самый медленный класс, который при таком размере ещё успеет, в виде строки вроде "O(n log n)". В коде квадрат пишут как "O(n^2)": значок ^ означает степень.
Код работает, но в нём одна специально оставленная ошибка: ошибка на единицу на границе. В одном месте стоит < (меньше) там, где нужно <= (меньше или равно). Из-за этого размер, который попадает ровно на границу, получает не тот класс.
Ты уже знаешь, где искать: в сравнениях с границами. Прочитай функцию, найди неверное сравнение, исправь его и снова запусти тесты. Один из тестов проверяет размер ровно на границе, поэтому сразу укажет на ошибку.
Для тех, кто уже пишет код. Это формализованная привычка читать ограничения. Если ты решал олимпиадные задачи, нового здесь нет. Польза в том, чтобы сделать автоматическим один ход: перевести
nв целевой класс до выбора подхода. Пролистай, исправь ошибку на единицу и иди дальше. Одно уточнение: это не бенчмарк. Бенчмарк меряет одну машину на одном входе в один день. Big-O говорит, что план на O(n2) для миллиона строк слишком медленный на любой машине, и запускать ничего не нужно.
Практика
predictComplexity
predictComplexity(n) -> string (one of "O(n^2)","O(n log n)","O(log n)")
// Step 09: Big-O and reading constraints. Tier 2: fix the bug left in on purpose.
//
// predictComplexity(n)
// n: input size
// returns one of "O(n^2)", "O(n log n)", "O(log n)": the slowest
// complexity class that still finishes in time for that input size
// (the table in the lesson).
//
// Bug: the boundary comparisons of predictComplexity have an off-by-one.
// One threshold uses `<` where it should use `<=`, so an input sitting
// exactly on that edge gets classified one class too fast. Find it, fix it.
//
// Run: node solution.test.js
export function predictComplexity(n) {
if (n <= 5000) return 'O(n^2)';
if (n < 1000000) return 'O(n log n)';
return 'O(log n)';
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.