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

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

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

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

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

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

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

Вурзма Моне до недавнего времени работал менеджером в фонде управления инвестиционными бумагами. Непостижимое решение стать рэпером возникло у него после того, как он прочитал в одной из школ лекцию о страховке кредиторов от дефолта. Беседа прошла под лозунгом «Кем работает мой отец», и к полудню Вурзма решил вести более осмысленную жизнь. Он ходит в местный супермаркет каждые две недели и часто ловит себя на том, что бродит по проходам из одного конца в другой в поисках нужных ему вещей из списка покупок. Туда-сюда, туда-сюда – у него уходит целая вечность на покупки. Визит в магазин еще больше затягивается из-за странной походки Вурзмы, которая мало походит на «крутую пацанскую» и больше напоминает ребят, которые своим видом будто говорят: «Я пропустил очередную консультацию у психотерапевта». Другие рэперы сразу замечают это несоответствие, и хрупкое доверие к Вурзме со стороны уличной продвинутой молодежи еще больше слабеет. Ему надо перестать выглядеть идиотом и избавиться от мыслей, обрекающих его на смехотворное существование.

Вурзма находится на перепутье. Но у нас хорошая новость: похоже, мы знаем, как ему помочь, и в этой главе рассмотрим варианты, о которых уже говорили в предыдущих главах. Есть два способа, которые Вурзма может использовать, бродя по супермаркету в поисках продуктов из списка.

ЦЕЛЬ: СВЕСТИ К МИНИМУМУ КОЛИЧЕСТВО РЯДОВ, ПО КОТОРЫМ НУЖНО ПРОЙТИ.

МЕТОД 1: ПРОСМОТРЕТЬ ВЕСЬ СПИСОК ПОКУПОК ПО ПУНКТАМ.

МЕТОД 2: ПОДГОТОВИТЬ СПИСОК ЗАРАНЕЕ, ЧТОБЫ ВСЕ БЫЛО РАЗЛОЖЕНО ПО КАТЕГОРИЯМ. ПРОСМАТРИВАТЬ ОДНУ КАТЕГОРИЮ ЗА ДРУГОЙ, СОВЕРШАЯ ПОКУПКИ.

Я положу свой массив в твой массив, чтоб ты не стартовал, не спросив

До сих пор мы говорили о массивах как о фундаментальной структуре, предназначенной для хранения набора элементов. В главе 6 мы ввели еще одну полезную структуру под названием матрица, которая также нужна для хранения групп элементов. Но здесь они сохраняются в двух измерениях, а не в одном. Что общего у этих двух структур? А то, что массив может быть преобразован в матрицу. Все, что нужно для этого сделать, – вместо сохранения литер (как, например, цифра, буква или слово) в каждом расположении сохранить массив. Массив массивов называется двумерным, или в более общем виде многомерным массивом.

Многомерные массивы позволяют нам с Вурзмой сделать одну полезную вещь – сохранить список покупок в двух измерениях, что позволит нашему герою двигаться по любому подмассиву в зависимости от отдела, в котором он сейчас находится.