Алгоритмы и структуры данных с примерами на Python
Покупка
Новинка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Цзинь Юйдун
Перевод:
Шевкун И. А.
Год издания: 2025
Кол-во страниц: 494
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
Дополнительное образование
ISBN: 978-5-93700-424-6
Артикул: 890953.01.99
Цель этой книги — при помощи наглядных иллюстраций и исполняемых примеров кода помочь читателю понять ключевые идеи алгоритмов и структур данных и освоить их воплощение в программном коде. Если вам не хватает времени на чтение множества учебников, она станет спасательным кругом в океане знаний.
Книга будет особенно полезна всем, у кого есть начальные навыки программирования, но отсутствует четкое понимание алгоритмов и структур данных.
Более опытным читателям она поможет освежить и систематизировать знания об алгоритмах.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Цзинь Юйдун Алгоритмы и структуры данных c примерами на Python
Hello 算法 Python 语言版 作者:靳宇栋 (@krahets) 代码审阅:靳宇栋((@krahets)
Москва, 2025 Алгоритмы и структуры данных с примерами на Python Цзинь Юйдун (Jin Yudong) (@krahets) Перевод: И. А. Шевкун
УДК 004.421 ББК 32.973 Ц55 Цзинь Юйдун Ц55 Алгоритмы и структуры данных с примерами на Python / пер. с кит. И. А. Шевкуна. – М.: ДМК Пресс, 2025. – 494 с.: ил. ISBN 978-5-93700-424-6 Цель этой книги – при помощи наглядных иллюстраций и исполняемых примеров кода помочь читателю понять ключевые идеи алгоритмов и структур данных и освоить их воплощение в программном коде. Если вам не хватает времени на чтение множества учебников, она станет спасательным кругом в океане знаний. Книга будет особенно полезна всем, у кого есть начальные навыки программирования, но отсутствует четкое понимание алгоритмов и структур данных. Более опытным читателям она поможет освежить и систематизировать знания об алгоритмах. УДК 004.421 ББК 32.973 Russian translation rights ©2025. 《Hello算法》(ISBN: 978-7-115-63750-5) 作者: 靳宇栋 (@krahets) Russian translation rights are arranged with Posts & Telecom Press Co., Ltd. through Media Solutions, Tokyo Japan (info@mediasolutions.jp) Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Copyrights ©2024 Posts and Telecom Press © Оформление, издание, перевод, ДМК Пресс, 2025 ISBN (анг.) 978-7-115-63750-5 ISBN (рус.) 978-5-93700-424-6
Оглавление Предисловие........................................................................................ 8 Предисловие от издательства......................................................... 10 Отзывы и пожелания........................................................................................10 Список опечаток...............................................................................................10 Нарушение авторских прав..............................................................................10 Глава 0. Введение.............................................................................. 11 0.1. О книге........................................................................................................12 0.2. Как использовать эту книгу.......................................................................15 0.3. Резюме........................................................................................................23 Глава 1. Введение в алгоритмы....................................................... 24 1.1. Алгоритмы повсюду...................................................................................25 1.2. Что такое алгоритм....................................................................................30 1.3. Резюме........................................................................................................32 Глава 2. Анализ сложности............................................................... 34 2.1. Оценка эффективности алгоритмов.........................................................35 2.2. Итерация и рекурсия..................................................................................37 2.3. Временная сложность................................................................................46 2.4. Пространственная сложность....................................................................61 2.5. Резюме........................................................................................................67 Глава 3. Структуры данных.............................................................. 70 3.1. Классификация структур данных..............................................................71 3.2. Основные типы данных.............................................................................74 3.3. Кодирование чисел*...................................................................................76 3.4. Кодирование символов*............................................................................80 3.5. Резюме........................................................................................................89 Глава 4. Массивы и списки............................................................... 92 4.1. Массивы......................................................................................................93 4.2. Связные списки..........................................................................................99 4.3. Списки.......................................................................................................105 4.4. Память и кеш*...........................................................................................109 4.5. Резюме......................................................................................................113
Глава 5. Стек и очередь...................................................................118 5.1. Стек............................................................................................................119 5.2. Очередь.....................................................................................................126 5.3. Двусторонняя очередь.............................................................................133 5.4. Резюме......................................................................................................144 Глава 6. Хеш-таблицы.....................................................................146 6.1. Хеш-таблицы............................................................................................147 6.2. Хеш-коллизии...........................................................................................152 6.3. Алгоритмы хеширования........................................................................161 6.4. Резюме......................................................................................................167 Глава 7. Деревья...............................................................................170 7.1. Двоичные деревья....................................................................................171 7.2. Обход двоичного дерева...........................................................................177 7.3. Представление двоичного дерева с помощью массива........................184 7.4. Двоичное дерево поиска..........................................................................189 7.5. АВЛ-дерево*..............................................................................................199 7.6. Резюме......................................................................................................210 Глава 8. Куча.....................................................................................213 8.1. Куча...........................................................................................................214 8.2. Построение кучи.......................................................................................226 8.3. Поиск k наибольших элементов..............................................................229 8.4. Резюме......................................................................................................234 Глава 9. Графы..................................................................................236 9.1. Графы........................................................................................................237 9.2. Основные операции с графами...............................................................241 9.3. Обход графа..............................................................................................249 9.4. Резюме......................................................................................................262 Глава 10. Поиск................................................................................264 10.1. Двоичный поиск.....................................................................................265 10.2. Вставка с использованием двоичного поиска............................................................................................270 10.3. Двоичный поиск границ........................................................................276 10.4. Стратегии оптимизации хеширования................................................279 10.5. Переосмысление алгоритмов поиска...................................................282 10.6. Резюме.....................................................................................................286 Глава 11. Сортировка......................................................................287 11.1. Алгоритмы сортировки..........................................................................288 11.2. Сортировка выбором..............................................................................289 11.3. Сортировка пузырьком..........................................................................294 11.4. Сортировка вставками...........................................................................298 6 Оглавление
11.5. Быстрая сортировка...............................................................................301 11.6. Сортировка слиянием............................................................................310 11.7. Пирамидальная сортировка..................................................................316 11.8. Блочная сортировка...............................................................................324 11.9. Сортировка подсчетом...........................................................................327 11.10. Поразрядная сортировка.....................................................................334 11.11. Резюме...................................................................................................337 Глава 12. Разделяй и властвуй......................................................342 12.1. Стратегия «разделяй и властвуй»..........................................................343 12.2. Применение стратегии «разделяй и властвуй» для поиска................347 12.3. Задача построения двоичного дерева..................................................350 12.4. Задача о Ханойских башнях..................................................................357 12.5. Резюме.....................................................................................................363 Глава 13. Поиск с возвратом..........................................................365 13.1. Алгоритмы поиска с возвратом............................................................366 13.2. Задача о перестановках..........................................................................377 13.3. Задача о сумме подмножеств................................................................383 13.4. Задача об n ферзях.................................................................................391 13.5. Резюме.....................................................................................................395 Глава 14. Динамическое программирование.............................397 14.1. Введение в динамическое программирование....................................398 14.2. Особенности задач динамического программирования....................404 14.3. Подход к решению задач динамического программирования..........410 14.4. Задача о рюкзаке 0-1..............................................................................422 14.5. Задача о полном рюкзаке......................................................................434 14.6. Задача расстояния редактирования......................................................448 14.7. Резюме.....................................................................................................457 Глава 15. Жадность..........................................................................460 15.1. Жадные алгоритмы................................................................................461 15.2. Задача о дробном рюкзаке.....................................................................466 15.3. Задача о максимальной вместимости..................................................469 15.4. Задача о максимальном произведении разбиения.............................478 15.5. Резюме.....................................................................................................482 Глава 16. Приложение....................................................................483 16.1. Установка программной среды.............................................................484 16.2. Совместная разработка..........................................................................486 16.3. Глоссарий................................................................................................488 Оглавление 7
Предисловие Два года назад я опубликовал на платформе LeetCode сборник задач по книге Coding Interviews, который получил хорошие отклики от читателей. В ходе общения с ними мне чаще всего задавали вопрос: «С чего начать изучение алгоритмов?» Постепенно этот вопрос начал все больше меня занимать. Решение задач наугад, вслепую является, пожалуй, самым распространенным методом: он прост, прямолинеен и результативен. Однако этот процесс напоминает компьютерную игру «Сапер»: люди с высокой способностью к самообучению могут без особых проблем разминировать все клетки. А те, кому
не хватает базовой подготовки, могут легко подорваться и быстро потерять мотивацию. Другой распространенный подход – читать учебники от корки до корки. Но у тех, кто готовится к устройству на работу, значительная часть времени и сил уходит на получение диплома, составление резюме, подготовку к тестам и собеседованиям. В таких условиях чтение объемных книг превращается в серьезное испытание. Если вы сталкиваетесь с подобными трудностями, то считайте большой удачей, что эта книга «нашла» вас. Она представляет собой мой ответ на вопрос «Как войти в мир алгоритмов?». Возможно, это не самый совершенный ответ, но это точно искренняя попытка. Эта книга не гарантирует вам быстрого получения хорошего офера, но она поможет построить «карту знаний» по структурам данных и алгоритмам, познакомит с различными «минами», их формой, размером и расположением, а также научит «методам разминирования». Овладев этими знаниями, вы сможете увереннее решать задачи и читать научные статьи, постепенно формируя целостную систему знаний. Я полностью согласен со словами Ричарда Фейнмана: «Знания не бесплатны. За них нужно платить вниманием». В этом смысле эта книга вовсе не бесплатна. И чтобы оправдать ваше драгоценное внимание, я вложу максимум усилий в ее создание. Осознавая ограниченность собственных знаний и опыта, я понимаю, что, несмотря на многократные доработки, в книге все же могут оставаться ошибки. Буду искренне признателен за критику и замечания от преподавателей и студентов. Исходные коды из книги доступны в виде исполняемых файлов в репозитории по адресу github.com/krahets/hello-algo. Формат PDF не очень хорошо подходит для анимированных изображений, поэтому для лучшего восприятия можно обратиться к веб-версии по адресу https://www.hello-algo.com/en (на англ.). Предисловие 9
Предисловие от издательства Отзывы и пожелания Мы всегда рады отзывам наших читателей. Расскажите нам, что вы думаете об этой книге – что понравилось или, может быть, не понравилось. Отзывы важны для нас, чтобы выпускать книги, которые будут для вас максимально полезны. Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на страницу книги и оставив комментарий в разделе «Отзывы и рецензии». Также можно послать письмо главному редактору по адресу dmkpress@gmail.com; при этом укажите название книги в теме письма. Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http://dmkpress.com/ authors/publish_book/ или напишите в издательство по адресу dmkpress@gmail.com. Список опечаток Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое качество наших текстов, ошибки все равно случаются. Если вы найдете ошибку в одной из наших книг – возможно, ошибку в основном тексте или программном коде, – мы будем очень благодарны, если вы сообщите нам о ней. Сделав это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги. Если вы найдете какие-либо ошибки в коде, пожалуйста, сообщите о них главному редактору по адресу dmkpress@gmail.com, и мы исправим это в следующих тиражах. Нарушение авторских прав Пиратство в интернете по-прежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к вопросам защиты авторских прав и лицензирования. Если вы столкнетесь в интернете с незаконной публикацией какой-либо из наших книг, пожалуйста, пришлите нам ссылку на интернет-ресурс, чтобы мы могли применить санкции. Ссылку на подозрительные материалы можно прислать по адресу dmkpress@gmail.com. Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.