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

Мы снова возвращаемся с вторым изданием книги “Грокаем алгоритмы”! Красивым, новеньким, актуализированным. От первого тиража всё ещё пахнет типографией, а код примеров обновлен на 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% по купону — Грокаем