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

ЛЕКЦИИ ШКОЛЫ
АНАЛИЗА ДАННЫХ ЯНДЕКСА

ИЗДАНИЕ ОСУЩЕСТВЛЯЕТСЯ
ПРИ ПОДДЕРЖКЕ КОМПАНИИ «ЯНДЕКС»

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

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

Об авторах

Бабенко Максим Александрович
Доцент кафедры алгоритмов и технологий программирования ФИВТ МФТИ. Кандидат физико-математических наук.
Заведующий базовой кафедрой Яндекса факультета компьютерных наук НИУ ВШЭ. Зам. директора отделения компьютерных наук Школы Анализа Данных.
Руководитель группы разработки технологий распределенных вычислений в компании Яндекс.
С 2004 года тренирует национальные команды школьников 
и студентов для международных олимпиад по программированию.

Левин Михаил Викторович
С 2010 года – технический руководитель качества рекламы в компании Яндекс. Руководитель группы разработки в 
компании Яндекс.
В прошлом – один из авторов анализатора «Яндекс.Пробки». Руководитель стажировок Школы Анализа Данных.
Победитель международных студенческих соревнований по
программированию. С 2007 г. тренирует команды студентов
для международных олимпиад по программированию.
С 2007 по 2009 г. инженер московского офиса Google.

ISBN 978-5-4439-0240-1

9 785443 902401 >

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

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

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

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

Москва
МЦНМО
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.

Оглавление

Предисловие (Елена Бунина) . . . . . . . . . . . . . . . . . . . .
5

Глава 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.1. Массивы переменного размера . . . . . . . . . . . . . . . . .
7
1.2. Анализ учетных стоимостей . . . . . . . . . . . . . . . . . .
9
1.3. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11

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

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

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

Оглавление

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

Глава 5. Хеширование
. . . . . . . . . . . . . . . . . . . . . . . .
85
5.1. Прямая адресация . . . . . . . . . . . . . . . . . . . . . . . .
85
5.2. Хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
5.3. Примеры хеш-функций . . . . . . . . . . . . . . . . . . . . .
89
5.4. Вероятностный анализ алгоритмов хеширования . . . . . .
90
5.5. Совершенная хеш-функция . . . . . . . . . . . . . . . . . . .
94
5.6. Фильтр Блюма . . . . . . . . . . . . . . . . . . . . . . . . . .
97
5.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98

Глава 6. Системы непересекающихся множеств . . . . . . . . . .
102
6.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . .
102
6.2. Лес непересекающих множеств . . . . . . . . . . . . . . . . .
103
6.3. Дополнительные операции . . . . . . . . . . . . . . . . . . .
107
6.4. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108

Глава 7. Задачи RMQ и LCA
. . . . . . . . . . . . . . . . . . . .
115
7.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . .
115
7.2. Динамическая задача RMQ, деревья отрезков . . . . . . . .
115
7.3. Статическая задача RMQ, предобработка . . . . . . . . . .
119
7.4. Задача LCA, сведение к задаче RMQ . . . . . . . . . . . . .
121
7.5. Декартово дерево, сведение задачи RMQ к задаче LCA . .
122
7.6. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
125

Глава 8. Динамическое программирование
. . . . . . . . . . . .
131
8.1. Наибольшая возрастающая подпоследовательность . . . . .
131
8.2. Перемножение последовательности матриц
. . . . . . . . .
136
8.3. Общие принципы . . . . . . . . . . . . . . . . . . . . . . . . .
138
8.4. Сегментация запросов . . . . . . . . . . . . . . . . . . . . . .
141

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . .
144

Предисловие

Книга М. А. Бабенко и М. В. Левина является учебным пособием
к курсу «Алгоритмы и структуры данных поиска», который авторы
читают в течение последних 5 лет в Школе анализа данных Яндекса.
Это пособие примечательно тем, что помимо теории, содержащейся обычно в книгах и заметках лекций по Computer Science,
к каждой главе приведено несколько примеров практических задач
с решениями и техническими комментариями по реализации.
Пособием можно пользоваться и как самостоятельным введением
в теорию алгоритмов, однако авторы убеждены, что решение практических задач, реализация их на каком-нибудь языке программирования и прохождение Code Review являются важнейшей и неотъемлемой частью курса, которую, к сожалению, невозможно включить
в книгу.
Данная книга покрывает только первую часть курса алгоритмов,
вторая часть находится в разработке.

Елена Бунина,
Директор отделения Сomputer Science,
профессор кафедры высшей алгебры
механико-математического факультета
МГУ им. М. В. Ломоносова,
доктор физико-математических наук.

Глава 1. Введение

Представленная вашему вниманию работа составлена по мотивам
лекций и семинаров курса «Алгоритмы и структуры данных для
поиска», читаемого в Школе анализа данных Яндекса. Полный курс
состоит из двух семестров, мы же пока публикуем материалы первого
из них с надеждой, что в скором времени мы найдем в себе силы
подготовить также и вторую часть.
Как уже было отмечено выше, занятия состоят из лекций и семинаров. На лекциях обсуждаются разнообразные теоретические вопросы, а также изучаются приемы реализации стандартных алгоритмов.
Семинары в большей степени ориентированы на решение задач.
Новые комплекты практических заданий периодически выдаются
на семинарах, и слушатели должны в течение установленного срока
прислать свое решение. Решение состоит из двух частей: теоретическое обоснование выбранного метода (включая оценки сложности)
и практическая реализация. В качестве последней принимается код
на языке C++.
Реализации, присылаемые студентами Школы, проверяются в автоматическом режиме на наборе заранее подготовленных тестов. Для
прохождения теста необходимо выдать правильный ответ, не превышая
при этом установленного предела по ресурсам (времени и памяти). Решение засчитывается в случае, если оно успешно проходит все тесты.
С учетом этого процесса и был написан данный конспект. Структурно он состоит из набора глав, каждая из которых фокусируется
на определенном разделе теории. В конце каждой главы вы найдете примеры задач. Для многих задач мы приводим формат вводавывода, который ожидается от программ, а также несколько примеров входных и выходных данных. Часть из этих задач, впрочем, более
теоретическая, поэтому для них подобных форматов не приводится.
Для всех задач вы найдете описание теоретической части решения
в форме, близкой к той, что ожидается от слушателей. Некоторые из

1.1. Массивы переменного размера
7

этих описаний не вполне формальны, но надеемся, что придирчивый
читатель простит нам подобные вольности.

Несмотря на то что данный курс сам по себе является вводным, мы предполагаем, что читатель имеет хотя бы минимальное
представление о том, что из себя представляет программирование.
В частности, мы предполагаем известными основные понятия какоголибо типичного императивного языка программирования.
Большинство примеров в данной книге будут проиллюстрированы
на языке C++. Причиной этого является его широкая распространенность в качестве практического средства, позволяющего писать
эффективный и переносимый код.
Помимо знания C++ как такового, мы считаем, что читатель
знаком со стандартной библиотекой языка. Это, конечно, не предполагает автоматического понимания устройства структур данных и алгоритмов, присутствующих там. Мы считаем известным разделение
на интерфейс и реализацию. В случае со стандартной библиотекой
речь идет о понимании ее интерфейсов, а также их неотъемлемой
части –– гарантии сложности операций. Такие гарантии определяют
поведение библиотечного кода в худшем случае.
И все же наша цель –– изучение базовых эффективных алгоритмов. Такая цель не предполагает привязку к какой-либо платформе
и библиотеке. В частности, желательно разобраться с тем, как именно
реализованы библиотечные средства.

1.1. Массивы переменного размера

Читатель, без сомнения, знаком с понятием массива. Массив ––
это средство языка C++, а не библиотеки. Библиотека же предлагает
более удобный аналог массива, а именно вектор (класс std::vector).
С точки зрения интерфейса ключевое различие между вектором
и массивом состоит в том, что массив имеет фиксированный, выбираемый в момент его создания размер, а вектор –– напротив, может
изменять количество лежащих в нем элементов динамически во время
работы. Как же реализуется такая возможность на практике? Вопрос
этот не вполне тривиальный, но достаточно простой, чтобы начать
изложение материалов курса с него.

Глава 1. Введение

Будем рассматривать простейший случай: нам необходимо предложить структуру данных, хранящую последовательность элементов переменной длины и поддерживающую операцию Insert добавления нового элемента в конец последовательности. Конечно, операция Insert
должна быть по возможности быстрой. Кроме того, должна быть возможность обратиться к любому элементу по его индексу за время O(1).
Последнее требование означает, что наиболее близкая к требуемой структура –– это обычный массив фиксированного размера, не
меньшего текущей длины последовательности. Такое решение также
упрощает (по крайней мере в языке С++) взаимодействие с кодом,
который ожидает получить на вход обычный массив. Этот массив
обычно задается указателем на свой начальный (нулевой) элемент,
и в случае вектора такой указатель всегда легко получить. Иными
словами, проектируемый нами вектор гарантирует непрерывное расположение своих элементов в памяти.
Поскольку длина массива в общем случае больше текущей длины последовательности, последнюю нужно явно хранить. Возникает
естественный вопрос: что же делать в случае, когда происходит вызов
Insert, а длина последовательности уже совпадает с длиной массива,
так что свободных элементов в конце его нет?
В этом случае придется выполнить операцию перевыделения
(reallocation): создать новый массив большего размера и скопировать
в него информацию из старого массива. Эта операция, конечно, не
бесплатная: ее временн´ая сложность пропорциональна количеству
элементов, подлежащих копированию.
Но как выбрать этот новый размер массива? К примеру, можно
было бы каждый раз увеличивать размер массива при перевыделении
на какое-либо постоянное количество элементов d. Такой метод называется аддитивным. Несложно убедиться, что общее время, которое
будет затрачено на выполнение последовательности из n операций
Insert, составляет1 Ω(n2).

1 Мы используем ряд стандартных обозначений асимптотического анализа. Для
положительных функций f и g записи f = O(g), f = Ω(g) обозначают соответственно, что найдется такая константа C > 0, что неравенства f ⩽C · g и f ⩾C · g
выполнены для всех достаточно больших значений аргументов. Если f = O(g)
и g = O(f), то пишем f = Θ(g).

1.2. Анализ учетных стоимостей
9

Упражнение 1.1.1. Скрытая константа в этой оценке зависит от d.
Как именно?

Квадратичную общую сложность последовательности из n вставок,
оказывается, возможно уменьшить до линейной. Для этого нужно использовать мультипликативный метод: получать новую длину умножением старой на некоторую константу α > 1. Для простоты положим
α = 2, так что размер массива каждый раз при необходимости будет
удваиваться (при этом, конечно, начинать нужно с длины 1, а не 0).
Доказать, что последовательность из n операций Insert будет
выполняться за время O(n), несложно и непосредственно. Сейчас,
однако, будет описан некоторый общий метод получения подобных
оценок, который впоследствии нам не раз пригодится.

1.2. Анализ учетных стоимостей

Будем изучать общую ситуацию, при которой имеется некоторая
структура данных S. Предположим, что над данной структурой данных выполняется последовательность операций a1, . . . , an. Каждая
операция ai требует определенных временн´ых затрат, которые мы
обозначим через c(ai). Числа c(ai) будем называть фактическими
стоимостями операций.
Обозначим через si состояние структуры S после выполнения i
операций (0 ⩽ i ⩽ n). В частности, s0 –– это начальное состояние до
выполнения операций, а sn –– заключительное состояние, в которое
структура переходит после выполнения всех операций из списка.
Наша задача состоит в том, чтобы оценить сумму времен, которые
затрачиваются на выполнение всех n операций, т. е.

n
i=1
c(ai).
(1.1)

Трудность получения оценки данной суммы связана с тем, что фактические стоимости зачастую слишком сильно различаются. Поэтому
оценка вида Cn, где C означает максимально возможную фактическую стоимость, может оказаться слишком грубой.
Предположим, что с каждым из состояний si связано некоторое
вещественное значение ϕi (0 ⩽ i ⩽ n), называемое потенциалом. Тогда

Глава 1. Введение

можно определить значения

c′(ai) := c(ai) + ϕi − ϕi−1
для всех i = 1, . . . , n,

которые мы будем называть приведенными (или учетными) стоимостями. Идея состоит в том, что подходящим выбором потенциалов
иногда удается добиться того, что максимальное возможное значение
приведенной стоимости операции (обозначим его C′) оказывается
намного меньше максимально возможного фактического значения.
Это позволяет оценить сумму (1.1) так:

n
i=1
c(ai) =

n
i=1
c′(ai) + ϕ0 − ϕn ⩽ C′n + (ϕ0 − ϕn).
(1.2)

Если дополнительно известно, что ϕn ⩾ ϕ0, то оценка упрощается до
C′n.

Применим введенную технику для анализа суммарной сложности
последовательности из n вставок в вектор. Фактическая стоимость
одной операции Insert зависит от того, происходит ли на данном
шаге перевыделение. Если нет, то время работы можно принять за
одну условную единицу. Если же перевыделение необходимо, то время
работы составляет m + 1 условных единиц, где m –– текущий размер
массива (m единиц уходят на копирование существующих значений,
а еще одна уходит на сохранение нового значения в перевыделенном
участке памяти).
Как видно, фактические времена выполнения операций сильно
разнятся. Чтобы выровнять их, введем потенциал следующим образом. Заметим, что если размер массива на каждом перевыделении
удваивается, то в любой момент времени, кроме начального (когда
вектор пуст), количество занятых элементов s в массиве не меньше
половины его длины l. Потенциал ϕ состояния структуры данных
примем равным 2s − l.
В случае добавления без перевыделения потенциал меняется на
O(1), значит, учетная стоимость операции также составляет O(1).
Более интересен случай добавления с перевыделением. Тогда l = s,
и операция Insert стоит s + 1 условных единиц. После перевыделения потенциал равен 2, а значит, увеличение потенциала равно

1.3. Задачи
11

2 − (2s − s) = 2 − s. Учетная стоимость операции Insert в итоге
составляет (s + 1) + (2 − s) = 3 единицы.
В обоих случаях получаем оценку O(1) на учетную стоимость
операции Insert. Кроме того, конечный потенциал не меньше начального. Следовательно, по формуле (1.2) общая сложность последовательности операций составляет O(n).

Упражнение 1.2.1. Покажите, что оценка O(n) на общее время выполнения n операций Insert остается справедливой и для любого другого
коэффициента перевыделения α > 1. Как зависит скрытая в оценке
O(n) константа от α?

1.3. Задачи

Задача 1. Правильной скобочной последовательностью называется
строка, состоящая только из скобок, в которой все скобки можно
разбить на пары таким образом, что
• в каждой паре есть левая и правая скобка, причем левая скобка
расположена левее правой;
• для любых двух пар скобок либо одна из них полностью находится
внутри другой пары, либо промежутки между скобками в парах
не пересекаются;
• в паре с круглой скобкой может быть только круглая скобка,
с квадратной –– квадратная, с фигурной –– фигурная.
Примеры:
• если разрешены только круглые скобки:
– правильные последовательности: (), (()), ()(), ()()(), (())(),
((()));
– неправильные последовательности: )(, )), ((, ())()(, ()),
))((;
• если разрешены круглые и квадратные скобки:
– правильные последовательности: [],(), [()], [[([])]()];
– неправильные последовательности: [), ([)], (())()[]][;
• если разрешены еще и фигурные скобки:
– правильные последовательности: [{(())}({})], []{}(), {},
(), [];
– неправильные последовательности: [{(})], [(]())]{}.