Алгоритмы с нуля
Мышление и сложность: предскажи, затем измерь
Знать, что O(n²) «растёт быстрее», чем O(n), — не то же, что увидеть это. Собери небольшой бенчмарк-стенд, прогони несколько алгоритмов по растущим размерам входа и увидь, как кривые загибаются ровно там, где сказала Big-O — анализ, подтверждённый измерением.
Преврати теорию юнита в эмпирический цикл: предскажи Big-O алгоритма, читая код, измерь, как его реальная стоимость масштабируется при удвоении n, и согласуй одно с другим — включая случаи, где константы и компромисс время-память делают практического победителя не тем, кто выигрывает асимптотически.
Собери бенчмарк «предскажи-затем-измерь», который прогоняет минимум четыре алгоритма разных классов сложности по диапазону размеров входа, затем покажи, что измеренный рост (число операций и время) совпадает с Big-O, которую ты предсказал по коду — и объясни каждое место, где не совпадает.
- Таблица предсказано-против-измерено: для каждого алгоритма предсказанная Big-O рядом с измеренным отношением удвоения, и они согласуются (O(n)≈2×, O(n²)≈4×, O(log n) — небольшой аддитивный шаг, O(1) — плоско).
- Стоимость алгоритма O(n²) показана обгоняющей O(n) по мере роста n, с явно отмеченной точкой пересечения (и любой областью малых n, где «медленный» класс выигрывает из-за констант).
- Короткое описание, согласующее каждое расхождение — например, шум при крошечных n, константные множители или отношение удвоения, сходящееся к теоретическому значению лишь при больших n.
- Сравнение поиска дубликата сообщает время и дополнительную память для каждого подхода и указывает, какое ограничение (задержка против памяти) заставило бы выбрать каждый.
- Твоё предсказание ~1 секунды по правилу 10⁸ опер/сек попадает в пределах порядка величины от измеренного результата, с объяснением разрыва (константные множители, накладные расходы языка).
- Нарисуй измеренные кривые на одних осях и ещё раз в log-log осях, где каждый класс Big-O становится прямой линией, наклон которой — её показатель степени; считай наклоны и сопоставь с предсказаниями.
- Добавь O(2ⁿ) наивный рекурсивный Фибоначчи и мемоизированную O(n) версию; покажи, как экспоненциальная становится неисполнимой за n ≈ 40, тогда как линейная остаётся мгновенной.
- Добавь стенд корректности: докажи каждый алгоритм через заявленную спецификацию и батарею крайних случаев (пустой вход, один элемент, все равны, все отрицательны), чтобы подтвердить скорость без потери корректности.
- Повтори один бенчмарк на втором языке (например, Python против JS) и покажи, что отношение удвоения — отпечаток Big-O — одинаково, хотя абсолютные времена различаются, закрепляя, что Big-O машинно- и языко-независима.
Это цикл, который ты запускаешь всякий раз, когда под вопросом производительность: предскажи Big-O, читая код, затем измерь реальный рост при удвоении n и сверь отношение удвоения с классом. Асимптотическое предсказание почти всегда выигрывает на масштабе, но константы и компромисс время-память решают практического победителя на тех размерах, что ты реально запускаешь — а быстрый алгоритм всё ещё обязан быть корректным. Сделав это однажды на бенчмарк-стенде, превращаешь «оцени до запуска» в рефлекс.