Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - страница 9
Обычно так и происходит. Однако коллекция может обладать одним интересным качеством, а именно: она поддается сортировке, что позволяет найти вещь по алгоритму логарифмического времени, примерно за 7 шагов, а не за 100. Вспомните, что логарифм – это всего лишь нечто обратное экспоненте. Составляя компьютерные программы, мы предполагаем, что основание логарифма есть 2, поэтому логарифм 100 это log2 100, то есть получается примерно 7. Это значительное улучшение можно увидеть, переходя от линейного времени к логарифмическому. Поэтому логарифм и является таким важным понятием, особенно когда мы говорим о скорости роста. К этому мы будем часто возвращаться в следующих главах.
Для начала давайте представим, как Эппи носится по магазину с сияющим от гордости и тщеславия лицом. Шарф развевается, ее боевые крики вырываются сквозь стиснутые зубы и отражаются от стен универмага. Она все утро готовилась к этому моменту.
ЦЕЛЬ: НА ВЫБРАННОЙ ВЕШАЛКЕ НАЙТИ БЛУЗКУ СВОЕГО РАЗМЕРА.
МЕТОД 1: ДЛЯ ВЫБРАННОЙ ВЕШАЛКИ. ПРОСМОТРЕТЬ ВСЕ БЛУЗКИ ОДНУ ЗА ДРУГОЙ.
МЕТОД 2: ДЛЯ ВЫБРАННОЙ ВЕШАЛКИ. НАЧНИТЕ ИСКАТЬ СВОЙ РАЗМЕР В СЕРЕДИНЕ ВЕШАЛКИ. ЕСЛИ ТАМ ВИСЯТ БЛУЗКИ РАЗМЕРОМ БОЛЬШЕ, НУЖНО ПОЙТИ НАЛЕВО. ЕСЛИ ЖЕ РАЗМЕРЫ МЕНЬШЕ – НАПРАВО.
Вот так можно наглядно сравнить эти два метода. Очевидно, что поиски по методу 1 станут значительно медленнее, чем по методу 2, по мере увеличения количества блузок на вешалке.
Как вы уже, вероятно, догадались, в методе 2 выгодно используется знание двух фактов. Во-первых, блузки, скорее всего, отсортированы по размерам. А во-вторых, поскольку у Эппи ходовой размер, то скорее всего нужные ей блузки висят где-то в середине вешалки. Зная это, можно не только начать с середины, но и передвигаться влево или вправо своеобразными скачками, каждый раз сокращая коллекцию вдвое. Такой подход и есть визитная карточка алгоритма логарифмического времени.[14] Это та самая интуиция, которую мы используем, чтобы найти нужное слово в словаре, или имя в телефонном справочнике, или статью в энциклопедии. Те же интуитивные знания мы будем применять, если заснем над скучной книгой и захотим на следующий день возобновить чтение с того же места. В целом можно охарактеризовать этот подход как принцип отбрасывания ненужной информации.
ЭППИ НАХОДИТ СВОЙ РАЗМЕР ЗА 4 ШАГА.