1. Задача
Тебе нужно найти фамилию «Смирнов» в бумажном телефонном справочнике на миллион имён. Фамилии в нём стоят по алфавиту. Есть два способа:
- Листать страницу за страницей с самого начала, пока не наткнёшься на нужную фамилию.
- Открыть справочник на середине и посмотреть, ушёл ты дальше нужной буквы или ещё не дошёл до неё. Ту половину, где фамилии быть не может, отбросить. Повторить то же самое с оставшейся половиной.
Оба способа находят Смирнова. Первый займёт целый перерыв на кофе, второй пару секунд. Ответ одинаковый, а затраты совсем разные.
2. Считай работу, а не секунды
Скорость способа меряют числом шагов: сколько коробок ты просматриваешь. Секунды для этого не годятся. На быстром компьютере медленный способ просто станет чуть менее медленным.
Листая страницы, ты просмотришь до миллиона страниц. Деля пополам, просмотришь около двадцати. После первого взгляда остаётся 500 000 страниц, после второго 250 000, после третьего 125 000. Каждый взгляд отбрасывает половину того, что осталось. Примерно через двадцать таких шагов остаётся одна страница.
3. Разрыв взрывается по мере роста
На маленьком списке разницы никто не заметит: оба способа срабатывают мгновенно. Разница видна, только когда данных становится много. Тогда она огромная:
| имён | по одной | деление пополам |
|---|---|---|
| 1 000 | ~1 000 | ~10 |
| 1 000 000 | ~1 000 000 | ~20 |
| 1 000 000 000 | ~1 000 000 000 | ~30 |
Медленный способ растёт так же быстро, как данные. Быстрый почти не растёт: когда имён становится в тысячу раз больше, ему нужно всего на 10 шагов больше. Из-за этой разницы алгоритмы вообще и изучают.
4. Твоя очередь (без кода)
Поиск на сайте перебирает товары по одному. На 100 товарах он кажется мгновенным, а на 5 000 000 зависает. Код при этом не менялся. Что же изменилось? И какой из двух способов выше это исправил бы?
Ответ: выросли данные. Перебор по одному замедляется во столько же раз, во сколько выросли данные. Деление пополам остаётся быстрым при любом размере входа, но ему нужны заранее отсортированные данные. Выбрать правильный способ до того, как данные вырастут, и есть работа программиста.
5. Главное
Одни способы остаются дешёвыми, когда данных становится больше. Другие разваливаются. Ты только что сам, без всякой математики, увидел два самых важных вида роста: «просмотреть всё» и «каждый раз делить пополам». В следующем уроке они получат свои настоящие имена, там появится Big-O. Дальше каждый приём в курсе учит оставаться на дешёвой стороне этой таблицы.
На LeetCode
Задачи для LeetCode здесь нет, потому что урок считает шаги и код не пишет. Он объясняет, зачем под каждой задачей на LeetCode стоят ограничения вроде n ≤ 10^5, а урок 9 учит выбирать по ним способ решения.
Ты читаешь как гость
Все бесплатные уроки открыты: читай и запускай. Бесплатный аккаунт отмечает пройденные уроки и показывает, где ты в курсе.