Ознакомительная версия. Доступно 5 страниц из 22
Второе свойство: каждый узел имеет два дочерних, с возможным исключением самых низших узлов. Этот структурный инвариант гарантирует, что высота пирамиды, то есть самый длинный возможный путь, не будет превышать log n, где n есть номер элементов в пирамиде.
Вот что происходит, когда Вурзма берет коробку перчаток – вещь, которая, как мы определили, лежит ближе всего ко входу, – и хочет узнать, что из списка взять следующим.
Как только мы удалили наивысший узел, первое свойство пирамиды уничтожается и активируется алгоритм повторной перестройки, который подразумевает замену пустого корневого узла последним узлом в пирамиде. Далее следует проверка нового корневого узла и его сравнение с дочерними, чтобы понять, нужно ли их поменять. Эта проверка и замена производятся с каждой парой, состоящей из родительского узла и самого малого из двух дочерних узлов все время, по мере продвижения к последнему узлу в пирамиде. Заметьте, что этот процесс перестройки пирамиды занимает логарифмическое время[47] и приводит к тому, что следующая самая близкая вещь оказывается наверху.
То же самое происходит, если нам нужно вставить новый приоритетный пункт в список, не стирая и не передвигая другие без необходимости, за log n число движений. Мы добавляем новый пункт в конец пирамиды и затем меняем местами с его родительским узлом, если он вдруг оказывается больше, чем новый пункт. Мы продолжаем менять их при необходимости до самого корневого узла.
В этой книге мы говорили об элегантных подходах, которые может использовать компьютер при решении какой-либо задачи. Нужно снова вспомнить о них, чтобы подчеркнуть: алгоритмы могут иметь все свойства, присущие искусству, – красоту, изящество и грацию. Если вы достигнете более продвинутых областей, где алгоритмы играют большую роль, обращайте внимание не только на результаты и производительность, но и на способы их составления. В мире искусственного интеллекта приложения алгоритмов включают в себя постановку более быстрых диагнозов в больнице, спасение жизни пациентов или исследования, дающие представление о геноме человека. В мире теории игр приложения работают на компании кратковременной аренды автомобилей, где принимают решения, как объединить пассажиров, которым нужно одновременно ехать одинаковым маршрутом. Мир компьютерного будущего занимается проектировкой беспилотных автомобилей или изобретает новые способы обработки изображений, выходящие за рамки простых трансформаций яркости и контраста. Приложениям нет границ в прикладном использовании.
Что же касается Вурзмы, то его карьера рэпера скоро начнется. Никто прежде не думал о сочинении рэпа как о массивах, хеш-таблицах и очередях с приоритетом. А ведь это может быть круто! Вурзме предстоит рассказать об этом своему сыну, которого он хочет поразить своим выступлением на рэп-баттле, в тот день, когда мальчику исполнится 11, то есть на следующей неделе. Да, что-то может пойти наперекосяк. Но самое главное: Вурзма стал быстрее управляться с покупками и делает все так хорошо, что его готовящийся к выпуску сингл пронизан самомнением. Вот и молодец.
Больше никаких игр, никаких шуток, я новый человек,
Феникс, возрожденный из пепла,
Давай начистоту, как Билл Хикс,[48]
Я так быстр, что трудно поверить, от варенья до салфеток «Клинекс»,
Хлеб, молоко и мед, органический сахар и печенье-ассорти,
Вижу: все глядят на меня, в удивлении и шоке,
Но твой стыд слишком велик, чтобы ты смог признать это,
И это норм,
Ты лишь критик себя самого,
А я – киношка Майкла Бея.[49]
Заключительные мысли
Когда Фейнманна однажды спросили, как ему удалось развить свою легендарную способность молниеносно решать задачи, он ответил, что применял к ним различные способы, то есть смотрел на них под разным углом зрения. Использование аналогий – один из способов рассмотреть задачу, отождествление – другой, диалектический метод – третий. Для Фейнманна, который всегда был шоуменом, выдуманная история была способом удивить аудиторию – и по-новому взглянуть на задачу.
В искусстве есть аналогичный подход к решению задач. Умение нарисовать сцену с различных точек без потери деталей здесь считается огромным достоинством. Интересно, что это стало возможным благодаря инновации итальянского архитектора и скульптора Брунеллески в период Возрождения. Разрабатывая математический способ передачи линейной перспективы, Брунеллески создал идеально точный рисунок баптистерии Святого Иоанна во Флоренции. Предметы, которые располагались ближе, выглядели больше, находящиеся дальше – меньше, а линии плиток сходились в одной точке. Такие фрески, как «Вручение ключей» авторства Пьетро Перуджино и «Афинская школа» Рафаэля, – прекрасные более поздние примеры применения этого метода.
Мы начали с того, что концентрация на относительных величинах и каждодневных задачах помогает сделать сложные задания более выполнимыми. В какой-то мере они создают в голове своеобразные триггеры, которые напоминают нам о необходимости постоянно делать выбор. В следующий раз, когда вы увидите гору вещей, которую нужно отсортировать, вы, наверное, подумаете: «Ага, хорошее и плохое, быстрое и медленное, квадратичное и линейно-логарифмическое». Ваши сын, дочь, племянница или племянник могут спросить вас, что такое бинарный поиск, и вы подумаете: «Ага, свобода, Уильям Уолас, Эппи Тоам, рубашки на вешалке». Такие ассоциации легко и весело запоминать. Умение выбирать между хорошим и плохим поможет вам: вы будете знать, как выглядит спектр вариантов для выполнения конкретного задания.
Сегодня слово «алгоритм» можно услышать от многих людей, подобно тому как словосочетание «большой массив данных» было в ходу несколько лет назад. Я надеюсь, что после прочтения этой книги вы поняли, что эта концепция – не причуда. Ее корни в истории, как мы видели при обсуждении вавилонских табличек. Это вневременная концепция, поэтому о ней стоит поговорить, разобрать ее и, что важнее всего, показать, как можно использовать алгоритм в качестве инструмента эффективного мышления.
Ознакомительная версия. Доступно 5 страниц из 22
