М. А. Бабенко , М. В. Левин - Введение в теорию алгоритмов и структур данных

М. А. Бабенко, М. В. Левин

Введение в теорию алгоритмов
и структур данных

Электронное издание

Москва
МЦНМО
2016

УДК 519.72
ББК 32.81
Б12
Бабенко М. А., Левин М. В.
Введение в теорию алгоритмов и структур данных
Электронное издание
М.: МЦНМО, 2016
144 с.
ISBN 978-5-4439-2396-3
В курсе дается краткое изложение классических способов построения и анализа алгоритмов. Первая часть курса, представленная в данном пособии, в большей степени сконцентрирована на
базовых структурах данных, а также задачах сортировки и поиска.
Теоретический материал дополняется рядом задач.
Несмотря на «олимпиадный» вид, многие из них имеют под
собой вполне практическую основу и представляют собой модельные варианты тех проблем, с которыми приходится сталкиваться
на практике.
Знания, которые даются в этой книге, представляют собой
необходимую (хотя и недостаточную) базу для работы с произвольными данными большого объема, дают понимание о возможности
или невозможности точного решения конкретных задач за приемлемое на практике время.

Подготовлено на основе книги:
Бабенко М. А., Левин М. В. Введение в теорию алгоритмов и структур
данных. –– М.: ФМОП, МЦНМО, 2012. –– 144 с. –– ISBN 978-5-94057-957-1

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11,
тел. (499)241–08–04.
http://www.mccme.ru

ISBN 978-5-4439-2396-3

c Бабенко М. А., Левин М. В., 2012.
c МЦНМО, 2016.

Оглавление
Предисловие (Елена Бунина) . . . . . . . . . . . . . . . . . . . .
Глава 1. Введение . . . . . . . . . .
1.1. Массивы переменного размера
1.2. Анализ учетных стоимостей .
1.3. Задачи . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

6
7
9
11

Глава 2. Сортировка . . . . . . . . . . . . . .
2.1. Введение . . . . . . . . . . . . . . . . . .
2.2. Квадратичная сортировка . . . . . . . .
2.3. Оптимальная сортировка, основанная на
2.4. Сортировка слиянием . . . . . . . . . . .
2.5. Быстрая сортировка . . . . . . . . . . . .
2.6. Порядковые статистики . . . . . . . . . .
2.7. Задачи . . . . . . . . . . . . . . . . . . . .

. . . . . . . .
. . . . . . . .
. . . . . . . .
сравнениях .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

16
16
17
18
20
23
30
33

Глава 3. Поиск . . . .
3.1. Введение . . . .
3.2. Линейный поиск
3.3. Бинарный поиск
3.4. Деревья поиска .
3.5. Сплей-деревья .
3.6. Задачи . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

39
39
40
40
42
47
54

Глава 4. Кучи . . . . . . . . . . . . . . . . . .
4.1. Приоритетные очереди . . . . . . . . . .
4.2. Бинарные кучи . . . . . . . . . . . . . . .
4.3. Сортировка кучей . . . . . . . . . . . . .
4.4. k-ичные кучи . . . . . . . . . . . . . . . .
4.5. Сливаемые приоритетные очереди . . . .
4.6. Левацкие кучи . . . . . . . . . . . . . . .
4.7. Косые кучи . . . . . . . . . . . . . . . . .
4.8. Структуры данных с хранением истории

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

62
62
63
68
70
71
72
74
76

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

5

4

Оглавление

4.9. Декартовы деревья и дучи . . . . . . . . . . . . . . . . . . .
4.10. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77
82

Глава 5. Хеширование . . . . . . . . . . . . . . . . . .
5.1. Прямая адресация . . . . . . . . . . . . . . . . . .
5.2. Хеш-функции . . . . . . . . . . . . . . . . . . . . .
5.3. Примеры хеш-функций . . . . . . . . . . . . . . .
5.4. Вероятностный анализ алгоритмов хеширования
5.5. Совершенная хеш-функция . . . . . . . . . . . . --">