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