Оглавление
Предисловие ............................................................................................. 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
Оглавление 7
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. Для многочленов степени k О-большое является O(nk
).................77
2.3.2. Для многочленов степени k О-большим не является O(nk −1).........79
8   Оглавление
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. Подсчет инверсий за время O(n log n)..................................................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. Пример (n = 2)............................................................................105
3.3.3. Простой алгоритм.......................................................................106
Оглавление 9
3.3.4. Подход «разделяй и властвуй» ...................................................107
3.3.5. Экономия времени на рекурсивном вызове.................................109
3.3.6. Детали........................................................................................111
3.3.7. Решение тестового задания 3.3...................................................112
*3.4. Алгоритм со временем O(n log n) для ближайшей пары....................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 (a).....................................................122
3.4.9. Доказательство леммы 3.3 (b).....................................................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
10   Оглавление
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
Оглавление 11
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. Сортировка требует Ω(n log n) сравнений .........................................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
12   Оглавление
*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
Приложение A. Краткий обзор доказательств по индукции........................236
A.1. Шаблон для доказательств по индукции........................................236
A.2. Пример: замкнутая формула..........................................................237
A.3. Пример: размер полного двоичного дерева...................................238
Приложение Б. Краткий обзор дискретной вероятности ............................239
Б.1. Выборочные пространства.............................................................240
Б.2. События ........................................................................................241
Б.3. Случайные величины.....................................................................243
Б.4. Математическое ожидание ............................................................244
Б.5. Линейность математического ожидания ........................................247
Б.6. Пример: распределение нагрузки..................................................250