Книга: «Грокаем алгоритмы. 2-е изд.»02.10.2024 16:15

Хаброжители, привет!

Мы снова возвращаемся с вторым изданием книги «Грокаем алгоритмы»! Красивым, новеньким, актуализированным. От первого тиража всё ещё пахнет типографией, а код примеров обновлен на Python 3!

Зачем второе издание? Первое было интересным, понятным, запоминающимся. Но оно было выпущено в далёком 2016 году, а перевод появился лишь в 2017. В сфере компьютерных технологий всё меняется и обновляется с невероятной скоростью, неудивительно, что автор решил актуализировать свою книгу.

Книга будет интересна читателям, которые владеют азами программирования и хотят разобраться в алгоритмах. Таким читателям, как:

• программисты-самоучки;
• студенты, начавшие изучать программирование;
• выпускники, желающие освежить память;
• специалисты по физике/математике/другим дисциплинам, интересующиеся программированием.

Причины купить «Грокаем алгоритмы. 2-е изд.»:

• Появилось 64 новые страницы!
Больше — значит лучше. Здесь нет воды, Адитья Бхаргава постарался подробно раскрыть темы, которые были пропущены в предыдущей версии. Он старательно отвечал на вопросы читателей, закрывая пробелы и недостающие фрагменты своих объяснений.

• Более подробно расписана концепция деревьев и о NP-полноте.
В первом издании не всё до конца было объяснено про концепцию деревьев. Автор получал отзывы, где были вопросы, в которых стоило разобраться. В новом издании информация была дополнена, добавлены 2 главы.
Также был расширен раздел, где рассказывается о NP-полноте. Концепция NP-полноты весьма абстрактна, и хотелось привести объяснение, придающее ей больше конкретности.

• Код примеров обновлен на Python 3 (теперь уже точно!)
Информация актуализировалась, теперь пользователям Python будет проще выполнять упражнения для закрепления.
Ранее мы выпустили бракованный тираж, где этот пункт был пропущен. Книги отозваны, новые версии проверены.

• Легко читается.
Это особенность прекрасного стиля Бхаргава. Он избегает неожиданных поворотов. Каждый раз, как в книге упоминается новая концепция, так или иначе она будет объяснена. Основные концепции подкрепляются упражнениями и повторными объяснениями, чтобы читатели могли проверить свои предположения и убедиться в том, что не потеряли нить изложения.
Не требуется продвинутых знаний математики или навыков программирования. Всё написано доступным языком и подробно объясняется.
Читать отрывок.

• Более 400 забавных иллюстраций и десятки примеров.
Одна из особенностей серии «Грокаем», о которой писали ранее — наличие понятных и запоминающихся за счёт своей необычной формы иллюстраций. Они помогают не только лучше понять материал, но и запомнить его.
Узнать подробнее о серии «Грокаем».

Отрывок из книги. Балансировка

Балансировка

С помощью бинарного поиска можно найти информацию намного быстрее, чем простым поиском — со сложностью O (log n) вместо O (n). Впрочем, есть одна проблема: вставка. Конечно, поиск занимает время O (log n), но массив должен быть отсортирован. Если требуется вставить новое число в отсортированный массив, это займет время O (n). Проблема в том, чтобы найти место для нового значения. Придется передвинуть несколько элементов, чтобы освободить для него место.

Вот если бы вставку можно было выполнять как в связанном списке, где достаточно поменять пару указателей…

Но поиск в связанных списках выполняется за линейное время. Как использовать лучшие стороны обоих решений?

Деревья повышают скорость вставки

Итак, по сути, нам нужны скорость поиска в отсортированном массиве и более быстрая вставка. Как известно, вставка выполняется быстрее в связанных списках. А значит, нам понадобится структура данных, объединяющая эти идеи.

И такая структура существует — это дерево! Деревья бывают десятков разных видов, поэтому я специально отмечаю, что нам нужно сбалансированное бинарное дерево поиска (BST). В этой главе я покажу, как работает BST, а затем вы научитесь его балансировать.
BST — это разновидность бинарного дерева. Пример BST:

Как и в бинарном дереве, каждый узел имеет до двух дочерних узлов: левый и правый. Но у этого дерева есть одно свойство, относящее его к BST: значение левого дочернего узла всегда меньше, чем значение узла, а значение правого дочернего узла всегда больше. Таким образом, для узла 10 левый дочерний узел имеет меньшее значение (5), а правый дочерний узел — большее значение (20).

Более того, все числа в поддереве левого дочернего узла меньше самого узла!

Это особое свойство означает, что поиск будет выполняться очень быстро.
Давайте посмотрим, содержится ли число 7 в этом дереве. Начнем с корневого узла.

Число 7 меньше 10, поэтому проверяется левое поддерево. Вспомните: все узлы с меньшими значениями находятся в левом поддереве, а все узлы с большими значениями — в правом. Следовательно, мы сразу понимаем, что проверять узлы справа не нужно, потому что 7 там не будет. Опускаясь по левому поддереву от 10, мы переходим к узлу 5.

Число 7 больше 5, поэтому на этот раз идем направо.

Нашли! Теперь поищем другое число — 8. Поиск проходит точно по такому же пути.

Только на этот раз его там нет! Если бы искомый узел присутствовал в дереве, он находился бы в месте, обозначенном пунктиром. Собственно, все наши рассуждения о деревьях обусловлены одной необходимостью: знать, работают ли они быстрее массивов и связанных списков. Итак, рассмотрим производительность деревьев, но для этого необходимо учитывать их высоту.

Короткие деревья работают быстрее

Рассмотрим два дерева. Оба дерева состоят из 7 узлов, но сильно различаются по производительности.

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

Помните игру с отгадыванием чисел? Чтобы угадать число из набора 100 чисел, бинарный поиск потребует 7 попыток, а простой — 100. Нечто похожее происходит и с деревьями.

Дерево для худшего случая выше, и у него хуже производительность. В нем все узлы выстроены в одну линию. Дерево имеет высоту O (n), так что поиск будет выполняться за время O (n). Это можно представить так: дерево в действительности напоминает связанный список, так как один узел содержит ссылку на другой и т. д. А поиск по связанному списку выполняется за время O (n).
Дерево для лучшего случая имеет высоту O (log n), а поиск по нему займет время O (log n).

Таким образом, ситуация очень похожа на сравнение бинарного поиска с простым! Если можно обеспечить высоту дерева в O (log n), то поиск по дереву будет выполняться за время O (log n) — именно то, что требовалось.

Но как добиться, чтобы высота составляла O (log n)? В следующем примере мы построим дерево, которое оказывается деревом для худшего случая (а этого нам желательно избежать). Начнем с одного узла, затем добавим другой.

Пока неплохо. Добавим еще несколько узлов.

Узлы приходится добавлять справа, потому
что все они больше всех своих предшественников.

Получается дерево для худшего случая — его высота равна O (n)! Короткие деревья работают быстрее. Кратчайшее время для BST может составлять O (log n). Чтобы укоротить BST, необходимо сбалансировать его.

Подводя итог, хочется сказать одно.
Пора грокать алгоритмы по-новому!

Более подробно с книгой можно ознакомиться на сайте издательства:

» Оглавление

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Грокаем

© Habrahabr.ru