Главная Совершенный алгоритм. Основы

Совершенный алгоритм. Основы

0 / 0
Насколько вам понравилась эта книга?
Какого качества скаченный файл?
Скачайте книгу, чтобы оценить ее качество
Какого качества скаченные файлы?
Алгоритмы — это сердце и душа computer science. Без них не обойтись, они есть везде — от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения. «Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую IT-компанию.

В этой книге Тим Рафгарден — гуру алгоритмов — расскажет об асимптотическом анализе, нотации большое-О, алгоритмах «разделяй и властвуй», рандомизации, сортировки и отбора.

Книга «Совершенный алгоритм» адресована тем у кого уже есть опыт программирования. Вы перейдете на новый уровень, чтобы увидеть общую картину, разобраться в низкоуровневых концепциях и математических нюансах.

Познакомиться с дополнительными материалами и видеороликами автора (на английском языке) можно на сайте www.algorithmsilluminated.org
Год:
2019
Издание:
1
Издательство:
Питер
Язык:
russian
Страницы:
258
ISBN 13:
9785446109074
Серия:
Библиотека программиста
Файл:
PDF, 14,94 MB

Возможно Вас заинтересует Powered by Rec2Me

 

Ключевые слова

 
0 comments
 

Чтобы оставить отзыв, пожалуйста, войдите или зарегистрируйтесь
Вы можете оставить отзыв о книге и поделиться своим опытом. Другим читателям будет интересно узнать ваше мнение о прочитанных книгах. Независимо от того, пришлась ли вам книга по душе или нет, если вы честно и подробно расскажете об этом, люди смогут найти для себя новые книги, которые их заинтересуют.
1

Introducing Mind and Brain

Год:
2018
Язык:
english
Файл:
EPUB, 139,83 MB
0 / 0
2

Minha mãe fazia: Crônicas e receitas saborosas e cheias de afeto

Год:
2017
Язык:
portuguese
Файл:
EPUB, 3,19 MB
4.0 / 0
С^ППТЕР

Algorithms Illuminated
Part 1: The Basics
Tim Roughgarden

ТИМ
РАФГАРДЕН

СОВЕРШЕННЫЙ
АЛГОРИТМ
ОСНОВЫ

COMPUTER

SCIENCE

^ППТЕР'
Санкт-Петербург • Москва • Екатеринбург•Воронеж
Нижний Новгород • Ростов-на-Дону
Самара • Минск

2019

ББК 32.973.2-018
УДК 004.42
Р26

Р26

Рафгарден Тим
Совершенный алгоритм. Основы. — СПб.: Питер, 2019. — 256 с.: ил. —
(Серия «Библиотека программиста»).
ISBN 978-5-4461-0907-4
Алгоритмы — это сердце и душа computer science. Без них не обойтись, они есть везде —
от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения.
«Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи
и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую
IT-компанию. В этой книге Тим Рафгарден — гуру алгоритмов — расскажет об асимпто­
тическом анализе, нотации большое-О, алгоритмах «разделяй и властвуй», рандомизации,
сортировки и отбора. Книга «Совершенный алгоритм» адресована тем, у кого уже есть опыт
программирования. Вы перейдете на новый уровень, чтобы увидеть общую картину, разо­
браться в низкоуровневых концепциях и математических нюансах.
Познакомиться с дополнительными материалами и видеороликами автора (на английском
языке) можно на сайте www.algorithmsilluminated.org.

16+ (В соответствии с Федеральным законом от 29 декабря 2010 г. № 436-ФЗ.)
ББК 32.973.2-018
УДК 004.42
Права на издание получены по соглашению с Soundlikeyourself Publishing LLC. Все права защищены. Ни­
какая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного
разрешения владельцев авторских прав.
Информация, содержащаяся в данной книге, получена из источников, рассматриваемых издательством
как надежные. Тем не менее, имея в виду возможные человеческие или технические ошибки, изда­
тельство не может гарантировать абсолютную точность и полноту приводимых сведений и не несет
ответственности за возможные ошибки, связанные с использованием книги. Издательство не несет от­
ветственности за дост; упность материалов, ссылки на которые вы можете найти в этой книге. На момент
подготовки книги к изданию все ссылки на интернет-ресурсы были действующими

ISBN 978-0999282908 англ.
ISBN 978-5-4461-0907-4

© Tim Roughgarden
© Перевод на русский язык ООО Издательство «Питер», 2019
© Издание на русском языке, оформление ООО Издательство
«Питер», 2019
© Серия «Библиотека программиста», 2019

Краткое содержание

Предисловие................................................................................................................. 14
Глава 1. Введение......................................................................................................... 21
Глава 2. Асимптотические обозначения...................................................................63
Глава 3. Алгоритмы «разделяй ивластвуй»............................................................. 91

Глава 4- Основной метод........................................................................................... 129
Глава 5. Алгоритм Quicksort..................................................................................... 158

Глава 6. Линейный выбор......................................................................................... 203
Приложения................................................................................................................. 235

Оглавление

Предисловие............................................................................................................... 14
О чем эти книги......................................................................................................... 14

Навыки, которые вы приобретете..........................................................................16

В чем особенность этой книги............................................................................... 17
Для кого эта книга?.................................................................................................. 18

Дополнительные ресурсы........................................................................................19

Благодарности........................................................................................................... 20
Глава 1. Введение...................................................................................................... 21

1.1. Зачем изучать алгоритмы?.............................................................................. 22
1.2. Целочисленное умножение............................................................................. 24

1.2.1. Задачи и решения.................................................................................... 24

1.2.2. Задача целочисленногоумножения...................................................... 25
1.2.3. Алгоритм начальной школы.................................................................. 25
1.2.4. Анализ числа операций...........................................................................27
1.2.5. Можно ли добиться лучшего?............................................................... 27
1.3. Умножение Карацубы...................................................................................... 28

1.3.1. Конкретный пример................................................................................ 28
1.3.2. Рекурсивный алгоритм............................................................................ 30

1.3.3. Умножение Карацубы............................................................................. 32

1.4. Алгоритм MergeSort.......................................................................................... 36
1.4.1. Актуальность....... .................................................................................... 36
1.4.2. Сортировка............................................................................................... 37

1.4.3. Пример.......................................................................................................39
1.4.4. Псевдокод.................................................................................................. 40

1.4.5. Подпрограмма Merge.............................................................................. 41
1.5. Анализ алгоритма MergeSort........................................................................... 42
1.5.1. Время исполнения подпрограммы Merge............................................. 43
1.5.2. Время исполнения алгоритма MergeSort..............................................44

1.5.3. Доказательство теоремы 1.2................................................................. 46
1.5.4. Ответы на тестовые задания 1.1-1.2.................................................... 50

Ответ на тестовое задание 1.1.........................................................................50
Ответ на тестовое задание 1.2.........................................................................51
1.6. Основные принципы анализа алгоритмов.................................................... 51

1.6.1. Принцип № 1: анализ наихудшего случая.......................................... 52
1.6.2. Принцип № 2: анализ значимых деталей............................................53

1.6.3. Принцип № 3: асимптотический анализ.............................................. 55

1.6.4. Что такое «быстрый» алгоритм?........................................................... 58
Задачи на закрепление материала....................................................................... 60
Задача повышенной сложности............................................................................. 62

Задача по программированию............................................................................... 62
Глава 2. Асимптотические обозначения........................................................... 63
2.1. Отправная точка............................................................................................... 64

2.1.1. Актуальность............................................................................................ 64
2.1.2. Высокоуровневая идея............................................................................ 65

2.1.3. Четыре примера...................................................................................... 67
2.1.4. Решения тестовых заданий 2.1-2.4...................................................... 72

2.2. Обозначение О-большое.................................................................................. 74

2.2.1. Определение на русском языке............................................................. 74
2.2.2. Иллюстрированное определение......................................................... 74

2.2.3. Математическое определение............................................................... 75
2.3. Два простых примера...................................................................................... 77

2.3.1. Для многочленов степени кО-большое является О(л*)................... 77
2.3.2. Для многочленов степени kO-большим не является О (л*”1).......... 79

2.4. Обозначение Омега-большое и Тета-большое............................................ 80

2.4.1. Обозначение Омега-большое................................................................ 80
2.4.2. Обозначение Тета-большое.................................................................. 81

2.4.3. Обозначение о-малое.............................................................................83
2.4.4. Откуда взялось обозначение?............................................................... 84
2.4.5. Решение тестового задания 2.5.............................................................84
2.5. Дополнительные примеры.............................................................................. 85

2.5.1. Добавление константы к экспоненте................................................... 85

2.5.2. Умножение экспоненты на константу.................................................. 86
2.5.3. Максимум против суммы........................................................................ 87

Задачи на закрепление материала....................................................................... 89

Глава 3. Алгоритмы «разделяй и властвуй».................................................. 91
3.1. Парадигма «разделяй и властвуй»................................................................ 92
3.2. Подсчет инверсий за время О(л log л)......................................................... 93

3.2.1. Задача....................................................................................................... 93

3.2.2. Пример...................................................................................................... 93
3.2.3. Совместная фильтрация........................................................................ 94

3.2.4. Поиск полным перебором...................................................................... 95
3.2.5. Подход «разделяй и властвуй»............................................................ 96
3.2.6. Высокоуровневый алгоритм.................................................................. 96
3.2.7. Ключевая идея: задействовать алгоритм MergeSort......................... 97

3.2.8. К вопросу о подпрограмме Merge......................................................... 99
3.2.9. Подпрограмма Merge и разделенные инверсии............................... 100

3.2.10. Подпрограмма Merge-CountSplitlnv...................................................102
3.2.11. Корректность........................................................................................103
3.2.12. Время исполнения............................................................................... 103
3.2.13. Решения тестовых заданий 3.1 - 3.2............................................... 104
3.3. Умножения матриц по алгоритму Штрассена............................................ 104

3.3.1. Умножение матриц............................................................................... 105
3.3.2. Пример (л = 2)........................................................................................105
3.3.3. Простой алгоритм.................................................................................. 106

3.3.4. Подход «разделяй и властвуй»........................................................... 107
3.3.5. Экономия времени на рекурсивном вызове...................................... 109
3.3.6. Детали...................................................................................................... 111

3.3.7. Решение тестового задания 3.3........................................................... 112

*3.4. Алгоритм со временем О (n log л) для ближайшей пары....................... 112
3.4.1. Задача...................................................................................................... 113
3.4.2. Разминка: одномерный случай............................................................ 113
3.4.3. Предварительная обработка................................................................114

3.4.4. Подход «разделяй и властвуй»........................................................... 116
3.4.5. Тонкая настройка.................................................................................. 118

3.4.6. Подпрограмма ClosestSplitPair............................................................. 119
3.4.7. Правильность.......................................................................................... 121
3.4.8. Доказательство леммы 3.3 (а)............................................................. 122

3.4.9. Доказательство леммы 3.3 (Ь)............................................................. 123
3.4.10. Решение тестового задания 3.4.........................................................125

Задача на закрепление материала.......................................................................126
Задачи повышенной сложности........................................................................... 127
Задачи по программированию............................................................................. 128
Глава 4. Основной метод.......................................................................................129

4.1. К вопросу о целочисленном умножении..................................................... 130
4.1.1. Алгоритм RecIntMult...............................................................................130

4.1.2. Алгоритм Karatsuba................................................................................ 131
4.1.3. Сравнение рекуррентных соотношений............................................. 132

4.2. Формулировка................................................................................................. 133
4.2.1 Стандартные рекуррентные соотношения..........................................133

4.2.2. Формулировка и обсуждение основного метода.............................. 135
4.3. Шесть примеров..............................................................................................137
4.3.1. К вопросу об алгоритме MergeSort..................................................... 137
4.3.2. Двоичный поиск..................................................................................... 138

4.3.3. Рекурсивное целочисленное умножение........................................... 139
4.3.4. Умножение Карацубы............................................................................ 139

4.3.5. Умножение матриц............................................................................... 140
4.3.6. Фиктивное рекуррентное соотношение............................................. 141

4.3.7. Решения тестовых заданий 4.2-4.3.................................................... 142
*4.4. Доказательство основного метода............................................................. 143

4.4.1. Преамбула...............................................................................................144
4.4.2. К вопросу о деревьях рекурсии........................................................... 145
4.4.3. Работа, выполняемая на одном уровне............................................. 146
4.4.4. Суммирование уровней.........................................................................147
4.4.5. Добро против зла: потребность в трех случаях............................... 148
4.4.6. Предсказание границ времени работы.............................................. 149
4.4.7. Заключительные расчеты: случай 1................................................... 151

4.4.8. Отклонение: геометрический ряд...................................................... 151
4.4.9. Заключительные вычисления: случаи 2 и 3...................................... 152
4.4.10. Решения тестовых заданий 4.4-4.5................................................. 153
Задачи на закрепление материала..................................................................... 156
Задача повышенной сложности........................................................................... 157
Глава 5. Алгоритм Quicksort............................................................................... 158

5.1. Обзор................................................................................................................ 159
5.1.1. Сортировка............................................................................................. 159
5.1.2. Разделение вокруг опорного элемента.............................................. 160
5.1.3. Высокоуровневое описание.................................................................. 162

5.1.4. Забегая вперед.......................................................................................163
5.2. Разделение массива вокруг опорного элемента....................................... 164

5.2.1. Легкий выход из положения............................................................... 164
5.2.2. Реализация на том же месте: высокоуровневый план................... 165

5.2.3. Пример.................................................................................................... 166
5.2.4. Псевдокод Partition................................................................................. 169
5.2.5. Псевдокод алгоритма Quicksort........................................................... 171

5.3. Важность хороших опорных элементов...................................................... 171
5.3.1. Наивная реализация подпрограммы ChoosePivot............................. 172

5.3.2. Избыточная реализация ChoosePivot.................................................. 173
5.3.3. Решения тестовых заданий 5.1- 5.2................................................... 174
5.4. Рандомизированный алгоритм Quicksort..................................................... 176

5.4.1. Рандомизированная реализация подпрограммы ChoosePivot........ 176
5.4.2. Время работы рандомизированного алгоритма Quicksort............... 177
5.4.3. Интуитивное понимание: чем хороши случайные опорные
элементы?.......................................................................................................... 178

*5.5. Анализ рандомизированного Quicksort..................................................... 180
5.5.1. Предварительные сведения................................................................. 181
5.5.2. Схема декомпозиции............................................................................. 183
5.5.3. Применение схемы................................................................................. 185
5.5.4. Вычисление вероятностей сравнения.................................................187
5.5.5. Заключительные вычисления.............................................................. 190
5.5.6. Решение тестового задания 5.3........................................................... 192

*5.6. Сортировка требует Q(n log л) сравнений............................................... 192

5.6.1. Алгоритмы сортировки на основе сравнения.................................... 193
5.6.2. Более быстрая сортировка при более строгих допущениях......... 194

5.6.3. Доказательство теоремы 5.5................................................................196
Задачи на закрепление материала..................................................................... 199

Задача повышенной сложности........................................................................... 201
Задачи по программированию............................................................................. 201

Глава 6. Линейный выбор.................................................................................... 203
6.1. Алгоритм RSelect..............................................................................................204

6.1.1. Задача выбора........................................................................................ 204

6:1.2. Сведение к задаче сортировки............................................................ 206
6.1.3. Подход «разделяй и властвуй»........................................................... 207
6.1.4. Псевдокод для алгоритма RSelect...................................................... 208
6.1.5. Время работы алгоритма RSelect........................................................ 209
6.1.6. Решение тестовых заданий 6.1-6.2.................................................... 212

Решение тестового задания 6.1..................................................................... 212

Решение тестового задания 6.2..................................................................... 212

*6.2. Анализ алгоритма RSelect...........................................................................213
6.2.1. Отслеживание прогресса посредством фаз...................................... 213
6.2.2. Сведение к задаче подбрасывания монеты...................................... 215

6.2.3. Соединяем все вместе...........................................................................217
*6.3. Алгоритм DSelect........................................................................................... 218
6.3.1. Гениальная идея: медиана медиан..................................................... 219
6.3.2. Псевдокод для алгоритма DSelect...................................................... 220

6.3.3. Понимание алгоритма DSelect............................................................. 221

6.3.4. Время работы алгоритма DSelect........................................................ 222
*6.4. Анализ алгоритма DSelect........................................................................... 224

6.4.1. Работа вне рекурсивных вызовов....................................................... 224
6.4.2. Грубое рекуррентное соотношение....................................................225

6.4.3. Лемма 30-70........................................................................................... 226
6.4.4. Решение рекуррентного соотношения............................................... 228
6.4.5. Метод догадок и проверок...................................................................230

Задачи на закрепление материала..................................................................... 233
Задачи повышенной сложности........................................................................... 234
Задачи по программированию............................................................................. 234
Приложения.......................................

235

Приложение А. Краткий обзор доказательств по индукции........................... 236
А.1. Шаблон для доказательств по индукции.............................................. 236

А.2. Пример: замкнутая формула...................................................................237
А.З. Пример: размер полного двоичного дерева........................................ 238

Приложение Б. Краткий обзор дискретной вероятности................................ 239

Б.1. Выборочные пространства...................................................................... 240
Б.2. События..................................................................................................... 241
Б.З. Случайные величины............................................................................... 243
Б.4. Математическое ожидание..................................................................... 244
Б.5. Линейность математического ожидания.............................................. 247

Б.6. Пример: распределение нагрузки......................................................... 250

Посвящается Эмме

Предисловие

Перед вами первая из четырех частей книги, основанной на проводимых
мною с 2012 года онлайн-курсах по алгоритмам. Эти курсы, в свою очередь,
появились благодаря лекциям для студентов, которые я читал в Стэнфордском
университете в течение многих лет.

О чем эти книги
Первая часть книги «Совершенный алгоритм» закладывает основы понима­
ния следующих четырех тем.

Асимптотический анализ и математическое обозначение О-болыпое.
Система обозначений, используемая в математическом анализе асимптот,
обеспечивает терминологическую базу для обсуждения процессов разработки
и анализа алгоритмов. Ключевым понятием здесь является математическое
обозначение О-большое, которое представляет собой вариант моделирования
гранулярности, используемой для оценки времени исполнения алгоритма.
Мы увидим, что «золотой серединой» для четкого и высокоуровневого по­
нимания механизмов разработки алгоритмов является подход, основанный на
игнорировании постоянных коэффициентов и членов более низкого порядка,
а также концентрация на том, каким образом производительность алгоритма
соотносится с размером входных данных.
Алгоритмы «разделяй и властвуй» и Основной метод. При разработке
алгоритмов нет какой-либо «серебряной пули», отсутствует универсальный
способ, который позволял бы запросто решать все вычислительные за­
дачи. Вместе с тем существует несколько общих методов проектирования
алгоритмов, которые находят успешное применение в различных областях.

О чем эти книги

15

В этой части книги мы рассмотрим методику «разделяй и властвуй». Ее идея
заключается в разбиении задачи на ряд мелких подзадач, которые решаются
рекурсивно. Затем полученные решения быстро объединяются в решение
исходной задачи. Мы рассмотрим быстрые алгоритмы типа «разделяй и вла­
ствуй» для решения задач сортировки, умножения целых чисел и умножения
матриц, а также для решения основной задачи вычислительной геометрии. Мы
также рассмотрим Основной метод (или основную теорему о рекуррентных
соотношениях), который является мощным инструментом анализа времени
исполнения алгоритмов типа «разделяй и властвуй».
Рандомизированные алгоритмы. Рандомизированный алгоритм в ходе
своего выполнения использует прием «подбрасывания монеты», и его пове­
дение может зависеть от результатов этих подбрасываний. Удивительно часто
рандомизация приводит к простым, изящным и практичным алгоритмам.
Каноническим примером является рандомизированный алгоритм быстрой
сортировки Quicksort. Мы детально рассмотрим как сам этот алгоритм, так
и анализ продолжительности его исполнения. Дальнейшие примеры приме­
нения рандомизации будут рассматриваться во второй части книги.

Сортировка и отбор. В качестве побочного продукта изучения первых трех
тем мы узнаем несколько знаменитых алгоритмов сортировки и отбора,
включая сортировку слиянием MergeSort, быструю сортировку Quicksort
и линейный отбор (как рандомизированный, так и детерминированный). Эти
вычислительные примитивы настолько невероятно быстры, что они не зани­
мают намного больше времени, чем требуется для чтения входных данных.
Важно наращивать коллекцию таких «бесплатных примитивов» как для не­
посредственного применения к данным, так и для использования в качестве
строительных блоков для решения более сложных задач.
Для более подробного изучения материала книги внимательно знакомьтесь
с разделами «Выводы», которые завершают каждую главу и выделяют наи­
более важные вопросы.

Темы, которые рассматриваются в других трех частях. Во второй части
книги рассматриваются различные структуры данных (кучи, сбалансиро­
ванные деревья поиска, хеш-таблицы, фильтры Блума), графовые прими­
тивы (поиск в ширину и в глубину, связность, кратчайшие пути) и области
их применения (от дедупликации до анализа социальных сетей). Третья

16

Предисловие

часть посвящена жадным алгоритмам (задачи планирования, определение
минимального остовного дерева графа, кластеризация, коды Хаффмана),
а также динамическому программированию («задача о рюкзаке», задачи
выравнивания рядов, поиска кратчайших путей, построения деревьев
оптимального поиска). Четвертая часть посвящена раскрытию класса
NP-полных задач, их сложности для разработчиков алгоритмов, искусству
решения алгоритмически неразрешимых задач, включая эвристический
анализ и локальный поиск.

Навыки, которые вы приобретете
Освоение алгоритмов требует времени и усилий. Ради чего все это?

Возможность стать более эффективным программистом. Вы изучите не­
сколько невероятно быстрых подпрограмм для обработки данных и несколько
полезных структур для организации данных, которые можете применять не­
посредственно в ваших собственных программах. Реализация и применение
этих алгоритмов расширит и улучшит ваши навыки программирования. Вы
также узнаете основные приемы разработки алгоритмов, которые актуальны
для решения разнообразных задач в широких областях, получите инструменты
для прогнозирования производительности этих алгоритмов. Такие «шаблоны»
могут быть вам полезны для разработки новых алгоритмов решения задач,
которые возникают в вашей собственной работе.
Развитие аналитических способностей. Алгоритмические описания, мысли­
тельная работа над алгоритмами дают большой опыт. Посредством математи­
ческого анализа вы получите углубленное понимание конкретных алгоритмов
и структур данных, описанных в этой книге. Вы приобретете навыки работы
с несколькими математическими методами, которые широко применяются
для анализа алгоритмов.

Алгоритмическое мышление. Научившись разбираться в алгоритмах,
трудно не заметить, что они окружают вас повсюду: едете ли вы в лифте,
наблюдаете ли за стаей птиц, управляете ли вы своим инвестиционным
портфелем или даже наблюдаете за тем, как учится ребенок. Алгоритмиче­
ское мышление становится все более полезным и распространенным в дис-

В чем особенность этой книги

17

циплинах, не связанных с информатикой, включая биологию, статистику
и экономику.
Знакомство с величайшими достижениями информатики. Изучение
алгоритмов напоминает просмотр эффектного клипа с многочисленными
суперхитами минувших шестидесяти лет развития информатики. Вы больше
не будете чувствовать себя отстраненным на фуршете для специалистов
в области информатики, когда кто-то отпустит шутку по поводу алгоритма
Дейкстры. Прочитав эти книги, вы будете точно знать, что он имеет в виду.

Успешность в собеседованиях. На протяжении многих лет студенты раз­
влекали меня рассказами о том, как знания, почерпнутые из этих книг, по­
зволяли им успешно справляться с любым техническим вопросом, который
им задавали во время собеседования.

В чем особенность этой книги
Эта книга предназначена только для одного: постараться научить основам
алгоритмизации максимально доступным способом. Воспринимайте ее как
конспект лекций, которые опытный наставник по алгоритмам будет давать
вам на протяжении серии индивидуальных уроков.
Существует ряд прекрасных, гораздо более традиционных и энциклопедиче­
ски выверенных учебников по алгоритмам. Любой из них с пользой украсит
эту серию книг дополнительными деталями, задачами и темами. Хотелось
бы, чтобы вы поискали и нашли что-то избранное среди этих книг для себя.
Кроме того, есть книги, которые ориентируются на программистов, ищущих
готовые реализации алгоритмов на конкретном языке программирования.
Множество соответствующих примеров также находятся в свободном до­
ступе в интернете.

18

Предисловие

Для кого эта книга?
Весь смысл этой книги, как и онлайн-курсов, на основе которых она созда­
на, — быть широко и легко доступной настолько, насколько это возможно.
На моих онлайн-курсах широко представлены люди всех возрастов, профес­
сионального опыта и слоев общества, есть немало учащихся и студентов,
разработчиков программного обеспечения (как состоявшихся, так и начина­
ющих), ученых и профессионалов со всех уголков мира.

Эта книга не является введением в программирование, и было бы просто
идеально, если бы вы уже обладали основными навыками программирования
на каком-либо распространенном языке (например, Java, Python, С, Scala,
Haskell). Чтобы пройти «лакмусовый» тест, обратитесь к разделу 1.4 — если
там все понятно, значит, в остальной части книги у вас все будет в порядке.
Если вам требуется развить свои навыки программирования, то для этих
целей есть несколько прекрасных бесплатных онлайн-курсов, обучающих
основам программирования.
По мере необходимости мы также используем математический анализ, чтобы
разобраться в том, как и почему алгоритмы действительно работают. Свободно
доступные конспекты лекций «Математика для Computer Science» под автор­
ством Эрика Лемана и Тома Лейтона являются превосходным и освежающим
память пособием по системе математических обозначений (например, £ и V),
основам теории доказательств (метод индукции, доказательство от против­
ного и др.), дискретному распределению вероятностей и многому другому1.
Краткие обзоры метода индукции и дискретного распределения вероятностей
изложены в приложениях А и Б соответственно. Наиболее математически на­
груженные разделы помечены звездочками. Если у вас «страх математики»
или вы ограничены во времени, можно пропустить их при первом чтении без

потери непрерывности в изложении материала.

1 См. Mathematics for Computer Science, Eric Lehman, Tom Leighton: http://www.
boazbarak.org/csl21/LehmanLeighton.pdf

Дополнительные ресурсы

19

Дополнительные ресурсы
Эта книга основана на онлайн-курсах, которые в настоящее время запущены
в рамках проектов Coursera и Stanford Lagunita. Имеется также ряд ресурсов
в помощь вам для повторения и закрепления опыта, который можно извлечь
из онлайн-курсов.
Видео. Если вы больше настроены смотреть и слушать, чем читать, обратитесь
к материалам с «Ютуба», доступным на сайте www.algorithmsilluminated.org. Эти
видео затрагивают все темы этой серии книг. Надеюсь, что они пропитаны
тем же заразительным энтузиазмом в отношении алгоритмов, который, увы,
невозможно полностью воспроизвести на печатной странице.
Тестовые задания. Как узнать, что вы действительно усваиваете понятия,
представленные в этой книге? Тестовые задания с решениями и объяснениями
разбросаны по всему тексту; когда вы сталкиваетесь с одним из них, призываю
вас остановиться и подумать об ответе, прежде чем читать далее.

Задачи в конце главы. В конце каждой главы вы найдете несколько от­
носительно простых вопросов для проверки усвоения материала, а затем
более трудные и менее ограниченные по времени сложные задачи. Решения
этих задач в книгу не включены, но для этого читатели могут обратиться ко
мне или взаимодействовать между собой через дискуссионный форум книги
(см. ниже).
Задачи по программированию. В конце большинства глав предлагается
реализовать программный проект, целью которого является закрепление
детального понимания алгоритма путем создания его рабочей реализации.
Наборы данных, а также тестовые примеры и их решения можно найти на
www.algorithmsilluminated.org.

Дискуссионные форумы. Существенной причиной успеха онлайн-курсов
являются реализованные через дискуссионные форумы возможности общения
для слушателей. Это позволяет им помогать друг другу в лучшем усвоении
материала курса, а также отлаживать свои программы. Читатели этих книг
имеют такую же возможность благодаря форумам, доступным на сайте www.
algorithmsilluminated.org.

20

Предисловие

Благодарности
Эта книга не появилась бы без того энтузиазма и интеллектуального голода,
которые демонстрируют тысячи слушателей моих курсов по алгоритмам на
протяжении многих лет как на кампусе в Стэнфорде, так и на онлайн-платформах. Я особенно благодарен тем, кто предоставлял подробные отзывы
на более ранний проект этой книги, среди них: Тоня Бласт, Юань Цао, Джим
Хьюмелсайн, Байрам Кулиев, Патрик Монкелбэн, Кайл Шиллер, Ниссэнка
Викермэзинг и Дэниел Зингаро.
Конечно же, всегда приятно получать замечания и предложения от читателей,
которые наилучшим образом доходят через упомянутые выше дискуссионные
форумы.

Стэнфордский университет
Тим Рафгарден
Стэнфорд, Калифорния
Сентябрь 2017

Введение

22

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

Цель этой главы — зародить в вас интерес к изучению алгоритмов. Начав
с рассмотрения алгоритмов в целом, мы постараемся выяснить, почему они
так важны. Затем мы воспользуемся задачей умножения двух целых чисел,
чтобы проиллюстрировать, как алгоритмическая изобретательность может
улучшить более простые или, казалось бы, очевидные на первый взгляд
решения. Далее мы подробно рассмотрим алгоритм сортировки слиянием
MergeSort, что важно по нескольким причинам. Во-первых, это широко при­
меняемый на практике и знаменитый алгоритм, который необходимо знать.
Во-вторых, его обзор станет неплохой разминкой при подготовке к изу­
чению более изощренных алгоритмов. И наконец, этот алгоритм является
классическим введением в методологию проектирования алгоритмов типа
«разделяй и властвуй». Главу завершает описание ряда руководящих прин­
ципов нашего подхода к анализу алгоритмов, которые будут применяться
в оставшейся части книги.

1.1. Зачем изучать алгоритмы?
Позвольте мне сначала обосновать актуальность этой книги, указав несколько
причин, почему так важно быть мотивированным в изучении алгоритмов. Так
что же такое алгоритм, в конце концов? Это набор четко сформулированных
правил, в сущности, рецепт для решения некоторой вычислительной задачи.
Может быть, у вас имеется куча чисел и вы хотите перераспределить их так,
чтобы расположить их в отсортированном порядке. Возможно, у вас есть
дорожная карта и необходимо вычислить кратчайший путь от некоторой
исходной точки до определенного места назначения. Вполне вероятно, вам
требуется выполнить несколько задач до наступления установленных сроков,
в таком случае вы заинтересованы в упорядочении выполнения этих задач,
для того чтобы вовремя все их завершить.

Итак, зачем же изучать алгоритмы?

Важность для всех отраслей computer science. Во-первых, понимание основ
алгоритмизации и тесно с ней взаимосвязанной сферы организации структур
данных необходимо для выполнения серьезной работы практически в любой
отрасли информатики. Например, в Стэнфордском университете для полу-

1.1. Зачем изучать алгоритмы?

23

чения любой степени по Computer Science (будь то бакалавр, магистр наук
и даже доктор наук) обязательно требуется пройти курс алгоритмов. Приведу
всего несколько примеров:
1. Протоколы маршрутизации в коммуникационных сетях задействуют
классические алгоритмы поиска кратчайшего пути.

2. Криптография с открытым ключом опирается на эффективные теоре­
тико-числовые алгоритмы.
3. Компьютерная графика требует вычислительных примитивов, предо­
ставляемых геометрическими алгоритмами.
4. Индексация в базах данных опирается на структуры данных сбаланси­
рованных деревьев поиска.
5. Вычислительная биология использует алгоритмы динамического про­
граммирования для измерения сходства геномов.

Приведенный список можно продолжать.
Двигатель технологических инноваций. Во-вторых, алгоритмы играют
ключевую роль в современных технологических инновациях. Приведу толь­
ко один очевидный пример: поисковые системы используют целую мозаику
алгоритмов для эффективного вычисления релевантности различных веб­
страниц заданному поисковому запросу. Наиболее известным подобным
алгоритмом является алгоритм PageRank, используемый в настоящее время
Google. В самом деле, в докладе за декабрь 2010 года для Белого дома
США президентский консультативный совет на науке и технике написал
следующее:

«Все знают Закон Мура — предсказание, сделанное в 1965 г. соучре­
дителем Intel Гордоном Муром о том, что плотность транзисторов
в интегральных схемах будет удваиваться каждые 1—2 года... Во многих
областях прирост производительности за счет улучшения алгоритмов
значительно превысил даже впечатляющий рост производительности
за счет увеличения скорости процессоров»'.
Выдержка из доклада президенту и конгрессу: Проектирование цифрового буду
щего, декабрь 2010 г. (с. 71).

24

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

Новый взгляд на достижения других наук. В-третьих (хотя это выходит
за рамки этой книги), алгоритмы все более и более используются в качестве
«увеличительного стекла», чтобы по-новому взглянуть на научные проблемы
за пределами computer science и IT. Например, исследование квантовых вы­
числений обеспечило новый вычислительный взгляд на квантовую механику.
Ценовые колебания на экономических рынках могут плодотворно рассматри­
ваться как алгоритмический процесс. Даже эволюцию можно рассматривать
как удивительно эффективный алгоритм поиска.

Гимнастика для мозга. Во времена студенчества моими любимыми всегда
были сложные предметы. После их освоения всегда оставалось ощущение,
что я становился на несколько пунктов 1Q умнее, чем в начале изучения. На­
деюсь, моя книга позволит вам получить аналогичный опыт.
Удовольствие! Я надеюсь, что к концу этой книги вы поймете, почему разра­
ботка и анализ алгоритмов просто приносит удовольствие! Это увлекательное
занятие, которое требует редкого сочетания точности и креативности. Раз­
умеется, временами эта работа может разочаровывать, но она также очень
затягивает. И давайте не будем забывать о том, что обучение алгоритмам, по
сути, сопровождает вас с самого детства.

1.2. Целочисленное умножение
1.2.1. Задачи и решения
Когда вы учились в начальной школе, вы, скорее всего, изучали умножение
двух чисел в столбик, что, по сути, является алгоритмом — четко сформули­
рованным набором правил для преобразования входа (два числа) в выход (их
произведение). Всегда важно понимать разницу между постановкой (описа­
нием) решаемой задачи и описанием метода ее решения (то есть алгоритма
этой задачи). В этой книге мы будем систематически придерживаться схемы,
в которой сначала производится постановка вычислительной задачи (данные
на входе и требуемый результат на выходе), а затем дается описание одного
или нескольких алгоритмов ее решения.

1.2. Целочисленное умножение

25

1.2.2. Задача целочисленного умножения
В задаче целочисленного умножения входными данными являются два
и-разрядных числа, обозначим их х и у. Разрядность (длина) п чисел х и у
может быть любым положительным целым числом. Однако я призываю вас
оперировать большими значениями и, в тысячах или более'. (Представьте,
что вы разрабатываете некое криптографическое приложение, ведь они ма­
нипулируют очень большими числами.) В задаче целочисленного умножения
требуемым выходом является результат произведениях *у.

ЗАДАЧА. ЦЕЛОЧИСЛЕННОЕ УМНОЖЕНИЕ
Вход: два л-значных неотрицательных целых числа, х и у.

Выход: произведение х х у.

1.2.3. Алгоритм начальной школы
Точно определив вычислительную задачу, мы опишем алгоритм, который
ее решает, — тот самый алгоритм, который вы изучали в начальной школе.
Мы оценим производительность этого алгоритма числом «примитивных
операций», которые он выполняет, в виде функции от количества знаков п
в каждом входном числе. Пока же давайте представим примитивную опе­
рацию как любую из следующих: (i) сложение двух одноразрядных (п = 1)
чисел; (ii) умножение двух одноразрядных чисел или (iii) добавление нуля
к началу или концу числа.

Чтобы освежить вашу память, рассмотрим конкретный пример умножения
х = 5678 на = 1234 (здесь п = 4) в столбик, см. рис. 1.1. Сначала алгоритм вы-

1 Если вы хотите перемножить числа с разными длинами (например, 1234 и 56), про­
сто добавьте несколько нулей в начало меньшего числа (например, рассматривайте
56 как 0056). С другой стороны, алгоритмы, которые мы обсудим, могут быть при­
способлены для чисел с разной длиной.

26

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

числяет «частичное произведение» первого числа и последней цифры второго
числа: 5678 * 4 = 22 712. Вычисление этого частичного произведения сводится
к умножению каждой цифры первого числа на 4, записи младшего разряда
результата, запоминанию («переносу» на следующий этап) старшего разряда
и добавлению этих «переносов» (если они есть) на следующем умножении1.
При вычислении следующего частичного произведения (5678 * 3 = 17 034)
мы делаем то же самое, сдвигая результат на один знак влево (фактически
добавляя «0» в конце). И так далее для оставшихся двух частичных произ­
ведений. Заключительный шаг состоит в том, чтобы сложить все частичные
произведения.
Тогда в третьем классе вы, вероятно, согласились, что этот алгоритм является
правильным, имея в виду, что неважно, с каких чисел х и у начинать. При
условии, что все промежуточные вычисления выполняются правильно, алго­
ритм в конечном итоге заканчивается получением результата произведения
х х у двух исходных чисел.

х

5678
1234

dUZO тч,
п строк

17034

11356
5678__________

< 2л операций
(«а строку)

7006652
Рис. 1.1. Алгоритм целочисленного умножения в столбик

Таким образом, вы никогда не получите неправильный ответ, и алгоритм не
может зациклиться.

1 8 х 4 = 32, 2 пишем, 3 «переносим», 7 х 4 = 28, плюс 3 равняется 31,1 пишем,
3 переносим, и так далее...

1.2. Целочисленное умножение

27

1.2.4. Анализ числа операций
Ваш школьный учитель, возможно, не обсуждал число примитивных опера­
ций, необходимых для завершения процедуры умножения в столбик. В на­
шем примере, для того чтобы вычислить первое частичное произведение,
мы умножили 4 раза каждую из цифр 5, 6, 7, 8 первого числа. Это четыре
примитивные операции. Мы также выполнили несколько сложений из-за пере­
носов. В общем случае вычисление частичного произведения влечет за собой
и умножений (одно умножение на один знак) и не более п сложений (не более
одного на один знак). Всего получается не более 2п примитивных операций.
Первое частичное произведение ничем не отличается от других, и каждое из
них требует не более 2п операций. Поскольку имеется п частичных произ­
ведений — по одному на каждый знак второго числа, — вычисление всех из
них требует не более п х 2п = 2п2 примитивных операций. Чтобы вычислить
окончательный ответ, нам все еще нужно все частичные произведения сложить
вместе, но для этого требуется сопоставимое число операций (не более чем
еще 2н2). Подведем итоги:
общее количество операций < константа х п\
-4

Рассуждая о том, каким образом объем работы, который этот алгоритм вы­
полняет, возрастает по мере того, как исходные множители становятся все
длиннее и длиннее, мы видим, что объем выполняемых операций растет
квадратически, следуя за увеличением разрядности. Если удвоить длину ис­
ходных множителей, то требуемый объем операций подскакивает в 4 раза.
Увеличьте их длину в 4 раза, и она подскочит в 16 раз, и так далее.

1.2.5. Можно ли добиться лучшего?
В зависимости от того, каким третьеклассником вы были, вы вполне могли
принять эту процедуру как уникальный или, по крайней мере, оптималь­
ный способ умножения двух чисел. Если вы захотите стать серьезным
проектировщиком алгоритмов, то нужно будет преодолеть эту робость.
Классическая книга по алгоритмам Ахо, Хопкрофта и Ульмана, после
итеративного рассмотрения целого ряда методик разработки алгоритмов,
говорит следующее:

28

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

«Для хорошего разработчика алгоритмов, пожалуй, самый важный прин­
цип состоит в том, чтобы отказаться от соглашательства»1.

Или как я люблю говорить, что каждый разработчик алгоритмов должен
принять как должное:

Можно ли добиться лучшего?
Этот вопрос особенно актуален, когда вы сталкиваетесь с очевидным или
прямым решением вычислительной задачи. В третьем классе вы, возможно,
не задавались вопросом о том, можно ли выстроить путь решения лучше, чем
это делает простой классический алгоритм умножения в столбик. Настало
время задать этот вопрос и дать на него ответ.

1.3. Умножение Карацубы
Разработка алгоритмов — удивительно разносторонняя сфера. Безусловно,
существуют другие интересные методы умножения двух целых чисел, помимо
того, что вы изучали в третьем классе. В этом разделе описывается один из
таких методов, под названием умножение Карацубы2.

1.3.1. Конкретный пример
Чтобы почувствовать, что такое умножение Карацубы, давайте снова восполь­
зуемся нашим предыдущим примером сх = 5678 иу= 1234. Мы выполним по­
следовательность шагов, совершенно отличающуюся от алгоритма начальной
школы (умножения в столбик), результатом которого является произведение х
х у. Этот новый алгоритм должен показаться вам очень загадочным, похожим
на фокус вынимания кролика из шляпы. Позже в этом разделе мы дадим точ­
ное объяснение того, что такое умножение Карацубы и почему оно работает.
1 См.: А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных
алгоритмов. М.: Мир, 1979 (Alfred V. Aho, John Е. Hopcroft, and Jeffrey D. Ullman,
The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, page 70).
2 Обнаружен в 1960 году Анатолием Карацубой, который в то время был 23-летним
студентом.

1.3. Умножение Карацубы

29

Сейчас главное — на этом примере оценить, что существует потрясающий
воображение массив различных вариантов решения вычислительных задач,
в частности целочисленного умножения.
Для начала обозначим первую и вторую половины числах как а и Ь, чтобы
рассматривать их отдельно. Для нашего примера получаем а = 56 и b = 78.
Аналогичным образом поступим с у, здесь пусть с и d соответственно обо­
значают первую и вторую половины числау, то есть с = 12 и d= 34 (рис. 1.2).

а

Рис. 1.2. Представление четырехзначных чисел как пар двузначных чисел

Затем мы выполним последовательность операций с участием только
двузначных чисел а, Ь, с и d и, наконец, волшебным образом соберем все
элементы вместе. Увидим, что в итоге это приведет нас к результату про­
изведения х и у.
Шаг 1: Вычислить произведение а х с = 56 х 12, которое составляет 672
(можете проверить сами).
Шаг 2: Вычислить b х d = 78 х 34 = 2652.

Следующие два шага еще более непостижимые.

Шаг 3: Вычислить (а + b) х (с + d) = 134 х 46 = 6164.
Шаг 4: Вычесть результаты первых двух шагов из результата третьего шага:
6164-672-2652 = 2840.
Наконец, мы суммируем результаты шагов 1, 2 и 4, но только после добав­
ления четырех конечных нулей к ответу на шаге 1 и двух конечных нулей
к ответу на шаге 4.

Шаг 5: Вычислить 672 * 104 + 2840 * 102 + 2652 = 6 720 000 + 284 000 + 2652 =
= 70 066 552.

30

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

Что мы видим? Это точно такой же (правильный) результат, который полу­
чился у нас при применении алгоритма умножения в столбик в разделе 1.2!

Я не требую от вас сразу интуитивно понять то, что только что произошло.
Скорее, я надеюсь, что вы ощущаете некое сочетание озадаченности и ин­
триги, и оценили тот факт, что, похоже, действительно существуют алго­
ритмы целочисленного умножения, принципиально отличающиеся от того,
с которым вы познакомились еще в школе. Как только вы поймете, насколько
сфера алгоритмизации разнообразна, вы начнете задумываться над вопросом:
может быть, существует что-то более интересное, чем алгоритм умножения
в столбик? Разве приведенный выше алгоритм не позволил вам продвинуться
в этом понимании?

1.3.2. Рекурсивный алгоритм
Прежде чем вплотную заняться умножением Карацубы, давайте немного
подробнее рассмотрим, в чем суть простого рекурсивного подхода к цело­
численному умножению1. Рекурсивный алгоритм целочисленного умножения,
очевидно, связан с умножением чисел с меньшим, чем у исходных, количе­
ством знаков (например, 12, 34, 56 и 78 в приведенном выше примере).

В общем случае число х с четным количеством знаков п может быть выражено
в виде двух и/2-значных чисел (его первой и второй половины, которые мы
обозначили как а и Ь)\
х = 10"/2 х а + 6.

Аналогично для числа у:
у = 10"/2 х с + d.

1 Я исхожу из того, что вы слышали о рекурсии в рамках вашего опыта программи­
рования. Рекурсивная процедура — это процедура, которая вызывает саму себя
как подпрограмму с меньшими по объему входными данными до тех пор, пока не
будет достигнут базовый случай.

1.3. Умножение Карацубы

31

Чтобы вычислить произведение х и у, воспользуемся двумя приведенными
выше представлениями чисел х и у и просто перемножим их. Получаем
х ху = (Юя/2 х a + b) х (ЧУ172 х c + d) =
= 10я х (а х с) + 10я/2 х (а х d+b х c) + b х d.

(1.1)

Обратите внимание на то, что все умножения в (1.1) либо происходят между
парами и/2-значных чисел, либо связаны с возведением в степень числа 104
Выражение (1.1) позволяет лучше понять рекурсивный подход к умножению
двух чисел. Чтобы получить произведение х х у9 мы производим расчет фор­
мулы (1.1). Во всех четырех присутствующих в ней произведениях (а х с,
a*d,b*cHb*d) задействуются числа с количеством знаков меньше и,
поэтому мы можем вычислить каждое из них рекурсивно. Как только наши
четыре рекурсивных вызова возвращаются к нам со своими результатами, мы
можем вычислить выражение (1.1) в явном виде. Приставляем п конечных
нулей к произведению а х с, суммируем произведения а х d и b х с (обычное
арифметическое сложение) и приставляем и/2 конечных нулей к этой сумме,
и, наконец, прибавляем эти два выражения к произведению b х <Р. Теперь
давайте обобщим этот алгоритм, который мы назовем ReclntMult, в следу­
ющем псевдокоде3.

1 Для простоты мы принимаем допущение, что п является степенью числа 2. Простой
прием, который позволяет использовать это допущение, — добавление соответ­
ствующего количества нулей к х и у, что не более чем удваивает разрядность этих
чидел. С другой стороны, когда п — нечетно, всегда можно также разбить х и у на
два числа с почти равными длинами.
2 Рекурсивные алгоритмы, естественно, нуждаются в одном или нескольких базовых
случаях для того, чтобы они не зацикливались до бесконечности. Здесь базовый
случай: если х и у являются однозначными числами, то необходимо просто пере­
множить их одной примитивной операцией и выдать результат, закончив алгоритм.
3 В псевдокоде мы используем символ = для обозначения проверки на эквивалент­
ность и символы := для обозначения присваивания переменной.

32

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

RECINTMULT
Вход: два и-значных положительных целых числа, х и у.

Выход: произведение х х у.
Допущение: п является степенью числа 2.
if n = 1 then

// базовый случай

вычислить х х у за один шаг и выдать результат
else
// рекурсивный случай
а, b := первая и вторая половины х

с, d := первая и вторая половины у
рекурсивно вычислить ас := а х с, ad:=a* d,

be :=b x си bd :=b x d

вычислить 10" x ас + IO"72 x (ad + be) + bd,
используя арифметическое сложение, и выдать результат.

Является ли алгоритм RecIntMult более быстрым, чем алгоритм умножения
в столбик? Конечно, можно обратиться к своей интуиции, но лучше все же
подождать до главы 4, там вы найдете точный ответ на этот вопрос.

1.3.3. Умножение Карацубы
Умножение Карацубы является оптимизированной версией алгоритма
RecIntMult. Мы снова начинаем с разложения, согласно формуле (l.l),
множителей произведения х х у на составляющие а, Ь, с и d. В алгоритме
RecIntMult используется четыре рекурсивных вызова, один для каждого про­
изведения в (1.1) между и/2-значными числами. Но нас совсем не интересуют
а х d или b х с по отдельности, нас интересует их сумма а * d + b х с. При
наличии всего трех промежуточных вычислений, в которых мы заинтересо­
ваны — а* с, a*d+b*cnb*d, — сможем ли мы обойтись всего тремя
рекурсивными вызовами?

1.3. Умножение Карацубы

33

Чтобы убедиться в этом, сначала, как и прежде, следует применить два ре­
курсивных вызова, чтобы вычислить а х с и b х d.
Шаг 1: Рекурсивно вычислить а х с.

Шаг 2: Рекурсивно вычислить b* d.

Вместо того чтобы рекурсивно вычислять a* d или b * с, мы рекурсивно
вычисляем произведение между а + b и с + dx.
Шаг 3: Вычислить а + b и с + d (обычное арифметическое сложение), и ре­
курсивно вычислить произведение (a -I- b) х (с + d).

Ключевой прием умножения Карацубы обязан математику XIX века Карлу
Фридриху Гауссу, который изучал умножение комплексных чисел. Вычитание
результатов первых двух шагов из результата третьего шага дает именно то,
что мы хотим: срединный коэффициент в (1.1) — выражение a* d + b *с:
(a + b)x(c + d) -axc-bxd = axd + Ьхс.
=a*c+a*d+b*c+b*d

Шаг 4: Вычесть результаты первых двух шагов из результата третьего шага,
чтобы получить а * d + b х с.

Заключительный шаг представляет собой формулу (1.1), как и в алгоритме
ReclntMult.
Шаг 5: Вычислить формулу (1.1), сложив результаты шагов 1, 2 и 4, после
добавления 10" конечных нулей к ответу на шаге 1 и 10"2 конечных нулей
к ответу на шаге 4.

1 Числа а + b и с + d могут иметь до (и/2) + 1 знаков, но алгоритм по-прежнему ра­
ботает отлично.

34

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

KARATSUBA

Вход: два и-значных положительных целых числа, х и у.

Выход: произведение х* у.
Допущение: п является степенью числа 2.
// базовый случай

if л = 1 then

вычислить х х у за один шаг и выдать результат
else

// рекурсивный случай

а, b := первая и вторая половины х

с, d := первая и вторая половины у
вычислить р := а + b и q := с + d, используя

арифметическое сложение,
рекурсивно вычислить ас := а х с, bd := b • d и
pq-p*q

вычислить adbc := pq-ac~ bd, используя

арифметическое сложение,

вычислить 10я х ас + IO"72 х adbc + bd, используя
арифметическое сложение, и выдать результат.

Таким образом, умножение Карацубы использует всего три рекурсивных вы­
зова! Экономия на одном рекурсивном вызове должна сэкономить на общем
времени исполнения, но насколько? Алгоритм Karatsuba быстрее школьного
алгоритма умножения в столбик? Ответ на этот вопрос далеко не очевиден.
Однако на его примере будет легко проиллюстрировать применение инстру­
ментов анализа времени исполнения алгоритмов типа «разделяй и властвуй»,
которые мы рассмотрим в главе 4.

1.3. Умножение Карацубы

35

О ПСЕВДОКОДЕ

В этой книге алгоритмы описываются с использованием комбинации
высокоуровневого псевдокода и обычного человеческого языка (как
в этом разделе).
Я исхожу из того, что у вас есть навыки трансляции таких высокоуровне­
вых (общих) описаний в рабочий код на вашем любимом языке програм­
мирования. Несколько других книг и ресурсов в интернете предлагают
конкретные реализации различных алгоритмов на определенных языках
программирования.
Во-первых, преимущество в предпочтении высокоуровневых описаний
над реализациями, специфичными для конкретного языка программиро­
вания, заключается в их гибкости: хотя я исхожу из вашей осведомлен­
ности в каком-то языке программирования, меня не интересует, что это
за язык. Во-вторых, этот подход способствует пониманию алгоритмов
на глубоком и концептуальном уровне, не обремененном деталями низ­
кого уровня. Опытные программисты и специалисты computer science
обычно мыслят и обмениваются информацией об алгоритмах на столь
же высоком уровне.

Тем не менее ничто не может заменить детального понимания алгорит­
ма, которое вытекает из разработки своей собственной рабочей про­
граммы. Настоятельно рекомендую вам реализовать на любимом языке
программирования столько алгоритмов из этой книги, насколько у вас
хватит времени. (Это также будет отличным поводом улучшить свои на­
выки программирования!)
Для развития своих навыков программирования воспользуйтесь задачами
по программированию в конце главы и соответствующими тестовыми
примерами.

36

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

1.4. Алгоритм MergeSort
Этот параграф дает возможность войти во вкус анализа времени исполнения
нетривиального алгоритма — известного алгоритма сортировки слиянием
MergeSort.

1.4.1. Актуальность
Алгоритм сортировки слиянием MergeSort — это достаточно старый
алгоритм, и, безусловно, он был известен Джону фон Нейману еще
в 1945 году. Зачем начинать современный курс об алгоритмах с такого
старого примера?
Старое, но по-прежнему нужное. Несмотря на то что алгоритму MergeSort
уже более 70 лет, он по-прежнему является одним из предпочтительных мето­
дов сортировки. Он широко используется на практике и является стандартным
алгоритмом сортировки в ряде программных библиотек.

Это классический алгоритм типа «разделяй и властвуй». Методология
разработки алгоритмов «разделяй и властвуй» представляет собой общий
подход к решению задач, который находит приложение в различных обла­
стях. Ее основная идея состоит в том, чтобы разбить вашу задачу на более
мелкие подзадачи, решить подзадачи рекурсивно и, наконец, объединить
решения в итоговое решение исходной задачи. Алгоритм MergeSort является
идеальным способом познакомиться с методологией «разделяй и властвуй»,
с учетом тех преимуществ, которые он предлагает, и возникающих при его
анализе сложностей.
Возможность улучшить техническую подготовку. Предстоящее изучение
алгоритма MergeSort позволит вам составить ясное представление о том,
насколько хорошо имеющиеся у вас навыки соответствуют материалу этой
книги. Я исхожу из того, что у вас есть достаточный опыт в программирова­
нии и математическом анализе, чтобы (с некоторой доработкой) перевести
высокоуровневое описание алгоритма MergeSort в рабочую программу на
вашем любимом языке программирования и оценить наш анализ времени
исполнения алгоритма. Если этот и следующий разделы будут вам понятны,
то у вас отличные шансы для понимания остальной части книги.

1.4. Алгоритм MergeSort

37

Введение в руководящие принципы анализа алгоритмов. Наш анализ
времени исполнения алгоритма MergeSort раскрывает ряд более общих ру­
ководящих принципов. Таких, как поиск ограничений на время исполнения
алгоритма, которые актуальны для любых входных данных заданного размера,
а также важность оценки темпов роста времени исполнения алгоритма в за­
висимости от объема входных данных.

Разминка для основного метода. Мы проанализируем алгоритм MergeSort
с использованием «метода дерева рекурсии», который представляет собой
способ подсчета операций, выполняемых рекурсивным алгоритмом. Глава 4
опирается на эти идеи и завершается «основным методом», мощным и про­
стым в использовании инструментом для вычисления границ времени ис­
полнения разнообразных алгоритмов типа «разделяй и властвуй», включая
алгоритмы RecIntMult и Karatsuba из раздела 1.3.

1.4.2. Сортировка
Вы, вероятно, уже знакомы с задачей сортировки и некоторыми алгорит­
мами для ее решения. Но все же, чтобы убедиться, что мы в одной лодке,
рассмотрим:

ЗАДАЧА: СОРТИРОВКА

Вход: массив из п чисел в произвольном порядке.
Выход: массив тех же самых чисел, отсортированных от наи­
меньшего до наибольшего.

Например, при наличии входного массива

5

4

I

8

7

2

6

3

7

8

Требуемый выходной массив будет следующим:
1

2

3

4

5

6

38

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

В приведенном выше примере все восемь чисел во входном массиве различны.
Сортировка на самом деле не будет как-то сложнее, когда есть дубликаты, она
вполне может быть проще. Но для того чтобы обсуждение было максимально
простым, давайте договоримся — по-дружески — о том, что числа во входном
массиве всегда различны. Я настоятельно рекомендую вам подумать о том,
как наши алгоритмы сортировки должны быть изменены (если это вообще
потребуется), чтобы справляться с дубликатами1.
Если вы не заботитесь об оптимизации времени исполнения, то не очень-то
сложно найти правильный алгоритм сортировки. Возможно, самый простой
способ — сначала просканировать входной массив, чтобы определить мини­
мальный элемент и скопировать его в первый элемент выходного массива;
затем просканировать оставшиеся элементы массива, чтобы идентифициро­
вать и скопировать второй наименьший элемент, и так далее. Этот алгоритм
называется сортировкой выбором Selectionsort. Вы, возможно, слышали
о сортировке вставками Insertionsort, которая может рассматриваться
в качестве более продуманной реализации той же самой идеи итеративного
наращивания префикса отсортированного выходного массива. Вероятно, вы
также знаете пузырьковую сортировку Bubblesort, в которой вы выявляете
пары соседних элементов, которые еще не упорядочены, и выполняете
многократные обмены до тех пор, пока весь массив не будет отсортирован.
Все эти алгоритмы имеют квадратичное время исполнения. Это означает,
что число операций, выполняемых на массивах длиной и, является функцией
от и2, квадрата длины входных данных. Можно ли добиться лучшего? При
помощи методики «разделяй и властвуй» алгоритм сортировки слиянием
MergeSort значительно улучшает более простые алгоритмы сортировки2.

1 На практике очень часто обрабатываемые данные (именуемые значением) связаны
с неким числом (которое именуется ключом). Например, вы можете отсортировать
записи о персонале (с именем, окладом и так далее), использовав номера социаль­
ного страхования в качестве ключей. Мы фокусируемся на сортировке ключей,
понимая, однако, что за каждым ключом закреплены соответствующие данные.
2 Несмотря на то что сортировка слиянием MergeSort доминирует, сортировка встав­
ками Insertionsort частенько по-прежнему широко применяется на практике,
в особенности когда размеры входных данных небольшие.

1.4. Алгоритм MergeSort

39

1.4.3. Пример
Наиболее простой способ понять алгоритм MergeSort — это взглянуть на
рисунок конкретного примера (рис. 1.3). Мы будем использовать входной
массив из параграфа 1.4.2.

<------------

рекурсивные
вызовы

-------------- >

Рис. 1.3. Вид с высоты птичьего полета на сортировку слиянием MergeSort
на конкретном примере

В качестве рекурсивного алгоритма «разделяй и властвуй» алгоритм MergeSort
оперирует более мелкими массивами. Самый простой способ разложить
задачу сортировки на более мелкие — разбить входной массив пополам.
Первая и вторая половины сортируются рекурсивно. Например, на рис. 1.3
первой и второй половинами входного массива являются {5, 4 ,1 ,8} и {7,
2, 6, 3}. Благодаря волшебству рекурсии (или индукции, если хотите), пер­
вый рекурсивный вызов правильно сортирует первую половину, возвращая
массив {1, 4, 5, 8}. Второй рекурсивный вызов возвращает массив {2, 3, 6,
7}. Заключительный шаг «слияния» объединяет эти два отсортированных
массива длиной 4 в один-единственный отсортированный массив из всех

40

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

8 чисел. Подробности этого шага приведены ниже, но идея состоит в том,
чтобы пройтись по индексам каждого отсортированного подмассива сверху
вниз, заполнив выходной массив слева направо в отсортированном порядке.

1.4.4. Псевдокод
Рисунок 1.3 может быть преобразован в следующий ниже псевдокод с двумя
рекурсивными вызовами и шагом слияния для решения исходной задачи.
Как обычно, наше описание высокоуровневое и не обязательно может быть
переведено построчно в рабочий программный код (хотя оно достаточно

близко к реализации).

MERGESORT

Вход: массив А из п разных целых чисел.
Выход: массив с теми же самыми целыми числами, отсортиро­
ванными от наименьшего до наибольшего.
// базовые случаи проигнорированы

С := рекурсивно отсортировать первую половину А
D := рекурсивно отсортировать вторую половину А

вернуть Merge (С, £>)

В псевдокоде пропущено несколько деталей, которые заслуживают коммен­
тария. Рекурсивный алгоритм как таковой должен иметь один или несколько
базовых случаев, когда больше нет дальнейшей рекурсии и результат возвра­
щается напрямую. Поэтому, если входной массив А содержит только 0 или
1 элемент, алгоритм MergeSort возвращает его же (он уже отсортирован). Наш
псевдокод не детализирует, как определяются «первая половина» и «вторая
половина», когда п нечетно, но очевидная интерпретация (когда одна «поло­
вина» имеет на один элемент больше другой) работает нормально. Наконец,
псевдокод игнорирует детали реализации в отношении того, как на самом
деле передавать два подмассива в соответствующие им рекурсивные вызовы.
Эти детали в некоторой степени зависят от языка программирования. Суть

1.4. Алгоритм MergeSort

41

высокоуровневого псевдокода состоит в том, чтобы игнорировать такие детали
и сосредоточиваться на общих понятиях, которые выходят за рамки любого
конкретного языка программирования.

1.4.5. Подпрограмма Merge
Что представляет собой шаг слияния Merge? Он применяется после того, как
два рекурсивных вызова сделали свою работу и у нас имеется два отсорти­
рованных подмассива, С и D, длиной п/2. Идея состоит в том, чтобы пройти
оба отсортированных подмассива по порядку и заполнить выходной массив
слева направо также в отсортированном порядке'.

MERGE
Вход: отсортированные массивы С и D (длиной п!2 каждый).

Выход: отсортированный массив В (длиной п).
Упрощающее допущение: п — четное.
1 г : == 1
2 j : == 1
3 for k := 1 to n do
4
5
6
7
8
9

if C[i] < D[y] then
B[fc] := C[i]
i := г + 1
else
B[fc] := D[j]
J := J + 1

// заполнить выходной массив
// прирастить г
// D[J1 < С[г

Мы сканируем выходной массив, используя индекс к, и отсортированные под­
массивы с индексами i и у. Все три массива проходятся слева направо. Цикл
for в строке 3 реализует проход по выходному массиву. В первой итерации
подпрограмма определяет минимальный элемент в С либо в D и копирует его
1 Мы нумеруем элементы массива, начиная с 1 (а не с 0), и используем синтаксиче­
скую конструкцию «ЛИ» для /-го элемента массива А. В разных языках програм­
мирования эти детали различаются.

42

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

в первую позицию выходного массива В. Минимальный элемент находится
либо в С (в этом случае это С [ 1 ], поскольку С отсортирован), либо в D (в этом
случае это D [ 1 ], поскольку D отсортирован). Приращение соответствующего
индекса (z или у), по сути, исключает только что скопированный элемент из
дальнейшего рассмотрения, и затем процесс повторяется, чтобы определить
наименьший элемент, остающийся в С или D (второй наименьший в двух
подмассивах). В общем случае, наименьший элемент, еще не скопирован­
ный в В. находится либо в С [/], либо в £>[/]; подпрограмма явным образом
проверяет, какой из них меньше, и действует соответствующим образом.
Поскольку каждая итерация копирует наименьший элемент, который все еще
рассматривается в С или £>, выходной массив действительно заполняется
в отсортированном порядке.
Как обычно, наш псевдокод преднамеренно слегка неаккуратен, чтобы подчер­
кнуть, что нас интересует лес, а не деревья. Рабочая программа, естественно,
должна отслеживать, когда прохождение С или D выходит за переделы (в про­
цессе приращения индексов i и у), и тогда в этой точке остающиеся элементы
другого массива копируются в окончательные элементы В (по порядку). Так
что для вас сейчас самое время разработать свою собственную программную
реализацию алгоритма MergeSort.

1.5. Анализ алгоритма MergeSort
Каково время исполнения алгоритма сортировки слиянием MergeSort (как
функции длины п входного массива)? Работает ли он быстрее, чем более
простые методы сортировки, такие как сортировка выбором Selectionsort,
сортировка вставками Insertionsort и пузырьковая сортировка Bubblesort?
Под «временем исполнения» мы понимаем количество строк кода, испол­
няемых в конкретной реализации алгоритма. Проанализируйте построчно
свою реализацию, использовав отладчик, по одной «примитивной операции»
за один раз. Нас интересует количество шагов, которые отладчику придется
сделать до завершения программы.

1.5. Анализ алгоритма MergeSort

43

1.5.1. Время исполнения подпрограммы Merge
Анализ времени исполнения алгоритма MergeSort представляет собой за­
дачу, которая на первый взгляд имеет устрашающий вид, поскольку перед
нами рекурсивный алгоритм, который неоднократно вызывает сам себя.
Поэтому давайте разомнемся на более простой задаче понимания числа
операций, выполняемых в результате одного вызова подпрограммы Merge
с двумя отсортированными массивами длиной €/2 каждый. Мы можем
сделать это напрямую, проанализировав код из раздела 1.4.5 (где / соответ­
ствует и). Первые строки 1 и 2 выполняют инициализацию, и мы зачтем их
как две операции. Затем у нас есть цикл for, который исполняется в общей
сложности I раз. Каждая итерация цикла выполняет сравнение в строке
4, присваивание в строке 5 либо в строке 8 и приращение в строке 6 или
в строке 9. Индекс к цикла тоже должен увеличиваться при каждой итера­
ции цикла. Это означает, что для каждой из / итераций цикла выполняются
4 примитивных операции1. Резюмируя, мы приходим к заключению, что
для того, чтобы объединить два отсортированных массива длиной /72 каж­
дый, подпрограмма Merge выполняет не более 4/ + 2 операций. В качестве
упрощения позвольте мне дополнительно злоупотребить нашей дружбой
слегка небрежным, но на самом деле верным допущением, использовав не­
равенство, которое сделает наши жизни проще: для / > 1,4/ + 2 < 6/. Таким
образом, 6/ также является допустимой верхней границей числа операций,
выполняемых подпрограммой Merge.

Лемма 1.1 (время исполнения подпрограммы Merge). Для каждой пары
отсортированных входных массивов С, D длиной 1/2 подпрограмма Merge
выполняет не более 6/ операций.

1 Можно придраться к тому, что мы насчитали 4 операции в цикле. Засчитывается ли
сравнение индекса цикла к с его верхней границей как дополнительная операция
в каждой итерации, что приводит в общей сложности к пяти операциям? В раз­
деле 1.6 объясняется, почему такие различия в ведении подсчета на самом деле
не имеют значения. Поэтому давайте договоримся — по-дружески, — что у нас
4 примитивных операции на итерацию.

44

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

О ЛЕММАХ, ТЕОРЕМАХ И ПРОЧЕМ

В математической практике самые важные технические утверждения
имеют статус теорем. Лемма — это техническое утверждение, которое
помогает с доказательством теоремы (во многом как подпрограмма
Merge помогает с реализацией алгоритма MergeSort). Следствие — это
высказывание, которое непосредственно вытекает из уже доказанного
результата, например частного случая теоремы. Термин утверждение мы
используем для автономных технических высказываний, которые сами по
себе не имеют особого значения.

1.5.2. Время исполнения алгоритма MergeSort
Как перейти от простого анализа подпрограммы Merge к анализу всего рекур­
сивного алгоритма MergeSort, который порождает дальнейшие вызовы самого
себя? В особенности пугает быстрое нарастание рекурсивных вызовов, коли­
чество которых буквально взрывается экспоненциально, вместе с глубиной
рекурсии. Единственное, что нас успокаивает, — это тот факт, что каждому
рекурсивному вызову передаются входные данные, значительно меньшие
по объему, чем те, с которых мы начали. Здесь играет роль противоборство
двух конкурирующих сил: с одной стороны, экспоненциальный рост количе­
ства разных подзадач, которые необходимо решать; и с другой — постоянно
уменьшающиеся исходные данные, за которые отвечают эти подзадачи. То, что
эти две силы друг друга балансируют, стимулирует наши усилия по анализу
алгоритма MergeSort. В итоге мы докажем нижеследующую полезную теоре­
му о конкретном максимуме количества операций, выполняемых алгоритмом
MergeSort (в целом, во всех своих рекурсивных вызовах).

Теорема 1.2 (предел времени исполнения алгоритма MergeSort). Для каж­
дого входного массива длиной п > 1 алгоритм MergeSort выполняет не более

6п log2 п + 6п

операций, где log2 обозначает логарифм по основанию 2.

1.5. Анализ алгоритма MergeSort

45

О ЛОГАРИФМАХ
Некоторых очень пугает вид логарифма, который на самом деле явля­
ется очень приземленным понятием. Для положительного целого л,
log2 л попросту означает следующее. Наберите л на калькуляторе и под­
считайте количество раз, которое вам потребуется, чтобы осуществить
последовательное деление на 2, прежде чем результат будет равняться
1 или меньше3. Например, для того, чтобы довести 32 до 1, требуется
пять делений на два, поэтому log2 32 = 5. Десять делений на два сводят
1024 к 1, поэтому log21024 = 10. Эти примеры делают интуитивно понят­
ным, что log2 л гораздо меньше л (сравните 10 с 1024). В особенности это
актуально, когда л становится большим. График (рис. 1.4) подтверждает
эту интуитивную догадку.

3Для особо щепетильных сообщаем, что log2 л не является целым числом,
если л не является степенью 2, и то, что мы описали, в действительности
является округлением log2 л до ближайшего целого числа. Это незначи­
тельное различие мы можем проигнорировать.

Теорема 1.2 ставит алгоритм MergeSort в выигрышное положение и демон­
стрирует преимущества методологии проектирования алгоритмов «разделяй
и властвуй». Мы ранее отмечали, что время исполнения более простых ал­
горитмов сортировки, например, сортировки выбором Selectionsort, со­
ртировки вставками Insertionsort и пузырьковой сортировки BubbleSort,
квадратично зависит от размерности п входных данных, а это означает, что
число операций, требуемых для исполнения этих алгоритмов, является функ­
цией, описываемой как константа, помноженная нал2. Для MergeSort, соглас­
но теореме 1.2, один из этих множителей п заменяется на гораздо меньший
log2 п. Рисунок 1.4 показывает, что, благодаря свойствам логарифма, алгоритм
MergeSort, как правило, работает намного быстрее, чем более простые алго­
ритмы сортировки. Особенно это справедливо, когда п становится большим1.

1 См. раздел 1.6.3 для дальнейшего пояснения этого вопроса.

46

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

Рис. 1.4. Функция логарифма растет намного медленнее, чем исходная
функция. Здесь показан логарифм с основанием 2; другие основания
приводят к качественно похожим изображениям

1.5.3. Доказательство теоремы 1.2
Теперь мы сделаем полный анализ времени исполнения алгоритма MergeSort
и в результате обоснуем утверждение о том, что рекурсивный подход «раз­
деляй и властвуй» позволяет получать более быстрый алгоритм сортировки,
нежели прямые методы. Для простоты мы примем допущение, что длина п
входного массива является степенью числа 2. Впрочем, это допущение может
и не использоваться после незначительной доработки.
План доказательства утверждения о пределе времени исполнения алгоритма
MergeSort в теореме 1.2 состоит в том, чтобы использовать дерево рекурсии,
или дерево рекурсивных вызовов; см. рис. 1.51. Идея метода дерева рекурсии
Судя по всему, по какой-то причине специалисты по computer science считают, что
деревья растут вниз.

1.5. Анализ алгоритма MergeSort

47

заключается в том, чтобы изобразить весь объем операций, выполняемых
рекурсивным алгоритмом, в виде древовидной структуры, в которой узлы
дерева соответствуют рекурсивным вызовам, а дочерние элементы узла
соответствуют рекурсивным вызовам, выполняемым этим узлом. Эта древо­
видная структура предоставляет нам принципиальный способ подсчитать все
операции, иными словами, всю работу, проделанную алгоритмом MergeSort
во всех его рекурсивных вызовах.

рооооооооооооооо,
узлы (одноэлементные массивы)

Рис. 1.5. Дерево рекурсии для алгоритма MergeSort. Узлы соответствуют
рекурсивным вызовам. Уровень 0 соответствует самому первому вызову
MergeSort, уровень 1 — следующим рекурсивным вызовам, и так далее

Корень дерева рекурсии соответствует самому первому вызову MergeSort,
где входными данными является исходный массив. Мы назовем его уровнем
О дерева. Поскольку каждая активация алгоритма MergeSort порождает два
рекурсивных вызова, дерево будет двоичным (то есть с двумя дочерними
элементами на узел). Уровень 1 дерева имеет два узла, которые соответству­
ют этим двум рекурсивным вызовам, сделанным самым первым вызовом,
один для левой половины входного массива и один для правой половины.
Каждый рекурсивный вызов уровня 1 сам будет делать два рекурсивных
вызова, и каждый из них будет оперировать с конкретной четвертью перво-

48

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

начального входного массива. Этот процесс продолжается до тех пор, пока
в конечном итоге рекурсия не закончится массивами размером 0 или 1
(базовые случаи).

ТЕСТОВОЕ ЗАДАНИЕ 1.1

Сколько приблизительно уровней имеет это дерево рекурсии,
как функция длины п входного массива?
а) постоянное число (независимо от и).

б) log2Zl.
в) 4п.

г) п.

(Ответ и анализ решения см. в разделе 1.5.4.)

Использование дерева рекурсии наводит на мысль о чрезвычайно удобном
способе учета операций, выполняемых алгоритмом MergeSort, а именно
спускаясь вниз уровень за уровнем. Чтобы реализовать эту идею, нам нужно
понять две вещи: количество разных подзадач на заданном уровне рекурсии j
и длину входных данных для каждой из этих подзадач.

ТЕСТОВОЕ ЗАДАНИЕ 1.2

Выявите закономерность: заполните пропуски в следующем вы­
сказывании: на каждом уровне 7 = 0, 1,2, ... дерева рекурсии
имеется [пропуск] подзадач, каждая из которых оперирует с под­
массивом длиной [пропуск].
а) 2J и 2J соответственно.

б) n/2J и n/2J соответственно.

в) 2J и п/21 соответственно.
г) n!2J и 27 соответственно.
(Ответ и анализ решения см. в разделе 1.5.4.)

1.5. Анализ алгоритма MergeSort

49

Теперь давайте применим полученную закономерность на практике и подсчи­
таем все операции, которые выполняет алгоритм MergeSort. Мы проходим от
уровня к уровню, поэтому давайте зафиксируему-й уровень дерева рекурсии.
Сколько операций выполняется нау-м уровне рекурсии, не считая операций,
выполняемых последующими рекурсивными итерациями, вызываемыми
с этого уровня? Просматривая код алгоритма MergeSort, мы видим, что он
делает только три вещи: выполняет два рекурсивных вызова и вызывает
подпрограмму Merge на объединение результатов. Таким образом, если, как
условились, игнорировать операции, выполняемые более поздними рекурсив­
ными вызовами, делаем вывод о том, что работа, выполняемая подзадачей на
уровне у, — это просто работа, выполняемая подпрограммой Merge.

Это и так уже было понятно из леммы 1.1: не более 6€ операций, где I — это
длина входного массива для этой подзадачи.
Сводя все воедино, мы можем выразить общий объем операций, выполняемых
рекурсивными вызовами на уровнеу (не учитывая более поздние рекурсивные
вызовы), как

Количество подзадач уровня у х работа в расчете на подзадачу уровня у

Решение тестового задания 1.2 (см. ниже) показывает, что первый член
равняется 2', и длина входных данных в каждую такую подзадачу равняется
л/27. Принимая f - n/2J, согласно лемме 1.1, получаем, что каждая подзадача
уровня у выполняет не более 6и/27 операций. Таким образом, во всех рекур­
сивных вызовах нау-м уровне рекурсии выполняется не более

6п
2j х -—= 6п
2J
операций.

Поразительно, но наша верхняя граница объема выполняемых операций ал­
горитма на заданном уровне у не зависит оту! То есть каждый уровень дерева
рекурсии производит одинаковое число операций. Это обусловлено идеаль­
ным равновесием между двумя конкурирующими силами — количество
подзадач удваивается с каждым уровнем, в то время как объем вычислений,
выполняемый в расчете на подзадачу, с каждым уровнем сокращается вдвое.

50

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

Нас интересует полное число операций, выполняемых на всех уровнях дерева
рекурсии алгоритма MergeSort. Решение тестового задания 1.1 (см. ниже) по­
казывает, что в дереве рекурсии имеется log2 п + 1 уровней (уровни от 0 до
log2 п включительно). Используя найденную нами границу, составляющую
6п операций на уровень, получаем, что общее число операций на весь алго­
ритм, составляет
количество уровней х работа в расчете на уровень < 6п log2 п + 6л.
'-------------------- V-------------------- '
- log2H+l

'---------------------------- V---------------------------- '

Полученное значение соответствует утверждению теоремы 1.2. Ч. т. д.[

О ПРИМИТИВНЫХ ОПЕРАЦИЯХ
Мы измеряем время исполнения алгоритмов, в частности MergeSort,
в терминах количества выполняемых «примитивных операций». Интуитив­
но понятно, что примитивная операция предназначена для выполнения
простой задачи (например, сложение, сравнение или копирование), за­
трагивая небольшое количество простых переменных (например, 32-разрядные целые числа)2. Но имейте в виду: в некоторых высокоуровневых
языках программирования одна строка кода может скрывать большое чис­
ло примитивных операций. Например, строка кода, которая затрагивает
каждый элемент длинного массива, транслируется в число примитивных
операций, пропорциональное длине массива.

1.5.4. Ответы на тестовые задания 1.1 -1.2
Ответ на тестовое задание 1.1
Правильный ответ: (б). Правильный ответ: ~ log2«. Это объясняется тем,
что размер входных данных уменьшается в два раза при переходе на каждый
последующий уровень рекурсии. Если длина входных данных на уровне О
равна и, то рекурсивные вызовы на уровне 1 оперируют с массивами длиной
1 «Ч. т. д.» — это аббревиатура выражения «что и требовалось доказать» от латин­
ского quod erat demonstrandum (Q.E.D.). В математике оно употребляется в конце
доказательства, чтобы отметить его завершение.
2 Могут иметься более точные определения, но нам они не нужны.

1.6. Основные принципы анализа алгоритмов

51

и/2, рекурсивные вызовы на уровне 2 — с массивами длиной и/4, и так далее.
Рекурсия отсутствует в базовых случаях, с входными массивами длиной не
больше единицы, где нет нужды в рекурсивных вызовах. В иных случаях
сколько требуется уровней рекурсии? Количество уровней равняется коли­
честву делений п на 2, чтобы получить число не более 1. Для п как степени 2
это как раз и есть определение логарифма log2«. (В более общем случае оно
равняется log2«, округленному до ближайшего целого числа.)

Ответ на тестовое задание 1.2
Правильный ответ: (в). Правильный ответ заключается в том, что на
уровне j рекурсии имеется 27 разные подзадачи, и каждая из них оперирует
с подмассивом длиной n/2J. Для начала начните с уровня 0, где имеется один
рекурсивный вызов. На уровне 1 имеется два рекурсивных вызова, и в более
общем плане (поскольку алгоритм MergeSort вызывает себя дважды) количе­
ство рекурсивных вызовов на каждом уровне вдвое превышает их количество
на предыдущем уровне. Это последовательное удвоение подразумевает, что
на каждом уровне j дерева рекурсии имеется 27 подзадачи. Аналогичным
образом, поскольку каждый рекурсивный вызов получает только половину
входных данных предыдущего, после j уровней рекурсии, длина входных
данных падает до n/2J. Ну и наконец, поскольку мы уже знаем, что на уровне
j имеется 2j подзадачи и первоначальный входной массив (длиной п) разделен
между ними поровну, — получается ровно n/2J элементов на подзадачу.

1.6. Основные принципы анализа
алгоритмов
Мы уже приобрели первый опыт анализа алгоритма на примере MergeSort
(см. теорему 1.2). Теперь самое время сделать шаг назад и дать исчерпыва­
ющее объяснение трех допущений, которые принимались нами при анализе
времени исполнения алгоритма и интерпретации результатов. Мы будем
использовать эти три допущения в качестве основных руководящих принци­
пов, которые объясняют, как рассуждать об алгоритмах, и применим их для
определения того, что же на самом деле подразумевается нами под термином
«быстрый алгоритм».

52

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

Цель этих принципов состоит в том, чтобы определить «золотую середину»
подхода к анализу алгоритмов, который уравновешивает точность с не­
противоречивостью. Точная оценка времени исполнения возможна только
для самых простейших алгоритмов; в более общем случае всегда требуются
компромиссы. С другой стороны, мы не хотим выплескивать ребенка вместе
с водой. Мы хотим, чтобы наши математические выкладки по-прежнему
имели предсказательную силу на практике, в отношении того, будет ли алго­
ритм быстрым или медленным. После того как мы нащупаем оптимальный
баланс, нам удастся обосновать полезные оценки пределов времени испол­
нения десятков фундаментальных алгоритмов, и эти оценки дадут возмож­
ность увидеть точную картину того, какие алгоритмы, как правило, работают
быстрее других.

1.6.1. Принцип № 1: анализ наихудшего случая
Формула предела времени исполнения алгоритма MergeSort, 6п log2 п + би,
доказанная в теореме 1.2, верна для каждого входного массива длиной и,
независимо от того, что он содержит. Мы не принимали никаких допущений
о природе входных данных, за исключением рамок их длины и. Гипотетиче­
ски, даже если бы существовал злоумышленник, единственная цель жизни
которого состояла бы в том, чтобы что-либо натворить с входными данными,
с целью заставить алгоритм MergeSort выполняться максимально медленно,
то предел времени исполнения этого алгоритма, 6л log2 п + 6л, по-прежнему
оставался бы верным и ни при каких условиях не мог бы быть превышен.
Этот тип анализа называется анализом наихудшего случая, поскольку он дает
ограничение времени исполнения, которое действительно даже для «худших»
входных данных.

С учетом того, как легко принцип анализа наихудшего случая следует из вы­
полненного нами анализа алгоритма MergeSort, вполне резонно задать вопрос,
что еще мы можем сделать. Один из альтернативных подходов — «анализ
среднего случая», который анализирует среднее время исполнения алгоритма
при определенном допущении об относительных частотах различных вход­
ных данных. Например, в задаче сортировки мы можем допустить, что все
входные массивы равновероятны, и затем изучать среднее время исполнения
различных алгоритмов сортировки. Вторая альтернатива — рассматривать
производительность алгоритма только на небольшой коллекции «эталонных

1.6. Основные принципы анализа алгоритмов

53

экземпляров», которые считаются репрезентативными для «типичных» или
«реальных» входных данных.
Как анализ среднего случая, так и анализ эталонных экземпляров могут быть
полезны, когда у вас есть предметные знания о вашей задаче и некоторое
понимание того, какие входные данные репрезентативнее других. Анализ
наихудшего случая, который отличается тем, что вы не делаете абсолютно
никаких допущений о входных данных, в особенности подходит для универ­
сальных подпрограмм, предназначенных для работы в различных областях
применения. Чтобы быть полезными как можно большему количеству людей,
в этой книге основное внимание уделяется таким подпрограммам общего
назначения, и, соответственно, используется принцип анализа наихудшего
случая, чтобы судить о производительности алгоритма.
Дополнительным преимуществом является то, что анализ наихудшего случая
обычно намного более формализован математически, нежели его альтер­
нативы. Это одна из причин, почему принцип анализа наихудшего случая
естественным образом очевиден из выполненного нами анализа алгоритма
MergeSort, несмотря на то что у нас априори не было ориентации на наи­
худшие входные данные.

1.6.2. Принцип № 2: анализ значимых деталей
Второй и третий руководящие принципы тесно взаимосвязаны. Назовем второй
из них анализом значимых деталей (предупреждение: это не общепринятый
термин). Этот принцип констатирует, что мы не должны излишне беспокоиться
о малых коэффициентах или членах низших порядков при вычислении преде­
лов времени исполнения алгоритмов. Мы уже встречались с этим концептуаль­
ным подходом на практике в нашем анализе алгоритма MergeSort: анализируя
время исполнения подпрограммы Merge (лемма 1.1). Мы сначала обосновали
верхний предел числа операций как 4/ + 2 (где { — это длина выходного
массива), а затем перешли к более простой формуле верхнего предела как 6€,
несмотря на то что ее недостатком является более крупный коэффициент. Что
позволяет нам так легко играть с коэффициентами?
Математическая простота. Первым преимуществом анализа значимых
деталей является его большая математическая простота, чем альтернатива

54

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

с использованием более точных коэффициентов или членов низших поряд­
ков. Этот момент был уже очевиден, когда использовался нами при анализе
времени исполнения алгоритма MergeSort.

Постоянные коэффициенты зависят от реализации. Второе обоснова­
ние менее очевидно, но чрезвычайно важно. На том уровне гранулярности,
который мы будем использовать для описания алгоритмов, как и в случае
с алгоритмом MergeSort, было бы совершенно неправильно зацикливаться
на том, что собой представляют постоянные коэффициенты. Например, во
время нашего анализа подпрограммы Merge ранее уже присутствовала двус­
мысленность относительно того, сколько именно «примитивных операций»
выполняется на каждой итерации цикла (4,5 или что-то другое?). Отсюда по­
нятно, что разные программные интерпретации одного и того же псевдокода
могут привести к разным постоянным коэффициентам. Двусмысленность
только увеличивается, как только псевдокод транслируется в конкретную
реализацию на любом высокоуровневом языке программирования, и затем
далее транслируется в машинный код — постоянные коэффициенты будут
неизбежно меняться в зависимости от используемого языка программирова­
ния, конкретной реализации и деталей компилятора и процессора. Поскольку
наша цель состоит в том, чтобы сосредоточиться на свойствах алгоритмов,
которые выходят за рамки особенностей языка программирования и машин­
ной архитектуры, то очевидно, что эти свойства должны быть независимы
от небольших изменений постоянного коэффициента при расчете времени
исполнения алгоритма.
Мы не рискуем потерять в точности прогноза о результате. Третье оправ­
дание — мы получаем возможность избежать неприятностей. Возможно, вы
будете обеспокоены тем, что игнорирование точности постоянных коэффици­
ентов собьет нас с правильного пути, обманом заставив думать, что алгоритм
является быстрым, тогда как на практике он на самом деле работает медленно,
или наоборот. К счастью, этого не произойдет для алгоритмов, обсуждаемых
в этих книгах1. Даже при том, что мы не будем отслеживать члены низших
порядков и зацикливаться на значениях постоянных коэффициентов, каче­
ственные предсказания нашего математического анализа будут очень точны.

1 С одним возможным исключением: детерминированный линейный алгоритм вы
бора, см. в факультативном разделе 6.3.

1.6. Основные принципы анализа алгоритмов

55

Когда анализ приводит к выводу, что алгоритм является быстрым, он на самом
деле будет быстрым на практике, и наоборот. Таким образом, в то время как
анализ значимых деталей действительно пренебрегает некоторыми деталями,
он дает нам то, в чем мы действительно заинтересованы: в точной оценке
того, какие алгоритмы демонстрируют тенденцию работать быстрее других1.

1.6.3. Принцип № 3: асимптотический анализ
Наш третий и заключительный руководящий принцип состоит в использова­
нии асимптотического анализа и акценте на темпе роста времени исполнения
алгоритма по мере того, как размер п входных данных становится большим.
Это смещение в сторону больших входных данных было уже очевидным,
когда мы оценивали предел времени исполнения алгоритма MergeSort (теоре­
ма 1.2), бп log2 п + бп операций. Мы тогда довольно самоуверенно объявили,
что алгоритм MergeSort «лучше», чем более простые методы сортировки
с квадратичным временем исполнения по отношению к размеру входных
данных, как, например, сортировка вставками Insertionsort. Но так ли это

на самом деле?
Рассмотрим конкретный пример. Пусть имеется алгоритм сортировки, кото­

рый выполняет не более -п2 операций, сортируя массив длиной п. Сравним
время исполнения этого алгоритма с таковым известного нам алгоритма
MergeSort, проанализировав
6nlog2 и + би в сопоставлении с ±п2.

Глядя на поведение этих двух функций на рис. 1.6, а, мы видим, что значение
- п2 меньше своего визави при малом п (не более 90 или около того), в то время

как значение бп log2 п + бп меньше для более крупного п. Поэтому, когда мы
говорим, что алгоритм MergeSort быстрее, чем более простые методы сорти1 Однако по-прежнему полезно иметь общее представление о релевантных постоян­
ных множителях. Например, в сильно доработанных версиях алгоритма MergeSort,
которые вы найдете во многих библиотеках программирования, этот алгоритм
переключается с MergeSort на сортировку вставками Insertionsort (из-за его луч­
шего постоянного коэффициента), как только длина входного массива становится
небольшой (например, не более семи элементов).

12000

Рис. 1.6. По мере того как п становится большим, функция ~п растет
намного быстрее, чем 6л log2 л+бл. Шкалы оси X и оси У в (б), соответственно
на один и два порядка больше, чем на (а)

1.6. Основные принципы анализа алгоритмов

57

ровки, мы в действительности имеем в виду, что он быстрее при достаточно
больших значениях размера массива входных данных.
Почему нас больше должны интересовать случаи с большими массивами
входных данных? Потому что алгоритмической изобретательности на самом
деле требуют только крупные задачи. При современном быстродействии ком­
пьютеров почти любой метод сортировки, о котором можно подумать, будет
моментально сортировать массив длиной 1000 — нет никакой необходимости
изучать алгоритмы «разделяй и властвуй».

С учетом того, что компьютеры постоянно становятся быстрее, вам, воз­
можно, любопытно, не станет ли решение всех вычислительных задач
в конечном итоге тривиальным. На самом деле, чем быстрее становятся
компьютеры, тем актуальнее становится асимптотический анализ. Наши
вычислительные амбиции всегда росли вместе с нашей вычислительной
мощью, поэтому с течением времени мы будем рассматривать задачи со
все более крупными размерами входных данных. И пропасть в произво­
дительности между алгоритмами с различным асимптотическим временем
работы будет становиться только шире по мере увеличения размеров вход­
ных данных. Например, рис. 1.6, б показывает разницу между функциями

6п log2 и + би и - л2 для относительно больших (но по-прежнему скромных)
значений п. И все равно, к моменту времени, когда п = 1500, разница между

значениями функций становится 10-кратной. Если бы мы увеличили шкалу
п еще в 10,100 или 1000 раз для того, чтобы получать задачи с интересными
размерами, разница между двумя функциями стала бы просто огромной.
Имеется еще одно обоснование полезности принципа асимптотического
анализа. Допустим, что у вас имеется фиксированный бюджет времени,
например час или день. Каким образом привлечение дополнительных вы­
числительных мощностей позволит вам влиять на подвластный размер
вычислительно разрешимой задачи? С алгоритмом, который выполняется
со временем, пропорциональным значению размера входных данных, че­
тырехкратное увеличение вычислительной мощности позволяет решать
задачи с размерностью в четыре раза больше, чем раньше. С алгоритмом,
который выполняется со временем, пропорциональным квадрату размера
входных данных, вы сможете решать задачи, размерность которых только
,в два раза больше, чем раньше.

58

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

1.6.4. Что такое «быстрый» алгоритм?
Принимая во внимание наши три руководящих принципа, сформулируем
следующее определение «быстрого алгоритма»:

«Быстрый алгоритм» — это алгоритм, для которого с увеличением
размера входных данных наихудшее время исполнения растет медленно.
Целесообразность использования категории «наихудшее время исполнения»
следует из нашего первого руководящего принципа, описывая который мы
обосновали, что важно ориентироваться на время исполнения, которое не
исходит из наличия каких-либо предметных знаний, допущений, упрощений
применительно к входным данным. Наши второй и третий руководящие прин­
ципы, исходящие из понимания того, что значения коэффициентов зависят от
особенностей языка и машинной архитектуры и ввиду этого нам надо укрупнять
коэффициенты и отметать детали, являются причинами, почему нам важно
сосредоточиваться именно на темпе роста времени исполнения алгоритма.

ЛЕГКОВЕСНЫЕ ПРИМИТИВЫ

Алгоритм с линейным или почти линейным временем исполнения можно
представить как примитив-заготовку, который мы можем использовать,
по существу, «беззатратно» с точки зрения вычислительной нагрузки, по­
скольку объем требуемых для его исполнения операций едва ли больше,
чем требуется для того, чтобы прочитать входные данные. Классическим
примером такого легковесного примитива является сортировка, и мы
также изучим еще несколько других. Когда у вас есть невероятно быстрый
примитив, относящийся к вашей задаче, почему бы им не воспользо­
ваться? Например, вы всегда можете отсортировать данные на этапе
предварительной обработки, даже если вы не совсем представляете,
как это пригодится позже. Одна из целей этой книги — пополнить ваш
алгоритмический арсенал как можно большим количеством легковесных
примитивов, готовых к применению по вашему усмотрению.

Что мы имеем в виду, говоря, что время исполнения алгоритма «растет мед­
ленно»? Дело в том, что почти для всех задач, рассматриваемых нами, идеалом
(этаким Святым Граалем, к которому надо стремиться) является линейно-вре-

1.6. Основные принципы анализа алгоритмов

59

менной алгоритм — тот, для которого время исполнения прямо пропорцио­
нально зависит от размера входных данных. Значение установленного нами
ранее предела времени исполнения алгоритма MergeSort, пропорциональное
п log и, является незначительно сверхлинейным и поэтому все же хуже, чем
линейное время работы. Нам удастся спроектировать линейно-временные
алгоритмы для некоторых задач, но не для всех. В любом случае, линейно-за­
висимое время — это наилучший сценарий, к которому мы будем стремиться.

ВЫВОДЫ

* Алгоритм — это набор четко сформулированных правил для
решения некоторой вычислительной задачи.
* Число примитивных операций, выполняемых алгоритмом
умножения двух и-значных чисел в столбик, которому вы
обучились в начальной школе, описывается как квадратичная
функция числа и.

* Умножение Карацубы — это рекурсивный алгоритм целочислен­
ного умножения, в котором, в отличие от обычного рекурсивного
алгоритма, используется метод Гаусса с целью экономии на одном
рекурсивном вызове.

4е Опытные программисты и специалисты в области computer
science обычно мыслят и обмениваются информацией об алго­
ритмах, используя довольно абстрактные описания высокого
уровня, а не подробные реализации.

* Алгоритм сортировки слиянием MergeSort — это алгоритм типа
«разделяй и властвуй», который разбивает входной массив на две
половины, рекурсивно сортирует каждую половину и объединяет
результаты, используя подпрограмму слияния Merge.
* При игнорировании постоянных коэффициентов и членов низ­
ших порядков при расчете времени исполнения число операций,
выполняемых алгоритмом MergeSort для сортировки п элементов,
растет как функция п log, п. В анализе используется дерево ре­
курсии, чтобы удобно организовать работу, выполняемую всеми
рекурсивными вызовами.

60

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

♦ Поскольку функция log2 п растет медленно в зависимости от л,
то алгоритм MergeSort, как правило, быстрее, чем более простые
алгоритмы сортировки, которые характеризуются квадратич­
ным ростом числа операций. Для большого п улучшение будет
радикальным.

♦ Три руководящих принципа анализа алгоритмов: (i) анализ наи­
худшего случая, который дает нам алгоритмы, хорошо работающие
без допущений о природе входных данных; (ii) анализ значимых
деталей, который уравновешивает предсказательную силу с ма­
тематической простотой, игнорируя постоянные коэффициенты
и члены низших порядков; и (iii) асимптотический анализ, пред­
ставляющий собой смещение в сторону больших входных данных,
то есть данных, требующих алгоритмической изобретательности.
♦ «Быстрый алгоритм» — это алгоритм, время работы которого
в худшем случае растет медленно, в зависимости от роста раз­
мера входных данных.

♦ «Легковесный примитив» — это алгоритм, который выполняется
за линейное или почти линейное время, кото