Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

Эта модернизация метода сортировки путем вставки ведет от алгоритма квадратичного времени к линейно-логарифмическому «с высокой вероятностью», как выразился его автор, и называется библиотечной сортировкой. Вспомните идею из главы 10: расставление книжных держателей по полке может сделать этот подход медленнее, если книг мало, но при их достаточно большом количестве он обладает преимуществом перед альтернативным алгоритмом.

Вот как два этих подхода выглядят на графике:

Возможно, мы лучше поймем выигрышность этого подхода, рассмотрев альтернативный, чуть более ограниченный сценарий. Вот какую мрачную картину рисуют авторы библиотечной сортировки: технологическая индустрия накрылась медным тазом, мир устал от ее глупых идей. Тысячи уволенных работников нашли убежище в некоем месте, где применяют свои таланты в обмен на бесплатную пиццу с приправами. Приток специалистов привел в восторг университеты по всей стране. Все рады, кроме архивариуса в том самом колледже. Да, пятнадцать лет назад его звали Терри. Он заведует полками с ячейками, которые промаркированы именами всех выпускников кафедры, расположенными в алфавитном порядке, и затем двигает поверх всех остальных лейблов один.

Теперь, когда частота движения ячеек достигла космической скорости, Терри вспомнил об алгоритме, который он применял когда-то в школе. Он признает, что подобный подход поможет снизить его стресс за счет высвобождения свободного пространства. И вот он создает пустые кармашки между занятыми ячейками.[42]

Недавнее упоминание о «высокой вероятности» подводит нас к важной теме и одновременно сути этой главы. Прежде мы мимоходом упоминали о «худших случаях» и «средних случаях» для разных алгоритмов. Эти существенные показатели позволяют спрогнозировать, сколько времени уйдет у определенного алгоритма на перебор всего ряда элементов.

Время осуществления алгоритма зависит от многих условий. Например, в коде мы можем столкнуться с присутствием логических ветвей (если это не ваш случай, то пропустите этот абзац). Исходя из того, какой путь выбран, время пробега может варьироваться. Хороший пример – быстрая сортировка, которая упомянута в главе 5. При быстрой сортировке разделение начинается в первую очередь с выбора опорного элемента. Этот элемент используется для разделения массива данных на две группы: в одной содержатся элементы меньше опорного, в другой – больше него. Когда опорный элемент выбирается наугад, быстрая сортировка в среднем случае проходит в логарифмическом времени. Если опорный элемент слишком велик или слишком мал, быстрая сортировка может идти в квадратичном времени в худшем случае. Это изменение в производительности происходит из-за того, что опорный элемент не справляется с разделением массива элементов на каждом этапе, и приходится проверять почти каждый элемент на каждом из тех этапов, которые, как мы видели в ранних главах, являются атрибутами квадратичного алгоритма.

Анализ быстрой сортировки показывает, что алгоритм имеет высокую вероятность прохождения в линейно-логарифмическом времени. Мы знаем, что нужно сделать, чтобы достичь этого, – убедиться, что опорный элемент не является самым верхним или самым нижним в массиве. Таким образом элемент с усредненным значением применим практически для всех случаев и может гарантировать, что быстрая сортировка пройдет в линейно-логарифмическом времени.

Но иногда вероятной гарантии все же недостаточно. Если наш алгоритм работает с таким приложением, как управление космическим шаттлом, или представляет угрозу для чьей-то жизни, регулирует работу инфузионного насоса или дефибриллятора, то показатель наихудшего случая будет нас сильно беспокоить. Классификация потенциального результата полезна и в других приложениях, применимых в повседневной жизни.

Для Терри средний случай линейно-логарифмического времени более чем предпочтителен, хотя поиск по его алгоритму в худшем случае будет проходить в квадратичном времени. Сейчас ему не о чем волноваться. Пока у него достаточно книжных разделителей, он успевает в кино вовремя.

12

В супермаркете