Это допущение требует нескольких оговорок.
Например, бывают случаи, в которых второстепенные члены оказывают серьезное влияние на функцию. Вспомните Джо и ее ожерелье из главы 9. Мы сконцентрировались на добавлении бусин и рассматривали первый метод как линейно-временной, а второй – как постоянно-временной и при этом более привлекательный. Мы по умолчанию признавали, что склеивание свободных концов шпагата было простым заданием – но если клею нужно пять минут, чтобы схватиться? Повлияет ли это на выбор Джо? Такие постоянные величины наиболее заметны, когда мы имеем дело с малым числом элементов и должны учитывать их наличие.
Две другие нотации, которые дополняют большую тету и оперируют при тех же условиях, – большая омега и большая о. Большая омега устанавливает нижнюю границу функции для достаточно большого значения n, то есть она говорит, что наша функция может расти не медленней, чем ее нижняя граница. Большая о определяет верхнюю границу функции для достаточно большого значения n, то есть говорит о том, что наша функция может расти не быстрее, чем верхняя граница. Конечно, в действительности функция может расти медленней, чем верхний предел и, таким образом, быть более привлекательной, но большое о – пессимист и воплощение закона Сода.
[41]
Когда мы говорим о скорости роста алгоритма, мы имеем в виду его действенность в худшем случае, когда он тесно связан, по оценке большой теты. Заметьте, что любой уровень скрытности, двуличия, обмана, который мы допускаем в этой книге, порождает компромисс. Важно знать, что в реальности больше нюансов, чем в теории, – об этом можно прочитать в источниках, перечисленных в конце книги. Что касается Людвика, то различия в двух алгоритмах очевидны, что делает решение его проблемы достаточно легким.
11
Заполни полки
Терри учится на втором курсе престижного вуза Medlock High в Беверли-Хиллз (Калифорния). Он наказан (оставлен после занятий) за затеянную на лекции по социологии провокационную дискуссию на тему «Не во всем должны быть авокадо и капуста». В качестве воспитательной меры куратор отправил Терри в школьную библиотеку и велел выставить книги на только что купленную полку. Старая полка недавно обрушилась, и около 250 книг оказалось на полу. Все, что нужно сделать второкурснику-бунтарю, – выстроить книги на полке в алфавитном порядке по фамилиям авторов. Терри собирается вечером сходить в кино с друзьями и не хочет застрять в университете до полуночи. Ему удастся все сделать, но нельзя терять ни минуты.
ЦЕЛЬ: ВЫСТАВИТЬ ВСЕ КНИГИ НА ПОЛКУ В АЛФАВИТНОМ ПОРЯДКЕ.
МЕТОД 1: ВЗЯТЬ КНИГУ И ПОСТАВИТЬ ЕЕ НА ПОЛКУ. ВЗЯТЬ ДРУГУЮ И ПОСТАВИТЬ ЕЕ ПЕРЕД ИЛИ ПОСЛЕ ПЕРВОЙ, В ЗАВИСИМОСТИ ОТ ФАМИЛИИ АВТОРА. И ТАК ДАЛЕЕ.
МЕТОД 2: ИСПОЛЬЗОВАТЬ КНИЖНЫЕ ДЕРЖАТЕЛИ, ЧТОБЫ ОСТАВЛЯТЬ МЕСТО ПОСЛЕ КАЖДОЙ БУКВЫ АЛФАВИТА, ЗАТЕМ СТАВИТЬ КНИГИ, ПЕРЕМЕЩАЯ ДЕРЖАТЕЛИ ПО МЕРЕ НАДОБНОСТИ.
Давайте вначале решим, как Терри может поступить с заданием. Мы видели в главе 15, что подходы к сортировке, которые строятся на сравнении смежных элементов и определении, какой из них больше, а какой меньше, занимают квадратичное время. Мы говорили, что примеры такого подхода на практике включают в себя сортировку вставкой, сортировку выбором и пузырьковую сортировку и что все они работают, используя образец с минимальными различиями. Метод 1 Терри – это тот же подход, что и метод 1 Чарли из главы 5.
Здесь интересно, что усовершенствованный метод Терри не останавливается на алгоритме разбивания, как в случае с Чарли. Он модифицирует оригинальный алгоритм квадратичного времени. Это происходит при внедрении относительно простой инновации. Если мы возьмем такой алгоритм, как сортировка вставкой, мы обнаружим, что самым медленным действием будет помещение элемента на правильное место. Каждый раз после того, как мы делаем это, приходится менять расположение всех последующих элементов, передвигая их один за другим.
Что происходит при применении метода 2 Терри? Он заранее учитывает эти сдвиги, создавая пустые пространства по всей длине полки через равные промежутки. Найдя нужное место для вставляемой книги, Терри, вероятнее всего, передвинет лишь несколько других книг. Чем больше и шире эти свободные пространства, тем меньше книг ему придется сдвигать каждый раз.
Эта модернизация метода сортировки путем вставки ведет от алгоритма квадратичного времени к линейно-логарифмическому «с высокой вероятностью», как выразился его автор, и называется библиотечной сортировкой. Вспомните идею из главы 10: расставление книжных держателей по полке может сделать этот подход медленнее, если книг мало, но при их достаточно большом количестве он обладает преимуществом перед альтернативным алгоритмом.
Вот как два этих подхода выглядят на графике:
Возможно, мы лучше поймем выигрышность этого подхода, рассмотрев альтернативный, чуть более ограниченный сценарий. Вот какую мрачную картину рисуют авторы библиотечной сортировки: технологическая индустрия накрылась медным тазом, мир устал от ее глупых идей. Тысячи уволенных работников нашли убежище в некоем месте, где применяют свои таланты в обмен на бесплатную пиццу с приправами. Приток специалистов привел в восторг университеты по всей стране. Все рады, кроме архивариуса в том самом колледже. Да, пятнадцать лет назад его звали Терри. Он заведует полками с ячейками, которые промаркированы именами всех выпускников кафедры, расположенными в алфавитном порядке, и затем двигает поверх всех остальных лейблов один.
