Сложность алгоритмов и нотация Big-O
Big-O спрашивают все и всегда, но не таблицу наизусть. Проверяют две способности: оценить сложность собственного кода прямо во время написания и угадать по ограничениям задачи, какую сложность от тебя вообще ждут.
Типовые формулировки: «какая сложность у твоего решения?», «а по памяти?», «n до миллиона - твой квадрат пройдёт?».
// Вопрос «какая тут сложность» прозвучит после любой задачи лайвкодинга, это гарантия. Готовь ответ по ходу написания кода, а не когда спросят: пауза на подсчёт выглядит хуже, чем сам подсчёт.
Зачем считать рост, а не секунды
Время в секундах ничего не говорит: на другом ноутбуке оно другое, на другом языке тоже. Полезно другое - как время меняется, когда вход растёт. Big-O описывает именно это: верхнюю границу роста при увеличении n, размера входа (число элементов массива, длина строки, количество вершин графа).
Раз важен только рост, константы и младшие слагаемые выбрасываются: O(2n + 10) - это O(n), а O(n + n log n) - это O(n log n), потому что при больших n второе слагаемое перевешивает первое.
Чтобы почувствовать иерархию, прикинь на миллионе элементов, считая, что процессор делает порядка ста миллионов простых операций в секунду. O(n) - миллион операций, примерно сотая доля секунды. O(n log n) - двадцать миллионов, десятые доли секунды. O(n²) - триллион операций, около трёх часов. Между «мгновенно» и «не дождёшься» лежит один вложенный цикл.
// Логарифм в этой компании почти бесплатен: log₂ от миллиарда - это примерно 30. Алгоритм, делящий задачу пополам, справляется с миллиардом элементов за тридцать шагов, поэтому O(log n) на практике неотличим от константы.
- n
- размер входа. Обязательно проговори, что именно им называешь: у графа это может быть число вершин, число рёбер или и то и другое
Как оценить свой код за десять секунд
Правил ровно три, и их хватает почти всегда. Вложенный цикл - умножение сложностей. Последовательные блоки - сложение, а из суммы остаётся старший член. Деление задачи пополам на каждом шаге даёт логарифм.
Отдельная категория - операции, которые выглядят бесплатными, а на деле стоят целого прохода по данным. Срез списка копирует его целиком. Склейка строк в цикле каждый раз создаёт новую строку. Проверка «есть ли элемент в списке» перебирает список. Любая из них внутри цикла тихо превращает O(n) в O(n²), и в коде это не видно - там всего одна строчка.
Память считается теми же правилами, и рекурсия - это тоже память: глубина n означает O(n) стека вызовов, даже если внутри функции нет ни одной переменной.
// Правильная привычка - называть, какой случай оцениваешь. У быстрой сортировки в среднем O(n log n), а в худшем O(n²), и это два честных, но разных ответа.
- амортизированная сложность
- средняя цена операции на длинной серии. Добавление в динамический массив - O(1) амортизированно: изредка массив перевыделяется за O(n), но эта редкая трата размазывается по всем дешёвым добавлениям
- in-place
- алгоритм работает прямо во входном массиве и тратит O(1) дополнительной памяти. Сам вход при подсчёте доппамяти не считается
Обратный ход: от ограничений к решению
Приём, который экономит половину времени на лайвкодинге. Ограничения в условии - это подсказка про ожидаемую сложность, а сложность сужает выбор до двух-трёх приёмов.
Читается так. n до миллиона - ждут O(n) или O(n log n). n до пяти тысяч - пройдёт и O(n²). n до двадцати - можно честный перебор всех подмножеств, их всего миллион. Если в условии написано «n до 10⁵», квадратичное решение писать бессмысленно, даже если оно первым пришло в голову.
Обратный словарь тоже короткий. Нужна O(n log n) - думай про сортировку или кучу. Нужна O(n) - хеш-таблица, два указателя, один проход. Нужна O(log n) - бинарный поиск.
// Проговаривать этот ход вслух полезно вдвойне: интервьюер видит, что ты не угадываешь решение, а выводишь его из условия. Даже если конкретный алгоритм потом не сложится, ход мысли уже засчитан.
Как отвечать: «Поиск в хеш-таблице это O(1)? Всегда?»
O(1) в среднем и амортизированно, и вот эта оговорка и есть содержательная часть ответа. Хеш-функция раскладывает ключи по ячейкам, и пока таблица не слишком заполнена, в каждой ячейке лежит один-два элемента, поэтому операция стоит константу. Худший случай - все ключи попали в одну ячейку, из-за неудачных данных или плохой хеш-функции; тогда поиск вырождается в перебор и стоит O(n). Плюс отдельный сюжет с перестройкой: когда таблица заполняется, она пересоздаётся с большим числом ячеек за O(n), но эта редкая операция размазывается по остальным и потому не портит амортизированную оценку. Итоговая формулировка: O(1) в среднем, O(n) в худшем.
На одном примере разведены средний, худший и амортизированный случаи - ровно то, что этот вопрос и проверяет. Плюс объяснено, откуда берётся каждый из трёх.
На чём валят
- −Ответить «O(n + n log n)»: сумма отдаёт старший член, это просто O(n log n), а развёрнутая запись звучит как неуверенность.
- −Путать вложенные и последовательные циклы: первые перемножаются, вторые складываются.
- −Не заметить срез, склейку строк или проверку вхождения в список внутри цикла - там прячется лишний O(n).
- −Сказать «хеш-таблица это O(1)» без оговорок: при массовых коллизиях, когда разные ключи попадают в одну ячейку, поиск деградирует до перебора.
- −Забыть про память рекурсии: глубина n стоит O(n) стека, даже если сама функция пустая.
Проверьте себя
Пять вопросов из банка по этой подтеме. Всего их 22, остальные разбираются в тренажёре.
- Почему в O(2n) отбрасывают множитель и записывают её как O(n)?A)Потому что константу в асимптотике по определению считают равной единицеB)Потому что 2n и n дают одинаковое число операций на практикеC)При росте n класс роста задаёт старший член, а не постоянный множительD)Потому что умножать O(...) на число запрещено правилами нотации
показать ответ и разбор
+C)При росте n класс роста задаёт старший член, а не постоянный множитель// разбор: Асимптотика описывает поведение при n→∞. Постоянный множитель (2, 100) не меняет класс роста: 2n и n оба линейны, а n и n² — разные классы. Поэтому константы и младшие члены отбрасывают. Это не значит, что на практике множитель неважен — на фиксированном n он влияет на реальное время.
- Внешний цикл идёт по n, внутренний каждый раз до n, но с break в среднем на n/2. Какова сложность?A)O(n/2), потому что внутренний в среднем проходит половину входаB)O(n) — линейно, ведь есть breakC)O(n²) — константы и множитель 1/2 в асимптотике отбрасываютсяD)O(n log n)
показать ответ и разбор
+C)O(n²) — константы и множитель 1/2 в асимптотике отбрасываются// разбор: Внешний цикл n раз, внутренний в среднем n/2 → всего ≈ n·n/2 = n²/2 операций. В O-нотации множитель 1/2 отбрасывают: O(n²). break уменьшает константу, но не класс роста — он остаётся квадратичным. Ошибка новичка — записать «среднее» n/2 как класс O(n/2), которого не существует (это то же O(n)).
- Вход увеличили в 10 раз — время работы выросло примерно в 100 раз. Какая сложность у алгоритма?A)O(n²)B)O(n log n)C)O(2ⁿ)D)O(n)
показать ответ и разбор
+A)O(n²)// разбор: Сложность — это закон роста: у O(n²) вход в k раз больше → время в k² раз дольше, отсюда 10 → 100. Такой замер — рабочий способ прикинуть сложность чужого кода: прогнать на n и на 10n и сравнить. Типичный источник квадрата — вложенный цикл по тем же данным.
- Какая из операций выполняется за O(1)?A)поиск максимума в неотсортированном массивеB)чтение элемента массива по индексу arr[i]C)бинарный поиск в отсортированном массивеD)вставка элемента в начало массива
показать ответ и разбор
+B)чтение элемента массива по индексу arr[i]// разбор: Массив лежит в памяти непрерывно: адрес i-го элемента = начало + i × размер элемента, одна арифметическая операция при любом n. O(1) значит «не зависит от размера», а не «мгновенно»: у хеш-таблицы тоже O(1) в среднем, но константа больше, чем у чтения из массива.
- Функция перебирает все пары элементов массива вложенным циклом. Какая у неё сложность?A)O(n)B)O(n²)C)O(log n)D)O(n!)
показать ответ и разбор
+B)O(n²)// разбор: Для каждого из n элементов внешнего цикла — проход по n элементам внутреннего: n × n = n². На 10⁵ элементов это уже 10¹⁰ операций. Фраза «переберём все пары» на собесе — сигнал искать хеш, сортировку или два указателя, чтобы уйти от квадрата. Точнее пар n(n−1)/2, но константы нотация не различает.
дальше
Теорию прочитали. Навык ставится повторением
В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.