mirror of
https://github.com/krahets/hello-algo.git
synced 2026-07-09 20:46:43 +08:00
338 lines
29 KiB
Markdown
338 lines
29 KiB
Markdown
# Введение
|
||
|
||
{width="4.60417760279965in" height="5.958333333333333in"}
|
||
|
||
1. **О книге**
|
||
|
||
> Этот проект задуман как открытое, бесплатное и дружелюбное к новичкам введение в структуры данных и алгоритмы.
|
||
|
||
1. В книге используются анимационные иллюстрации. Материал изложен ясно и последовательно, что облегчает освоение и помогает начинаю- щим построить «карту знаний» по структурам данных и алгоритмам.
|
||
|
||
2. Исходный код можно запустить одним кликом, что позволяет трениро- ваться, развивать навыки программирования и формировать понима- ние принципов работы алгоритмов и реализации структур данных на фундаментальном уровне.
|
||
|
||
3. Мы призываем к взаимопомощи читателей: задавайте вопросы и дели- тесь идеями в комментариях. Обсуждения помогают двигаться вперед всем вместе.
|
||
|
||
### Целевая аудитория
|
||
|
||
> Если вы новичок в алгоритмах, никогда с ними не сталкивались или у вас есть некоторый опыт решения задач, но еще нет четкого понимания структур дан- ных и алгоритмов, эта книга создана специально для вас!
|
||
>
|
||
> Если у вас уже есть определенный опыт решения задач и вы знакомы с боль- шинством типов задач, эта книга поможет вам освежить и систематизировать знания об алгоритмах. Исходный код может служить набором инструментов для решения задач или алгоритмическим словарем.
|
||
>
|
||
> Если вы владеете алгоритмами на экспертном уровне, мы будем рады ва- шим ценным советам или совместному участию в создании книги.
|
||
|
||
### Структура книги
|
||
|
||
> Основное содержание книги представлено на рис. 0.1.
|
||
|
||
1. **Анализ сложности**: критерии и методы оценки структур данных и ал- горитмов. Методы расчета временной и пространственной сложности, распространенные типы, примеры и т. д.
|
||
|
||
> **Структуры данных**
|
||
>
|
||
> **Структуры данных**
|
||
>
|
||
> **Массивы и списки**
|
||
>
|
||
> **Стек**
|
||
>
|
||
> **[и]{.smallcaps} очередь**
|
||
>
|
||
> **Хеш- таблицы**
|
||
>
|
||
> Логическая и физическая структура Базовые типы данных
|
||
>
|
||
> Цифровое и символьное кодирование
|
||
>
|
||
> Способы непрерывного и распределенного хранения Методы работы, преимущества
|
||
>
|
||
> [и]{.smallcaps} недостатки двух способов
|
||
>
|
||
> Реализация списка на основе динамического массива
|
||
>
|
||
> Память и кеш в компьютере
|
||
>
|
||
> Последний пришел -- первый вышел, первый пришел -- первый вышел, двусторонняя очередь
|
||
>
|
||
> Реализация на основе массива и связного списка
|
||
>
|
||
> Принцип работы хеш-таблицы, реализация на основе массива
|
||
>
|
||
> Хеш-коллизии, цепная и открытая адресация Назначение и цели хеш-алгоритмов
|
||
>
|
||
> Идеальное, совершенное, полное, сбалансированное
|
||
>
|
||
> двоичное дерево
|
||
>
|
||
> **Анализ сложности**
|
||
>
|
||
> **Итерация и рекурсия**
|
||
>
|
||
> **Временная сложность**
|
||
>
|
||
> **Пространственная сложность**
|
||
>
|
||
> **Поиск**
|
||
>
|
||
> Циклы for и while, вложенные циклы
|
||
>
|
||
> Стек вызовов рекурсии, хвостовая рекурсия, дерево рекурсии
|
||
>
|
||
> Сравнение итерации и рекурсии
|
||
>
|
||
> Асимптотическая верхняя граница
|
||
>
|
||
> Методы вычисления, основные типы
|
||
>
|
||
> Наихудшая, наилучшая, средняя временная сложность
|
||
>
|
||
> Методы вычисления, основные типы Компромисс между временем
|
||
>
|
||
> и пространством
|
||
>
|
||
> Перебор: линейный поиск, поиск в ширину и глубину
|
||
>
|
||
> Адаптивный поиск: двоичный поиск, хеш-поиск, поиск по дереву
|
||
>
|
||
> Выбор алгоритма поиска
|
||
>
|
||
> Местность, устойчивость, адаптивность, основанность на сравнении
|
||
>
|
||
> Перебор: сортировка выбором, пузырьком, вставками
|
||
|
||
**Деревья**
|
||
|
||
**Куча**
|
||
|
||
**Графы**
|
||
|
||
https://github.com/krahets/hello-algo
|
||
|
||
> Представление связным списком и массивом, сравнение Обход в ширину; прямой, симметричный и обратный порядок Двоичное дерево поиска
|
||
>
|
||
> АВЛ-дерево
|
||
>
|
||
> Минимальная и максимальная куча, **Алгоритмы**
|
||
>
|
||
> очередь с приоритетом
|
||
>
|
||
> Реализация кучи на основе массива, операция построения кучи
|
||
>
|
||
> Задача о k наибольших элементов
|
||
>
|
||
> Ориентированный, связный и взвешенный графы Список и матрица смежности, их сравнение Обход в ширину и в глубину
|
||
>
|
||
> **Сортировка**
|
||
>
|
||
> **Разделяй и властвуй**
|
||
>
|
||
> **Поиск**
|
||
>
|
||
> **с возвратом**
|
||
>
|
||
> **Динамическое программирование**
|
||
>
|
||
> **Жадные алгоритмы**
|
||
>
|
||
> «Разделяй и властвуй»: быстрая сортировка, сортировка слиянием, пирамидальная сортировка
|
||
>
|
||
> Без сравнения: блочная сортировка,
|
||
>
|
||
> сортировка подсчетом, поразрядная сортировка Стратегия «разделяй и властвуй»
|
||
>
|
||
> Примеры задач: двоичный поиск, построение дерева, Ханойская башня
|
||
>
|
||
> Задача поиска с возвратом, каркас кода
|
||
>
|
||
> Примеры задач: перестановки, сумма подмножеств, n ферзей
|
||
>
|
||
> Перебор, рекурсия с мемоизацией, восходящая рекурсия
|
||
>
|
||
> Перекрывающиеся подзадачи, оптимальная подструктура, отсутствие последействия
|
||
>
|
||
> Методы определения задач динамического программирования, этапы решения
|
||
>
|
||
> Примеры задач: рюкзак 0-1, полный рюкзак, расстояние редактирования
|
||
>
|
||
> Характеристики жадных задач, этапы решения
|
||
>
|
||
> Примеры задач: дробный рюкзак, максимальная вместимость, максимальное произведение разбиения
|
||
>
|
||
> 0.1. О книге ❖ **13**
|
||
|
||
2. **Структуры данных**: классификация основных типов данных и структур данных. Определение, преимущества и недостатки, основные операции, распространенные типы, типичные приложения и методы реализации мас- сивов, списков, стеков, очередей, хеш-таблиц, деревьев, куч, графов и т. д.
|
||
|
||
3. **Алгоритмы**: определение, преимущества и недостатки, эффективность, области применения, этапы решения и примеры задач для поиска, со- ртировки, алгоритма «разделяй и властвуй», обратного поиска, динами- ческого программирования, жадных алгоритмов и т. д.
|
||
|
||
### Благодарности
|
||
|
||
> Эта книга постоянно совершенствуется благодаря совместным усилиям множества участников открытого сообщества. Благодарим каждого автора, вложившего свое время и силы. Имена перечислены в порядке, автоматически сгенерированном GitHub: krahets, coderonion, Gonglja, nuomi1, Reanon, justin-tse, hpstory, danielsss, curtishd, night-cruise, S-N-O-R-L-A-X, msk397, gvenusleo, khoaxuantu, RiverTwilight, rongyi, gyt95, zhuoqinyue, K3v123, Zuoxun, mingXta, hello-ikun, FangYuan33, GN-Yu, yuelinxin, longsizhuo, Cathay-Chen, guowei-gong, xBLACKICEx, IsChristina, JoseHu- ng, qualifier1024, QiLOL, pengchzn, Guanngxu, L-Super, WSL0809, Slone123c, lhxsm, yuan0221, what-is-me, theNefelibatas, longranger2, cy-by-side, xiongsp, Jefferson- Huang, Transmigration-zhou, magentaqin, Wonderdch, malone6, xiaomiusa87, gaofer, bluebean-cloud, a16su, Shyam-Chen, nanlei, hongyun-robot, Phoenix0415, MolDuM, Nigh, he-weilai, junminhong, mgisr, iron-irax, yd-j, XiaChuerwu, XC-Zero, seven1240, SamJin98, wodray, reeswell, NI-SW, Horbin-Magician, Enlightenus, xjr7670, YangXu- anyi, DullSword, boloboloda, iStig, qq909244296, jiaxianhua, wenjianmin, keshida, kilikilikid, lclc6, lwbaptx, liuxjerry, lucaswangdev, lyl625760, hts0000, gledfish, fbigm, echo1937, szu17dmy, dshlstarr, Yucao-cy, coderlef, czruby, bongbongbakudan, beinten- tional, ZongYangL, ZhongYuuu, luluxia, xb534, bitsmi, ElaBosak233, baagod, zhouLion, yishangzhang, yi427, yabo083, weibk, wangwang105, th1nk3r-ing, tao363, 4yDX3906, syd168, steventimes, sslmj2020, smilelsb, siqyka, selear, sdshaoda, Xi-Row, popozhu, nuquist19, noobcodemaker, XiaoK29, chadyi, ZhongGuanbin, shanghai-Jerry, JackYang- hellobobo, Javesun99, lipusheng, BlindTerran, ShiMaRing, FreddieLi, FloranceYeh, iF- leey, fanchenggang, gltianwen, goerll, Dr-XYZ, nedchu, curly210102, CuB3y0nd, KraHsu, CarrotDLaw, youshaoXG, bubble9um, fanenr, eagleanurag, LifeGoesOnionOnionOnion, 52coder, foursevenlove, KorsChen, hezhizhen, linzeyan, ZJKung, GaochaoZhu, hopk- ings2008, yang-le, Evilrabbit520, Turing-1024-Lee, thomasq0, Suremotoo, Allen-Scai, Risuntsy, Richard-Zhang1019, qingpeng9802, primexiao, nidhoggfgg, 1ch0, MwumLi, martinx, ZnYang2018, hugtyftg, logan-qiu, psychelzh, Keynman, KeiichiKasai и 0130w. Рецензирование кода книги выполнили coderonion, curtishd, Gonglja, gve- nusleo, hpstory, justin-tse, khoaxuantu, krahets, night-cruise, nuomi1, Reanon и ron- gyi (в алфавитном порядке). Благодарим их за потраченное время и усилия, ко-
|
||
|
||
торые обеспечили стандартизацию и единообразие кода на различных языках.
|
||
|
||
> В процессе создания этой книги мне помогало много людей.
|
||
|
||
1. Благодарю моего наставника в компании, доктора Ли Си (Li Xi), который в одной из бесед вдохновил меня «действовать быстро», что укрепило мою решимость написать эту книгу.
|
||
|
||
2. Благодарю мою девушку Паo Пао (Pao Pao), которая, будучи первым чи- тателем книги, дала множество ценных советов с точки зрения новичка в алгоритмах, что сделало книгу более понятной и доступной.
|
||
|
||
3. Благодарю Тен Бао (Teng Bao), Ци Бао (Qi Bao) и Фей Бао (Fei Bao) за креа- тивное название книги, которое навевает приятные воспоминания о на- писании первой строки кода «Hello World!».
|
||
|
||
4. Благодарю Сяо Цюань (Xiao Quan) за профессиональную помощь в во- просах интеллектуальной собственности, что сыграло важную роль в со- вершенствовании этой открытой книги.
|
||
|
||
5. Благодарю Су Тун (Su Tong) за дизайн обложки и логотипа книги, а также за терпение при многократных исправлениях по моим просьбам.
|
||
|
||
6. Благодарю \@squidfunk за советы по оформлению и за разработку от- крытой темы документации Material-for-MkDocs.
|
||
|
||
> В процессе написания я ознакомился с множеством учебников и статей по структурам данных и алгоритмам. Эти работы послужили отличным образцом для этой книги, обеспечив ее точность и качество. Выражаю благодарность всем преподавателям и предшественникам за их выдающийся вклад!
|
||
>
|
||
> Настоящая книга пропагандирует метод обучения, сочетающий умственную и практическую деятельность, на который меня вдохновила книга Dive into Deep Learning («Погружение в глубокое обучение», на англ. языке). Настоятель- но рекомендую эту замечательную работу всем читателям.
|
||
>
|
||
> **Сердечно благодарю своих родителей, ведь именно ваша постоянная поддержка и ободрение дали мне возможность заняться этим увлека- тельным делом.**
|
||
|
||
#### как использовать эту книгу
|
||
|
||
### Стиль изложения
|
||
|
||
- Главы, имеющие символ \* после заголовка, являются дополнительными и содержат более сложный материал. Если у вас ограничено время, мож- но их пропустить.
|
||
|
||
- Профессиональные термины выделяются полужирным шрифтом (в печат- ной и PDF-версии) или подчеркиванием (в веб-версии), например **массив** (array). Рекомендуется запоминать их для удобства чтения литературы.
|
||
|
||
- Важные моменты и обобщающие фразы выделяются **полужирным шрифтом**, на такие тексты следует обращать особое внимание.
|
||
|
||
- При упоминании терминов, различающихся в разных языках програм- мирования, в качестве стандарта используется Python, например None для обозначения «пустого значения».
|
||
|
||
- В некоторых местах книга отходит от стандартов комментирования про- граммного кода ради более компактного оформления. Комментарии де- лятся на три типа: заголовочные, содержательные и многострочные.
|
||
|
||
> \"\"\" Заголовочные комментарии, используются для обозначения функций, классов, тестовых примеров и т.д. \"\"\"
|
||
>
|
||
> \# Содержательные комментарии, используются для пояснения кода.
|
||
>
|
||
> \"\"\"
|
||
>
|
||
> Многострочные комментарии. \"\"\"
|
||
|
||
### Эффективное обучение с помощью анимированных иллюстраций
|
||
|
||
> Видео и изображения обладают более высокой плотностью информации и структурированностью по сравнению с текстом, что облегчает понимание. В этой книге **ключевые и сложные моменты в основном представлены в виде анимированных иллюстраций**, а текстовая информация служит по- яснением и дополнением.
|
||
>
|
||
> Если какой-либо раздел в книге сопровождается анимационной иллюстра- цией, как на рис. 0.2, **используйте иллюстрацию в качестве основного ис- точника информации, а текст -- в качестве вспомогательного**.
|
||
|
||
{width="5.06667760279965in" height="3.4239577865266844in"}
|
||
|
||
> **Рис. 0.2.** Пример анимационной иллюстрации. Шаг 1
|
||
>
|
||
> {width="5.066665573053369in" height="3.4239577865266844in"}
|
||
|
||
{width="5.066665573053369in" height="3.4239577865266844in"}
|
||
|
||
> **Рис. 0.2.** *Продолжение*. Шаги 2--3
|
||
>
|
||
> {width="5.066665573053369in" height="3.4239577865266844in"}
|
||
|
||
{width="5.066674321959755in" height="3.4239577865266844in"}
|
||
|
||
> **Рис. 0.2.** *Окончание*. Шаги 4--5
|
||
|
||
### Углубление понимания через практику написания кода
|
||
|
||
> Сопроводительный код размещен в репозитории GitHub, **он содержит тесто- вые примеры и может быть запущен одним нажатием кнопки**, как по- казано на рис. 0.3.
|
||
|
||
{width="5.0666863517060365in" height="3.4239577865266844in"}
|
||
|
||
> **Рис. 0.3.** Запуск примера кода
|
||
>
|
||
> Если позволяет время, **рекомендуется самостоятельно набирать код**. Если время ограничено, по крайней мере **просмотрите и выполните весь код**.
|
||
>
|
||
> Процесс написания кода приносит больше пользы, чем его чтение. **Настоя- щее обучение -- это обучение на практике**.
|
||
>
|
||
> Предварительная подготовка для запуска кода включает три этапа.
|
||
|
||
1. **Установка локальной среды программирования**. Следуйте инструк- циям программы установки. Если среда уже установлена, этот шаг мож- но пропустить.
|
||
|
||
2. **Клонирование или загрузка репозитория кода**. Перейдите в репози- торий GitHub. Если у вас установлена утилита Git, можно клонировать репозиторий с помощью следующей команды:
|
||
|
||
> git clone https://github.com/krahets/hello-algo.git
|
||
>
|
||
> Либо можно нажать кнопку **Download ZIP** (Скачать ZIP-архив), как показа- но на рис. 0.4, загрузить архив с кодом и затем распаковать его на локальном компьютере.
|
||
>
|
||
> 
|
||
>
|
||
> **Рис. 0.4.** Клонирование репозитория и загрузка кода
|
||
|
||
3. **Запуск исходного кода**. Если для блока кода в книге указано имя фай- ла, этот файл можно найти в папке codes репозитория, как показано на рис. 0.5. Исходный код можно запустить одним нажатием, что поможет вам сэкономить время на отладку и сосредоточиться на изучении ма- териала.
|
||
|
||
|
||
|
||
> **Рис. 0.5.** Блоки кода и соответствующие файлы исходного кода
|
||
>
|
||
> Помимо локального запуска, **в веб-версии книги код на Python можно выполнить в визуальной среде** (реализовано на основе pythontutor). Для этого нажмите кнопку **Визуализировать выполнение** под блоком кода, как показано на рис. 0.6. Также в раскрывшемся окне можно нажать кнопку **От- крыть в полноэкранном режиме** для более удобного просмотра1.
|
||
|
||
{width="5.122829177602799in" height="3.12in"}
|
||
|
||
> **Рис. 0.6.** Визуальное выполнение кода Python
|
||
|
||
### Совместное развитие через вопросы и обсуждения
|
||
|
||
> При чтении книги не оставляйте без внимания непонятные моменты. **Мы при- зываем вас задавать вопросы в разделе комментариев**, и я вместе с колле- гами постараюсь ответить вам в течение двух дней.
|
||
>
|
||
> В конце каждой главы веб-версии книги предусмотрено место для коммен- тариев, как показано на рис. 0.7. Рекомендуется уделять внимание содержимо- му этой области. С одной стороны, это позволит вам понять, с какими пробле- мами сталкиваются другие читатели, что поможет выявить пробелы в знаниях и стимулировать более глубокое понимание. С другой стороны, мы надеемся, что вы будете отвечать на вопросы других участников и делиться своими мне- ниями.
|
||
>
|
||
> 1 Функция визуального выполнения кода доступна только в китайской веб-версии книги -- *Прим. перев*.
|
||
>
|
||
> {width="5.066666666666666in" height="3.4239577865266844in"}
|
||
>
|
||
> **Рис. 0.7.** Пример раздела комментариев
|
||
|
||
### Дорожная карта изучения алгоритмов
|
||
|
||
> Процесс изучения структур данных и алгоритмов можно разделить на три этапа.
|
||
|
||
1. **Введение в алгоритмы**. Необходимо ознакомиться с особенностями и применением различных структур данных, изучить принципы, про- цессы, назначение и эффективность различных алгоритмов.
|
||
|
||
2. **Решение алгоритмических задач**. Рекомендуется начинать с популяр- ных задач и решить не менее 100 из них, чтобы познакомиться с основ- ными алгоритмическими проблемами. При первом решении задач вы можете столкнуться с так называемым забвением знаний -- не беспокой- тесь, это нормально. Следуйте при повторении задач кривой забывания Эббингауза, обычно после 3--5 циклов повторения они хорошо запоми- наются. Рекомендуемые списки задач и планы решения можно найти в **этом репозитории GitHub**.
|
||
|
||
3. **Построение системы знаний**. В процессе обучения можно читать статьи по алгоритмам, изучать типичные решения и учебники по алгоритмам, чтобы постоянно обогащать систему знаний. В решении задач можно при- менять продвинутые стратегии, такие как классификация по темам, множе- ственные решения одной задачи или одно решение для множества задач. Советы по этим техникам обучения можно найти в различных сообществах.
|
||
|
||
> Эта книга в основном охватывает первый этап и призвана помочь вам эф- фективно подготовиться ко второму и третьему этапам обучения, как показа- но на рис. 0.8.
|
||
|
||
1. Резюме ❖ **23**
|
||
|
||
> *Этап 1*
|
||
>
|
||
> **Базовые сведения**
|
||
>
|
||
> *Этап 2*
|
||
>
|
||
> **Тренировка навыков**
|
||
>
|
||
> *Этап 3*
|
||
>
|
||
> **Построение системы знаний**
|
||
>
|
||
> **Решение алгоритмических задач**
|
||
>
|
||
> **Периодическое повторение** *Повторное решение одной и той же задачи через определенное время*
|
||
>
|
||
> *для формирования долговременной памяти и углубления понимания*
|
||
>
|
||
> **Активное обобщение** *Систематизация содержа*- *ния, выявление законо*-
|
||
>
|
||
> *мерностей для построения целостной системы знаний*
|
||
|
||
#### резюме
|
||
|
||
> **Рис. 0.8.** Дорожная карта изучения алгоритмов
|
||
|
||
- Основная аудитория книги -- новички в изучении алгоритмов. Если у вас уже есть определенная база, книга поможет систематизировать имею- щиеся знания об алгоритмах, а исходный код послужит инструменталь- ной библиотекой для решения задач.
|
||
|
||
- Содержание книги включает три основные части -- анализ сложности, структуры данных и алгоритмы -- и охватывает большинство тем в этой области.
|
||
|
||
- Для новичков в алгоритмах крайне важно изучить начальные разделы книги, чтобы избежать множества ошибок в будущем.
|
||
|
||
- Анимированные иллюстрации в книге обычно используются для пред- ставления ключевых и сложных аспектов. При чтении книги следует уде- лять этим материалам большое внимание.
|
||
|
||
- Практика -- лучший способ изучения программирования. Настоятельно рекомендуется запускать исходный код и самостоятельно писать про- граммы.
|
||
|
||
- В веб-версии книги каждая глава имеет область комментариев, где вы можете задавать вопросы и делиться своим мнением.
|
||
|
||
> Глава 1
|