времени к логарифмическому. Поэтому логарифм и является таким важным понятием,
особенно когда мы говорим о скорости роста. К этому мы будем часто возвращаться в
следующих главах.
Для начала давайте представим, как Эппи носится по магазину с сияющим от гордости
и тщеславия лицом. Шарф развевается, ее боевые крики вырываются сквозь стиснутые зубы
и отражаются от стен универмага. Она все утро готовилась к этому моменту.
ЦЕЛЬ: НА ВЫБРАННОЙ ВЕШАЛКЕ НАЙТИ БЛУЗКУ СВОЕГО
РАЗМЕРА.
МЕТОД 1: ДЛЯ ВЫБРАННОЙ ВЕШАЛКИ. ПРОСМОТРЕТЬ ВСЕ БЛУЗКИ
ОДНУ ЗА ДРУГОЙ.
МЕТОД 2: ДЛЯ ВЫБРАННОЙ ВЕШАЛКИ. НАЧНИТЕ ИСКАТЬ СВОЙ
РАЗМЕР В СЕРЕДИНЕ ВЕШАЛКИ. ЕСЛИ ТАМ ВИСЯТ БЛУЗКИ РАЗМЕРОМ
БОЛЬШЕ, НУЖНО ПОЙТИ НАЛЕВО. ЕСЛИ ЖЕ РАЗМЕРЫ МЕНЬШЕ –
НАПРАВО.
Вот так можно наглядно сравнить эти два метода. Очевидно, что поиски по методу
1 станут значительно медленнее, чем по методу 2, по мере увеличения количества блузок на
вешалке.
13
Как вы уже, вероятно, догадались, в методе 2 выгодно используется знание двух
фактов. Во-первых, блузки, скорее всего, отсортированы по размерам. А во-вторых,
поскольку у Эппи ходовой размер, то скорее всего нужные ей блузки висят где-то в середине
вешалки. Зная это, можно не только начать с середины, но и передвигаться влево или вправо
своеобразными скачками, каждый раз сокращая коллекцию вдвое. Такой подход и есть
визитная карточка алгоритма логарифмического времени.14 Это та самая интуиция, которую
мы используем, чтобы найти нужное слово в словаре, или имя в телефонном справочнике,
или статью в энциклопедии. Те же интуитивные знания мы будем применять, если заснем
над скучной книгой и захотим на следующий день возобновить чтение с того же места. В
целом можно охарактеризовать этот подход как принцип отбрасывания ненужной
информации.
ЭППИ НАХОДИТ СВОЙ РАЗМЕР ЗА 4 ШАГА.
14 Сходным образом процесс многократного удвоения чисел от 1 до n логарифмичен, поскольку мы можем
сделать не более чем log n скачков, прежде чем получим n. Например, сколько лет уйдет на зарабатывание
1 млн долларов, если начать с 1 доллара и каждый год удваивать его? Можно посчитать это вручную или же
применить log2 1 000 000 = 19,93 года ( прим. автора).
14
ЭППИ НАХОДИТ СВОЙ РАЗМЕР ЗА 2 ШАГА.
Для нас наиболее важной информацией о логарифмах является то, что они медленно
растут, как вы видели из предыдущих графиков. Мы предпочитаем решения, которые растут
медленно, потому что это означает, что наш метод не так сильно зависит от количества
предметов. Эппи скорее всего найдет нужную вещь на вешалке с сотней блузок менее чем за
7 шагов, а на гипотетической вешалке с тысячью блузок – всего за 10 шагов или около того,
что не так уж плохо. Этот метод логарифмического поиска чего-либо в отсортированной
группе предметов часто называют бинарным поиском. Он значительно эффективнее метода
1, известного под названием линейный поиск, и благодаря ему Эппи приобрела кучу новых
блузок своего размера.
15
16
3
Поход за продуктами
Ян Патой – бывший учитель английской словесности, лингвист. Он пенсионер и живет
на востоке Лондона. Несколько лет назад он упал, и теперь у него сильно болит спина. Он не
17
любит выходить на улицу, потому что боится соседской собаки, но ему приходится иногда
совершать вылазки за продуктами. В Лондоне часто идет дождь, а старые кости Яна не
выносят сырости. Как свести к минимуму количество походов в магазин в неделю, чтобы не
умереть с голода?
Есть такой комедийный скетч с двумя Ронни15 – клиент приходит в скобяную лавку и
читает список вещей, которые ему нужно купить. Вместо того чтобы дождаться конца
списка, владелец магазина каждый раз хватает названную вещь, и все заканчивается тем, что
у продавца едет крыша.
Запомните эту сценку.16 Мы еще вернемся к ней. Но сначала давайте посмотрим, как
Ян может решить, насколько часто ему ходить в магазин.
ЦЕЛЬ: СОВЕРШАТЬ КАК МОЖНО МЕНЬШЕ ВЫЛАЗОК В МАГАЗИН
В ТЕЧЕНИЕ НЕДЕЛИ.
МЕТОД
1:
ОБНАРУЖИТЬ,
ЧТО
КАКОЙ-ТО
ПРОДУКТ
ЗАКАНЧИВАЕТСЯ И ОТПРАВИТЬСЯ ЗА НИМ В МАГАЗИН.
МЕТОД 2: СОСТАВЛЯТЬ СПИСОК ЗАКОНЧИВШИХСЯ ПРОДУКТОВ.
ПОЙТИ В МАГАЗИН, КОГДА СПИСОК ДОСТИГНЕТ ОПРЕДЕЛЕННЫХ
РАЗМЕРОВ ИЛИ КОГДА ЗАКОНЧИТСЯ КАКОЙ-НИБУДЬ ЖИЗНЕННО
ВАЖНЫЙ
ПРОДУКТ,
НАПРИМЕР
ШОКОЛАДНЫЕ
БАТОНЧИКИ
«КИТ-КАТ».17
Вот уже знакомый нам график, где можно посмотреть и сравнить эффективность этих
двух методов.
Одна
