Алгоритмы с нуля
Мышление и сложность: тест с выбором ответа
Суть Тест с выбором на синтез по всему юниту — доминирующий член, классы Big-O, компромисс время-память и чтение ограничений для выбора подхода.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов поперёк всего юнита. Ни один из них — не определение для заучивания: каждый отражает решение, которое ты принимаешь, оценивая алгоритм ещё до того, как его запустишь.
Цель
Убедись, что связываешь подсчёт шагов, Big-O, классы сложности, компромисс время-память и входные ограничения в одно суждение: вот код и вот лимиты — сколько это стоит и достаточно ли быстро?
Викторина
Completed
Алгоритм выполняет ровно 5n + n²/2 + 1000 базовых операций на входе размера n. Какова его Big-O и почему?
Heads-up Big-O отбрасывает константные множители. 1/2 не меняет, как масштабируется стоимость при удвоении n, поэтому O(n²/2) и O(n²) — один класс; пишем простейшую форму, O(n²).
Heads-up Члены младшего порядка отбрасываются, а не суммируются в нотации. При больших n n² подавляет n, поэтому член n пренебрежим, и ответ — просто O(n²).
Heads-up Big-O — про рост при больших n, а не про значение при малых. +1000 — фиксированная стоимость, которая никогда не растёт, поэтому она исчезает против n² для любого заметного входа.
Викторина
Completed
В задаче указано n ≤ 1 000 000 при лимите в 1 секунду. Твоя первая идея — вложенный цикл O(n²). Прочитай ограничение — что оно говорит ещё до написания кода?
Heads-up Никакая настройка констант не закроет разрыв в 10 000 раз. Когда ограничение исключает класс сложности, меняют алгоритм, а не константы.
Heads-up Граница входа n прежде всего ограничивает бюджет времени: ~10⁸ опер/сек × лимит. n ≤ 10⁶ напрямую отображается в «требуется O(n log n) или лучше».
Heads-up Полиномиальный — не автоматически реализуемый. O(n²) полиномиален и всё равно 10¹² операций здесь — далеко за бюджетом. Граница выбирает конкретный класс, а не просто «полином против экспоненты».
Викторина
Completed
Чтобы найти дубликат, можно взять вложенный цикл (время O(n²), память O(1)) или hash set (время O(n), память O(n)). На сервере с запасом памяти и пользователями, ждущими ответ, что выберешь и почему?
Heads-up Меньше памяти лучше только когда память — связывающее ограничение (embedded, мобильные). Здесь памяти вдоволь, а задержка важна, поэтому обмен памяти на ускорение O(n²)→O(n) — верный выбор.
Heads-up Неодинаковая. Вложенный цикл — O(n²); hash set — O(n). Для больших n это разница между триллионом и миллионом операций.
Heads-up Наоборот: hash set использует БОЛЬШЕ памяти (O(n) против O(1)). Его выбирают несмотря на лишнюю память, потому что он покупает большую экономию времени — это и есть компромисс.
Викторина
Completed
В функции один цикл, выполняющийся n раз, и внутри него вызывается бинарный поиск (O(log n)) по отсортированному массиву. Какова её сложность по времени?
Heads-up Сложности складывают только для последовательных независимых фаз. Здесь поиск ВНУТРИ цикла, поэтому выполняется по разу на итерацию — стоимости перемножаются, давая O(n log n).
Heads-up log n не константа; он растёт с n (медленно). Его нельзя свести к O(1). Работа O(log n) на итерацию через n итераций — это O(n log n).
Heads-up Квадратичность даёт цикл, чья внутренняя работа O(n), то есть ещё один полный проход по n. Здесь внутренняя работа O(log n), а не O(n), поэтому это O(n log n), много ниже O(n²).
Викторина
Completed
Джуниор пишет largestOf с `let largest = 0` вместо `let largest = numbers[0]`, тестирует на нескольких списках из положительных чисел и выкатывает. Какой более глубокий урок, когда функция возвращает 0 для [-5, -3, -1]?
Heads-up Инициализация не меняет число шагов; цикл всё равно делает n−1 итераций. Это баг корректности, а не сложности — функция возвращает неверный ответ.
Heads-up Полностью отрицательные списки — допустимые входы, которые спецификация обязана покрывать. Аргумент через инвариант цикла ловит баг для каждого класса входов, не перечисляя их как тесты.
Heads-up Big-O измеряет рост стоимости, а не корректность. Неверный и верный алгоритм могут иметь одинаковую O(n). Корректность доказывают инвариантами и разбором крайних случаев, а не Big-O.
Викторина
Completed
Две процедуры сортировки обе «корректны». Merge sort — время O(n log n) / память O(n); bubble sort — время O(n²) / память O(1). Для сортировки 1 000 000 записей на обычной машине как верно это прочитать?
Heads-up На миллионе записей 10¹² операций bubble sort безнадёжно медленны. Экономия O(1) памяти неважна, когда стоимость времени в 50 000 раз хуже, а память не является ограничением.
Heads-up Оба корректны, но корректность ничего не говорит о стоимости. Разрыв O(n log n) против O(n²) — это и есть суть: на масштабе только один завершится за разумное время.
Heads-up O(n²) практичен только до нескольких тысяч элементов. При 10⁶ это ~10¹² операций — далеко за пределами осуществимого, поэтому и существуют сортировки O(n log n).
Итог
Сквозная линия юнита — одна привычка: до запуска оцени стоимость. Подсчитай шаги, оставь только доминирующий член, назови класс Big-O, взвесь время против памяти под своё реальное ограничение и дай границе входа подсказать, какой класс вообще допустим. И никогда не путай стоимость с корректностью — Big-O измеряет, насколько быстро, а инвариант цикла доказывает, верно ли это вообще.