Главная Грокаем алгоритмы

Грокаем алгоритмы

0 / 0
Насколько вам понравилась эта книга?
Какого качества скаченный файл?
Скачайте книгу, чтобы оценить ее качество
Какого качества скаченные файлы?
Алгоритмы - это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузится в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу и вы сразу поймете, что алгоритмы - это просто. А грокать алгоритмы - это веселое и увлекательное занятие.
Год:
2017
Издательство:
Питер
Язык:
russian
Страницы:
290
Файл:
PDF, 69,45 MB

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

 
0 comments
 

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

Грокаем алгоритмы

Год:
2017
Язык:
russian
Файл:
DJVU, 12,63 MB
0 / 0
Aditya Bhargava

Grokking

Algorithms
An illustrated guide for programmers

and other curious people

Адитъя Бхаргава

Гр окаем

алгоритмы
Иллюстрированное пособие
для программистов и любопытствующих

С1нкт-Петер6урr

• Моск11 • Ек1термн6урr ·Воронеж

Нижний Новгород. Ростов-на-Дону

С1м1р1

• Минск

2017

Адитья Бхаргава

Грокаем алгоритмы. Иллюстрированное пособие
для программистов и любопытствующих
Серия «Библиотека программиста»
Перевел с английского Е. Матвеев
Заведующая редакцией

Ю. Сергиенко

Ведущий редактор

Н. Римицан

И. Карпова

Литера~урный редактор

с. MCL1UK06Q

Художник

Корректоры

Н. Викторова, Г Ш1'аmова

Верстка

ББК

УДК

Л. Егорова

32.973-018
004.421

Бхаргава А.
Б94

Грокаем алгоритмы. Иллюстрированное пособие для программистов и любо­

пытствующих.

-

СПб.: Питер,

2017. -

288

с. : ил.

-

(Серия «Библиотека про­

граммиста»).

ISBN 978-5-496-02541-6
Алгоритмы -

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

были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую фило­
софию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями,

но хотите ли вы тратить на это свое время? Огкройте великолепно иллюстрированную книгу, и вы сразу
поймете, что алгоритмы

это просто. А rрокать алгоритмы

-

-

это веселое и увлекательное занятие.

12+ (В соответствии с Федеральным законом от 29 декабря 201 О г.
ISBN 978-1617292231 англ .
ISBN 978-5-496-02541-6

© 2016

Ьу

Manning

№ 436-ФЗ .)

PuЫications Со .

гights гeserved .

All

©Перевод на русский язык ООО Издательство «Питер•,

2017

©Издание на русском языке , оформление ООО Издательство
«Питер» ,

2017

©Серия «Библиотека программиста»,

Права на издание получены по соглашению с

2017

Manning. Все права защищены. Никакая часть данной книги не

может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских
прав .

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

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

СХЮ «Питер Пресс» ,
Налоговая льгота

192102, Санкт-Петербург,

-

ул. Андреевская (д. Волкова),

общероссийский классификатор продукции ОК

3, литер

А, лом. 7Н .

034-2014, 58.1 t .12.000 -

Книги печатные профессиональные, технические и научные.
Подписано в печать

23.12.16.

Формат 70х100/16. Бумага офсетная. Усл. л. л.

24,510.

Тираж

1700.

Заказ № ВЗК-06096-16.
Отпечатано в АО « Первая Образцовая типография» . филиал «до м печати

-

в полном соответствии с качеством предоставленных материалов .

610033 , г.

Киров. ул. Московская ,

http ://www.gipp. kirov. гu ;

122. Факс: (8332) 53-53-80, 62-10-36
e-mail: oгder@gipp.kirov.ru

ВЯТКА »

Оглавление

Предисловие

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

12

Благодарности

О книге

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Структура книги

... ... .. .......... . .... . . . . .... ... ... .. . .... .. ...
........................................
Для кого предназначена эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Условные обозначения и загружаемые материалы . . . . . . . . . . . . . . . . . . . . . . .
Об авторе .......... . ................ . ........... . ...... . ......
От издательства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Как работать с этой книгой

Глава

1.

Знакомство с алгоритмами

. . . . . . . . . . . . . . . . . . . . . 18

Введение

. .. . . ....... . ..... . .. . ... . ... . . .... . ..... . . . . . .. ... . . .
..........................
Что вы узнаете о решении задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Бинарный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Более эффективный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Что вы узнаете об эффективности алгоритмов

Упражнения

...... . ......... . . . .... ... .. . ... . .. ... .. .... . ..... ..

Время выполнения.

............................................
...................................................
выполнения алгоритмов растет с разной скоростью ... . . .. . . . .. . ..

« О-большое »

Время

15
16
16
17
17
17

18
19
19
20
23
27
28
29
29

б

Оглавление

Наглядное представление «О-большое» .............................

............
Типичные примеры «О-большого» ..... . .............. . ............
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Задача о коммивояжере .........................................
Шпаргалка ..... .. .... ... .......................................
«О-большое» определяет время выполнения в худшем случае

Глава

2.

Сортировка выбором

. . . . . . . . . . . . . . . . . . . . . . . . . . 40

Как работает память

.............................................
........... . .. .. .......................
Связанные списки ..... .. .................. . ......... .. ........
Массивы . .... .............. .... . .. . . . ... .... ....... .. .......
Терминология ................................................
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Вставка в середину списка . ................. . ....................
Удаление ............... .... . .. ........... . .... . .... .. ... .. ..
Упражнения . ... . ................... ... .. .. ... .. . .. .. .. . ........
Сортировка выбором . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Пример кода . .. . .... ...... .. . .... ..... ............. . . .. . .. .....
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Массивы и связанные списки

Глава

3.

Рекурсия

......................................................
Базовый случай и рекурсивный случай ................................
стек ............... .......... . ... ..... . .......................
Стек вызовов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Стек вызовов с рекурсией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Шпаргалка ....................... .. ........ .... .... . ..... .. .. . .

4.

Быстрая сортировка

«Разделяй и властвуй»

60
63
65
66
68
69
73
74

.......................... 75

... .... ... . ....... .... ... ....... . .. ... .. ... .
....................................................
Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Снова об «О-большом» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Сортировка слиянием и быстрая сортировка .........................
Средний и худший случай .......................................
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Упражнения

41
43
45
46
47
48
49
50
51
53
57
58

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Рекурсия

Глава

32
34
35
36
37
39

76
85
85
92
93
95
99
99

Оглавление

Глава

5.

Хеш-таблицы

Хеш-функции

Упражнения

7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

Примеры использования

.........................................
............................
Исключение дубликатов . .. ............ . ............. . .... . .....
Использование хеш-таблицы как кэша . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Шпаргалка ............. . ....... .. ...........................
Коллизии ........................ .. ...... ..... .... .. ...... .. ..
Быстродействие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Коэффициент заполнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Хорошая хеш-функция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

107
108
110
112
116
116
119
122
124
Упражнения ................................................... 125
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Использование хеш-таблиц для поиска

Глава

6.

Поиск в ширину

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Знакомство с графами

...............
....................
Поиск в ширину . . . . . . . . . . . . . . . . . . . .
Поиск кратчайшего пути . . . . . . . . . . .
Очереди .. .................. . ..
Что такое граф?

Упражнения

....
....
....
....
....

........................
........................
........................
........................
........................

. ....... . .... . ............ . ........ .. ..............

Реализация графа

..............................................
...........................................
выполнения .. . . . ......... . .................... ... ......

Реализация алгоритма
Время

Упражнения

Шпаргалка

Глава

7.

...................................................

....................................................

Алгоритм Дейкстры

128
131
132
135
136
137
138
141
146
147
150

. . . . . . . . . . . . . . . . . . . . . . . . . . 151

Работа с алгоритмом Дейкстры

....................................
................. .. .. ... ............. .. ..........
История одного обмена ..........................................
Ребра с отрицательным весом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

152
157
160
167
170
Упражнения .. .. ..... . ................... ...... ... . ............ 181
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Терминология

Глава

8.

Жадные алгоритмы

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

Задача составления расписания

Задача о рюкзаке

. . . . . . . . . . . . . . . . . . . . . . . . . . 182

8

Оглавление

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

187
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Приближенные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
NР- полные задачи .............................................. 196
Задача о коммивояжере - шаг за шагом . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Как определить, что задача является NР-полной? . . . . . . . . . . . . . . . . . . . . 202
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

Задача о покрытии множества

Глава

9.

Динамическое программирование

. . . . . . . . . . . . . 206

Задача о рюкзаке

...............................................
............................................
Динамическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Задача о рюкзаке: вопросы .......................................
Что произойдет при добавлении элемента? .........................
Простое решение.

Упражнения

. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Что произойдет при изменении порядка строк?

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

Упражнения

........ ...........................................

.
........
Заполнение таблицы . . . . . . . .
Решение . . . . . . . . . . . . . . . . .

..........................
..........................
..........................
..........................
подпоследовательность . . . . . . . . . . . . . . . . . . . . . . .
подпоследовательность - решение. . . . . . . . . . . . . .

Самая длинная общая подстрока

Построение таблицы

Самая длинная общая

Самая длинная общая
Упражнения
Шпаргалка

Глава

10.

..
..
..
..

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

...................................................

....................................................

Алгоритм

k

Апельсины и грейпфруты

ближайших соседей

206
207
208
217
217
220
220
221
221
221
223
224
225
226
226
226
228
229
230
232
233
235
235

. . . . . . . . . . . . . . 236

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Построение рекомендательной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Извлечение признаков. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

Оглавление

..................................................
.............................................
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Знакомство с машинным обучением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
OCR ..... . ....... . .. . ........ . ......... . .............. ... ..
Построение спам-фильтра ............. . ...... . .................
Прогнозы на биржевых торгах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Регрессия

Выбор признаков

Глава

11.

Что дальше?

Деревья

...............
Инвертированные индексы .
Преобразование Фурье . . .
Параллельные алгоритмы .
MapReduce . . . . . . . . . . . . .

245
248
249
249
250
251
252
252

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

...........................
...........................
...........................
...........................
...........................
Для чего нужны распределенные алгоритмы? . . . . . . . . . . . . . . . . . . . . . . .
Функция map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Функция reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Фильтры Блума и Hyperloglog .................................. . ..
Фильтры Блума . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hyperloglog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Алгоритмы SHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Сравнение файлов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Проверка паролей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Локально-чувствительное хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Обмен ключами Диффи-Хеллмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Линейное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эпилог ....... . ...... .. ........... . ................ . ..........
Ответы к упражнениям

9

........
........
........
........
........

....
....
....
....
....

254
258
259
260
261
261
261
262
263
265
265
266
267
268
269
270
272
273

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

Посвящается моим родителям

-

Сангите и Йогешу

Предисловие

Сначала программирование было для меня простым увлечением. Я изучил
азы по книге

«Visual Basic для

чайников» , а потом стал читать другие книги,

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

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

Через несколько лет я написал свое первое иллюстрированное сообщение

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

ному программированию ,

Git, машинному обучению и параллелизму. Кстати

говоря, в начале своей карьеры я писал довольно посредственно. Объяснять
научные концепции трудно . Чтобы придумать хорошие примеры, требуется
время, чтобы объяснить сложную концепцию

-

тоже. Проще всего умолчать

о сложных моментах. Я думал, что у меня все хорошо получается, пока по­

сле одной из моих популярных публикаций ко мне не обратился коллега со
словами: « Я прочитал твой материал, но все равно ничего не понял» . Мне еще
предстояло многое узнать о том, как пишутся научны е тексты.

В самом разгаре работы над иллюстрированными публикациями в благе
ко мне обратилось издательство

Manning· с

предложением написать иллю­

стрированную книгу. Оказалось, что редакторы

Manning; хорошо умеют объ ­

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

У меня была совершенно определенная цел ь: мне хотелось создать книгу,
которая бы объясняла сложные научные темы и легко читалась. С момента

написания моего первого сообщения в благе я прошел длинный путь; на­
деюсь, моя книга покажется вам простой и содержательной.

•

•••••••••••••••••••••••• "

• ••••••••••••• "

•

"

•

"

•

"

1

Благодарности

Спасибо издательству

Manning, которое дало мне возможность написать эту

книгу и предоставило большую творческую свободу в ходе работы. Я бла­

годарен издателю Марджану Бейсу

(Marjan Васе),

Майку Стивенсу

(Mike
(Bert Bates),
который научил меня писать на научные темы, и Дженнифер Стаут Qennifer
Stout) - невероятно отзывчивому редактору, всегда готовому прийти на
помощь. Спасибо всем участникам производственной группы Manning:
Кевину Салливану (Kevin Sullivan), Мэри Пьержи (Магу Piergies), Тиф­
фани Тейлор (Tiffany Taylor), Лесли Хаймс (Leslie Haimes) и всем осталь­
Stephens)

за то, что он ввел меня в курс дела, Берту Бейтсу

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

(Karen Bensdon), Роба Грина (Rob Green),
(Michael Hamrah), Озрена Харловица (Ozren Harlovic), Ка­
лин Хейсти (Colin Hastie), Кристофера Хаупта (Christopher Haupt), Чака
Хендерсона (Chuck Henderson), Павла Козловски (Pawel Kozlowski), Амита
Ламба (Amit Lamba), Жана-Франсуа Марина Qean-Fraщ:ois Morin), Робер­
та Моррисона (Robert Morrison), Санкара Раманатана (Sankar Ramanathan),
Сандера Рассела (Sander Rossel), Дуга Спарлинага (Doug Sparling) и Дэми­
ена Уайта (Damien White).
Майкла Хамра

Спасибо всем, кто помог мне в достижении цели: сотрудникам

Flashkit,

научившим меня программировать; многочисленным друзьям, которые

помогали мне в работе

-

рецензировали главы, делились советами и пред­

лагали разные варианты объяснений. Это были Бен Вайнгер
Карл Пьюзон

(Karl Puzon),

Алекс Мэннинг

(Ben Vinegar),
(Alex Manning), Эстер Чан

13

Благодарности

(Anish Bhatt), Майкл Гласе (Michael Glass),
Махди (Nikrad Mahdi), Чарльз Ли (Charles Lee), Джаред Фридман

(Esther Chan),
Никрад

Аниш Бхатт

Qared Friedшan), Хема Маникавасагам (Неша Manickavasagaш), Хари Рад­
жа (Hari Raja), Мурали Гудипати (Murali Gudipati), Шриниваса Барадан
(Srinivas Varadan) и другие; также спасибо Джерри Брэди (Gerry Brady),
моему учителю по теории алгоритмов. Отдельное большое спасибо таким
классикам алгоритмов, как

CLRS',

Кнут и Стрэнг; безусловно, я стою на

плечах гигантов.

Папа , мама, Приянка и все родные: спасибо за вашу неустанную поддерж­

ку. Огромное спасибо моей жене Мэгги. Впереди у нас много прекрасных
мом е нтов, и мне уже не придется проводить вечер пятницы за переписы­
ванием книги .

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

'

Авторы класс ичес кой книги по алгоритмам: Кармен , Л ейзе рсон , Ривест, Штайн.
меч. п ер.

-

При­

О книге

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

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

В книге приводится множество примеров. Моя цель

-

не вывалить на чита­

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

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

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

списков (глава

2), просто

вспомните, как ищете места для компании в ки­

нотеатре. Наверное, вы уже поняли, что я сторонник визуального стиля

обучения,

-

в книге полно рисунков .

Содержимое книги было тщательно продумано. Нет смысла писать книгу

- для этого есть такие источники,
Khan Academy. Все алгоритмы, описанные в книге, имеют

с описанием всех алгоритмов сортировки

как Википедия и

практическую ценность. Я применял их в своей работе программиста, и они

закладывают хорошую основу для изучения более сложных тем.
Приятного чтения!

Структура книги

15

Структура книги
В первых трех главах закладываются основы:

1:1 Глава

1-

вы изучите свой первый нетривиальный алгоритм: бинарный

поиск. Также здесь рассматриваются основы анализа скорости алгорит ­

мов с применением «О -большое» . Эта запись часто используется в книге
для описания относительной быстроты выполнения алгоритмов.

1:1 Глава

2-

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

данных: массивами и связанными списками. Эти структуры данных

часто встречаются в книге и используются для создания более сложных
структур данных, например хеш-таблиц (глава

1:1 Глава З

-

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

-

5).

удобном приеме, используемом

многими алгоритмами (наприм е р алгоритмом быстрой со ртировки ,
о котором рассказано в главе

4).

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

в разных областях.

1:1 Методы решения задач ра сс матриваются в главах

4, 8

и

9.

Если вы

столкнулись со сложной задачей и не зна ете , как эффективно ее решить,
воспользуйтесь стратегией «разделяй и вл аствуй» (глава

динамического программирования (глава

9).

4) или

методом

А если вы поняли , что эф­

фективного решения не существует, попробуйте получить приближен­
ный ответ с использованием жадного алгоритма (глава

1:1 Хеш-таблицы рассматриваются в главе

5.

8).

Хеш - таблицы

-

исключи­

тельно полезная структура данных, предназначенная для хранения пар

ключей и значений (например имени человека и адреса электронной
почты или имени пользователя и пароля). Трудно переоценить практи­

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

хеш-таблицей и можно ли смоделировать задачу в виде графа.

1:1 Алгоритмы графов рассматриваются в главах

6 и 7.

Графы используются

для моделирования сетей: социальных, дорожных, нейронных или лю-

16

О книге

бых других совокупностей связей. Поиск в ширину (глава
Дейкстры (глава

7)

6) и алгоритм

предназначены для поиска кратчайшего расстояния

между двумя точками сети: с их помощью можно вычислить кратчайший
маршрут к точке назначения или количество промежуточных знакомых

у двух людей в социальной сети.

о Алгоритм

k ближайших

соседей рассматривается в главе

10. Это про­

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

систему прогнозирования курсов акций

-

словом, всего, что требует про­

гнозирования значений («Мы думаем, что Адит поставит этому фильму

4 звезды » )

ил и классификации объектов («Это буква

Q» ).

о Следующий шаг: в глав е 11представлены10 алгоритмов, которые хоро­
шо подойдут для дальнейшего изучения темы .

Как работать с этой книгой
Порядок изложения и содержимое книги были тщательно продуманы.
Если вас очень сильно интересует какая-то тема

-

переходите прямо к ней.

В противном случае читайте главы по порядку, они логически переходят
одна в другую.

Я настоятельно рекомендую самостоятельно выполнять код всех примеров .

Вы не поверите , насколько это важно. Просто введите мои примеры кода

«с листа » (или загрузите их по адресу

algoritl1ms

или

leJWW.manning.com/ books/grokkinghttps.j/p)thub.com/ egonschiele/ grokking_ algorithms) и выпол­

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

две, иногда з а

5- 10

-

обычно задачи решаются за минуту или

минут. Упражнения помогут проверить правильность

понимания материала. Если вы где-то сбились с пути, то узнаете об этом ,
не заходя ели шком далеко .

Для кого предназначена эта книга
Эта книга предназначена для читателей, которые владеют азами программи­

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

От издательства

17

А может, вы хотите понять, где вам моrут пригодиться алгоритмы. Ниже при­
веден короткий и неполный список людей, которым может пригодиться книга:
о

программисты-самоучки;

о

студенты, начавшие изучать программирование;

о

выпускники, желающие освежить память;

о специалисты по физике/математике/другим дисциплинам, интересую­
щиеся программированием.

Условные обозначения
и загружаемые материалы
Во всех примерах в книге используется

Python 2.7.

Весь программный

код оформлен моноширинным шрифтом, чтобы его можно было отличить от
обычного текста. Некоторые листинги сопровождаются аннотациями, под­
черкивающими важные концепции.

Код примеров книги можно загрузить на сайте издательства по адресу

marming;.com/ books/grokking-algorithms

или

www.

https://github.com/egonschiele/

gгokkiщг;_algorithms.
Я считаю, что мы лучше всего учимся тогда, когда нам это нравится,

-

так

что получайте удовольствие от процесса ... и запускайте примеры кода!

Об авторе
Адитья Бхаргава работает программистом в

Etsy, интернет-рынке авторских

работ. Он получил степень магистра по информатике в Чикагском универси­

тете и ведет популярный иллюстрированный технический блог adit.io.

От издательства
Ваши замечания, предложения, вопросы отправляйте по адресу

comp@piter.

сот (издательство ~питер1>, компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию
о наших книгах.

1

Знакомство с алгоритмами

В этой главе

./ Закладываются основы для остальных глав книги .
./ Вы напишете свой первый алгоритм поиска (бинарный
поиск) .
./

Вы узнаете, как описывается время выполнения алго­

ритма («О-большое») .

./

Будет представлен стандартный прием, часто приме­

няемый при проектировании алгоритмов (рекурсия).

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

быстрыми или решали интересные задачи ... или и то и другое сразу. Вот
лишь несколько примеров .

Что вы узнаете о решении задач

о В главе

1 речь

19

пойдет о бинарном поиске и о том, как алгоритмы могут

ускорить работу кода. В одном примере алгоритм сокращает количество
необходимых действий с
о Устройство
вах

4 миллиардов до 32 !

GPS использует алгоритмы из теории графов (об этом в

6, 7 и 8) для

гла­

вычисления кратчайшего пути к точке назначения.

о При помощи методов динамического программирования (см. главу

9)

можно создать алгоритм для игры в шашки.

В каждом случае я опишу алгоритм и приведу пример. Затем мы обсудим
время выполнения алгоритма в понятиях ~о-большое» . В завершение будут
рассмотрены типы задач, которые могут решаться с применением того же
алгоритма.

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

в этой книге уже доступна на вашем любимом языке программирования и вам

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

-

массив или список? Даже выбор другой

структуры данных может оказать сильное вл ияние на результат.

Что вы узнаете о решении задач
Вы освоите методы решения задач, которые вам сейчас, возможно, неиз­
вестны. Примеры:

о Если вы любите создавать видеоигры, вы можете написать систему на

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

о Вы узнаете, как построить рекомендательную систему на базе
ших соседей.

k ближай­

20

Глава

1.

Знакомство с алгоритмами

о Некоторые проблемы не решаются за разумное время! В части книги, по­
священной NР-полноте задач, рассказано о том, как идентифицировать

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

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

Бинарный поиск
Предположим, вы ищете фамилию человека в те­

лефонной книге (какая древняя технология!). Она
начинается с буквы «К». Конечно, можно начать
с самого начала и перелистывать страницы, пока

вы не доберетесь до буквы «К». Но скорее всего
для ускорения поиска лучше раскрыть книгу на

середине: ведь буква «К» должна находиться где­

то ближе к середине телефонной книги.
Или предположим, что вы ищете слово в словаре,

и оно начинается с буквы
чать с середины.

«0».

И снова лучше на­

Бинарный поиск

21

Теперь допустим, что вы вводите свои

данные при входе на

Facebook

Facebook.

При этом

необходимо проверить, есть ли

у вас учетная запись на сайте. Для это­
го ваше имя пользователя нужно найти

в базе данных. Допустим, вы выбрали

себе имя пользователя ~karlrnageddon~.

Facebook может начать с буквы А и прове­
рять все подряд, но разумнее будет начать
с середины.

Перед нами типичная задача поиска. И во всех этих случаях для решения

задачи можно применить один алгоритм: бинарный поиск.
Бинарный поиск

-

это алгоритм; на входе он получает отсортированный

список элементов (позднее я объясню, почему он должен быть отсортиро­

ван). Если элемент, который вы ищете, присутствует в списке, то бинарный
поиск возвращает ту позицию, в которой он был найден. В противном слу­

чае бинарный поиск возвращает null.
Например:

Ищем компанию

в телефонной книге
с применением

бинарного поиска

i
~ИЧЕrо

22

Глава

1.

Знакомство с алгоритмами

Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую
игру: я загадал число от 1до100.

Вы должны отгадать мое число, использовав как можно меньше попыток.

При каждой попытке я буду давать один из трех ответов: «мало», «много»
или «угадал».

Предположим, вы начинаете перебирать все варианты подряд:

1, 2, 3, 4 ""

Вот как это будет выглядеть.

t~l

2 \

~

\ ... "

f

,I)())

Плохой способ
угадать число

Бинарный поиск

23

Это пример простого поиска (возможно, термин «тупой поиск» был бы
уместнее). При каждой догадке исключается только одно число. Если я за­

гадал число

99, то ,

чтобы добраться до него, потребуется

99

попыток!

Более эффективный поиск
Существует другой, более эффективный способ. Начнем с

50.

(§) a~~"'O"'J.. ~-')'-.-\~~:·\~-~_1~j51 !S2 \5З\ ·+3
ЬСЕ эти чием
СЛИШКОМ М~ЛЫI

Слишком мало ... но вы только что исключили половину чисел! Теперь вы
знаете, что все числа

1-50 меньше загаданного.

Следующая попытка:

75.

На этот раз перелет ... Но вы снова исключили половину оставшихся чисел!

С бинарным поиском вы каждый раз загадываете число в середине диапазона
и ис'КЛючаете половину оставшихся чисел. Следующим будет число
середине между

50

и

75).

63

(по

24

Глава

1.

Знакомство с алгоритмами

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

1100 ЭЛЕМснто3 ~

1Sф / ---'>/ 25 1-'> [ill ---'>ш ---'> l±J -1I) ~
t ШАГОВ

'

iri :
1

'

При бинарном поиске каждый раз исключается половина чисел

Какое бы число я ни задумал, вы гарантированно сможете угадать его не бо­
лее чем за

7 попыток, потому что с каждой попыткой исключается половина

оставшихся чисел!
Предположим, вы ищете слово в словаре с

240 ООО словами.

Как вы думаете,

сколько попыток вам понадобится в худшем случае?

ПРОСТО~ ПОИСК:

_

ШАГОВ

БИНАРНЫ~ ПОИСК: -

ШАГОВ

При простом поиске может потребоваться

240

ООО попыток, если искомое

слово находится на самой последней позиции в книге. С каждым шагом

бинарного поиска количество слов сокращается вдвое , пока не останется
ТОЛЬКО ОДНО СЛОВО .

~t+Ф "\--+( J3Ф~~ [бФ~] ___,. )зФ~ 1--) \1s1< / ~rт.sкJ~lз~s~]

(

[s'I] <-

[ 1111

1<-- \z3s I

+{+<А 1...@!J .... [iнs])

~-)ш~ш~1 4

\

J~~
1&

1

/

/

-.;ш:-

ШАГОВ

,

1 1 '

Бинарный поиск

Итак, бинарный поиск потребует

18

шагов

-

25

заметная разница! В об­

щем случае для списка из п элементов бинарный поиск выполняется за

log 2n шагов, тогда как простой поиск будет выполнен зап шагов.

26

Глава

1.

Знакомство с алгоритмами

r----- -- ----- -- ------ --- --- --- -- -------- ------,
ПРИМЕЧАНИЕ

Бинарный поиск работает только в том случае, если список отсортирован.
Например, имена в телефонной книге хранятся в алфавитном порядке, и вы

можете воспользоваться бинарным поиском. А что произойдет, если имена
не будут отсортированы?
L---------------------------------------- -- - -- ~

Посмотрим, как написать реализацию бинарного поиска на

Python. В следу­

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

ной последовательности ячеек, которая называется массивом. Нумерация
ячеек начинается с О: первая ячейка находится в позиции с номером О,
вторая

-

в позиции с номером

1 и т. д.

Функция binary_search получает отсортированный массив и значение. Если
значение присутствует в массиве, то функция возвращает его позицию. При
этом мы должны следить за тем, в какой части массива проводится поиск.

Вначале это весь массив:

low = 0
high = len(list) - 1

LO\.J

IOGH

J,

J.

[·
\...

1 •

1 .

1. J

"('

.J

ЧИСЛА, ПО КОТОРЫМ
П'РО&О.П.ИТСЯ ПОИСК

Каждый раз алгоритм проверяет средний элемент:

mid = (low + high) / 2
guess = list[mid]

-ОС:· · ·

Если значение

{low+high)

чески округляет значение

нечетно, то

mid

Python

автомати­

в меньшую сторону

Упражнения

27

Если названное число было слишком мало, то переменная low обновляется
соответственно:

i f guess < item :
low = mid + 1
НОВОЕ
.ЗНА­

LO\,J

ЧЕНИЕ

1-HGI-\

ф

J,

1.
А если догадка была слишком велика, то обновляется переменная high . Полный
КОД ВЫГЛЯДИТ так:

В переменнь1х

def Ыnary_search(list, item):
low = 0///
high = len(list)-1 .....""" .
while low <= high :
mid = (low + high)
guess = list[mid]
if guess == item :
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list

= [1,

3, 5, 7, 9)

-с

границы

поиск

... "..

""" "" ··" ·

-с
-с "·

low и high хранятся

-с .."".::::::.····· той части списка, в которой выпоnняется

Пока эта часть не сократится до одного эnемента

.•.
" ." ... "

".•

проверяем средний эnемент

Значение найдено

-с """"" " ".

Много

-с " " "

Мало

-с

Значение не существует

<С·

А теперь протестируем функцию!

print Ыnary_search(my_list, 3) # => 1 ....."" """"
print Ыnary_search(my_list, -1) # => None "'·

".

Вспомните: нумерация эnементов нa­

чинается с О. Второй ячейке cooтвeтствует индекс

"None"

в

1

Python означает

"ничто". Это

признак того, что эnемент не найден

Упражнения
1.1

Имеется отсортированный список из

128 имен,

и вы ищете в нем зна­

чение методом бинарного поиска. Какое максимальное количество
проверок для этого может потребоваться?

28

1.2

Глава

1.

Знакомство с алгоритмами

Предположим, размер списка увеличился вдвое. Как изменится мак­
симальное количество проверок?

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

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

одно за другим. Если список состоит из

100 чисел,

может потребоваться до

100 попыток. Для списка из 4 миллиардов чисел потребуется до 4 миллиар­
дов попыток. Таким образом, максимальное количество попыток совпадает
с размером списка. Такое время выполнения называется линейным.

С бинарным поиском дело обстоит иначе. Если список состоит из

100 эл е ­
7 попыток. Для списка из 4 миллиардов эле ­
более 32 попыток. Впечатляет, верно? Бинарный

ментов, потребуется не более
ментов потребуется не

поиск выполняется за логарифмическое время. В следующей таблице при ­
водится краткая сводка результатов.

11РОС.ТОК

БИНАРНЬIК

ПОIКК

поиск

100 'ЭЛЕМЕ.НТО&

J.
100
1t

попыток

ООО ООО ООО

......

1

попыток

1t

'ЭЛЕМЕНТО&

'ЭЛЕМЕНТО&

..J,

~
1t

ООО ООО ООО

ООО ООО ООО

3Z.

попытки

попыток

O(Log n)

O(n)

.,.

ЛИНЕКНОЕ

&PEMJI

~ лоrА РИФМИЧ Е.С.КОЕ.
&PEMJI

Время выполнения алгоритмов поиска

«О-большое»

29

«О-большое»
Специальная нотация «0-болъшое:1> опи­
сывает скорость работы алгоритма. Зачем
вам это? Время от времени вам придется
использовать чужие алгоритмы, а пото­

му неплохо было бы понимать, насколь­

ко быстро или медленно они работают.
В этом разделе я объясню, что представ­

\

ляет собой «О-большое:1>, и приведу спи­
сок самых распространенных вариантов
времени выполнения для некоторых ал­

горитмов.

Время выполнения алгоритмов растет

с разной скоростью
Боб пишет алгоритм поиска для

NASA.

Его алгоритм заработает, когда ра­

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

с разной скоростью. Боб пытается выбрать между простым и бинарным
поиском. Его алгоритм должен работать быстро и правильно. С одной

стороны , бинарный поиск работает быстрее. У Боба есть всего

10

секунд,

чтобы выбрать место посадки; если он не уложится в это время, то момент

для посадки будет упущен. С другой стороны, простой поиск пишется про­

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

100 элементов.
Допустим, проверка одного элемента занимает

1 миллисекунду

(мс) . При

простом поиске Бобу придется проверить

100 элементов, поэтому поиск
100 мс. С другой стороны, при бинарном поиске достаточно прове­
всего 7 элементов (log 2 100 равен приблизительно 7), а поиск займет

займет

рить

7

мс. Но реальный список может содержать более миллиарда элементов.

Сколько времени в таком случае потребуется для выполнения простого
поиска? А при бинарном поиске? Обязательно ответьте на оба вопроса,
прежде чем продолжить чтение.

30

Глава

1.

Знакомство с алгоритмами

и

nРОС.ТОА

БllНАРНЫА ПOllC.K

ПOllC.K

З.00 мс

7

мс

Время выполнения простого и бинарного поиска для списка из 100 элементов

Боб проводит бинарный поиск с

1 миллиардом элементов, и на это уходит
30 мс (log 21 ООО ООО ООО равен приблизительно 30). «32 мс! - думает Боб. Бинарный поиск в 15 раз быстрее простого, потому что простой поиск для
100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой
поиск займет 30 х 15 = 450 мс, верно? Гораздо меньше отведенных 10 се­
кунд~. И Боб выбирает простой поиск. Верен ли его выбор?
Нет, Боб ошибается. Глубоко ошибается. Время выполнения для простого
поиска с

1 миллиардом элементов

составит

1 миллиард миллисекунд, а это

11 дней!

Проблема в том, что время выполнения для бинарного и простого

поиска растет с разной скоростью.

ПРОСТО~ ПОИСК

\00 ЭЛЕМЕНТО6

7 мс

- - - - . - - - - - - - - - - -- -- - --------- ------\О ООО ЭЛЕМЕНТО6

'

З.00 мс

БИНАРНЫ~ ПОИСК

ООО ООО ЭЛЕМЕНТО6

W секунд
:1.:1. дней

:1.4

мс

...

3~ мс

Время выполнения растет с совершенно разной скоростью!

Другими словами, с увеличением количества элементов бинарный поиск

занимает чуть больше времени. А простой поиск займет гораздо больше
времени. Таким образом , с увеличением списка бинарный список внезап­
но начинает работать гораздо быстрее простого. Боб думал, что бинарный

«О-большое»

поиск работает в
стоит из

но в

33

15

31

раз быстрее простого, но это не так. Если список со­

1 миллиарда элементов,

бинарный поиск работает приблизитель­

миллиона раз быстрее. Бот почему недостаточно знать, сколько

времени должен работать алгоритм,

-

необходимо знать, как возрастает

время выполнения с ростом размера списка. Здесь-то вам и пригодится

«О-большое>->.

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

придется выполнить п операций. Бремя

выполнения « О-большое» имеет вид О(п).
Постойте, но где же секунды? А их здесь

нет

-

«О-большое>-> не сообщает скорость

в секундах, а позволяет сравнить количе­

ство операций . Оно указывает, насколько

быстро возрастает время выполнения алгоритма.

А теперь другой пример. Для проверки списка размером п бинарному поис­
ку потребуется

log п операций.

Как будет выглядеть «О-большое»?

O(log п) .

В общем случае « О-большое>-> выглядит так:

«О-БОЛЬШОЕ, ..7f

O<.n>
'\..

l(Qf\ИЧ Е.СТ&О
ОПЕ.РЩИК

Как записывается «О-большое»

Такая запись сооб щает количество операций, которые придется выпол­

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

«0»

(а большое

-

потому что в верхнем

регистре).

Теперь рассмотрим н есколько примеров. Попробуйте самостоятельно оце­
нить время выполнения этих алгоритмов.

32

Глава

1.

Знакомство с алгоритмами

Наглядное представление «О-большое»
Чтобы повторить следующий практический пример, достаточно иметь не­
сколько листков бумаги и карандаш. Допустим, вы должны построить сетку
из

16 квадратов.

\~1
Z\
~4,_ -

'
-5 ",-1' ~ )\".'
-,-r.~ ,, .•2•
.
~

-- ," r . ""'S ,3'\ '4' ,5 . ·~
1

Алгоритм

Как допжен выглядеть

хороший алгоритм
дпя построения этой

сетки?

1

Как вариант можно нарисовать

16

квадратов, по одному за раз. Напо­

минаю: ~о-большое~ подсчитывает количество операций. В данном при­
мере рисование квадрата считается одной операцией. Нужно нарисовать

16 квадратов.

Сколько операций по рисованию одного квадрата придется

выполнить?

Сетка
рисуется

\

~о одному

_\квадрату

Чтобы нарисовать

16 квадратов, потребуется 16 шагов.

выполнения этого алгоритма?

Как выглядит время

«О-большое»

Алгоритм

33

2

А теперь попробуем иначе. Сложите лист пополам.

На этот раз операцией считается сложение листка. Получается, что одна

операция создает сразу два прямоугольника!

Сложите бумагу еще раз, а потом еще и еще.

Разверните листок после четырех сложений

-

получилась замечательная

сетка! Каждое сложение удваивает количество прямоугольников. За
рации вы создали

16 прямоугольников!

сло~Е.НМЕ.

z. сло~Е.н мя

'

J,

ш

Построение сетки эа

3

CЛO~E.HMJI

J.

4 сложения

4

4 опе­

CЛO~E.HMJI

.J,

34

Глава

1.

Знакомство с алгоритмами

При каждом складывании количество прямоугольников увеличивается
вдвое, так что

16 прямоугольников

строятся за

4 шага.

Как записать время

выполнения этого алгоритма? Напишите время выполнения обоих алго­
ритмов, прежде чем двигаться дальше.

Ответы: алгоритм

1 выполняется

за время О(п) , а алгоритм

2-

за время

O(log п).
«О-большое» определяет время выполнения
в худшем случае

Предположим, вы используете простой поиск для поиска фамилии в теле­
фонной книге. Вы знаете, что простой поиск выполняется за время О(п), то

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

нается на букву ((,А» и этот челов ек стоит на самом первом месте в вашей

телефонной книге. В общем, вам не пришлось просматривать все записи

-

вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм
за время О(п)? А может, он занял время

0(1),

потому что результат был

получен с первой попытки?
Простой поиск все равно выполняется за время О(п) . Просто в данном
случае вы нашли нужное значение моментально; это лучший возможный

случай. Однако ((,О-большое» описывает худший возможный случай . Фак­
тически вы утверждаете, что в худшем случае придется просмотреть каждую
запись в телефонной книге по одному разу. Это и есть время О(п). И это
дает определенные гарантии

-

вы знаете, что простой поиск никогда не

будет работать медленнее О(п).

r------------------------------- - --- -- -------- ,
ПРИМЕЧАНИЕ

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

4.

~------------------- -- ------------- - ------ - -- - ~

«О-большое»

35

Типичные примеры «О-большого»
Ниже перечислены пять разновидностей «О-большого», которые будут встре­
чаться вам особенно часто, в порядке убывания скорости выполнения:

о

O(log п ), или логарифмическое время. Пример: бинарный поиск.

о О(п), или линейное время. Пример: простой поиск.
Q

О(п

* log

п). Пример: эффективные алгоритмы сортировки (быстрая

сортировка

-

но об этом в главе

4).

о О(п 2 ). Пример: медленные алгоритмы сортировки (сортировка выбо­
ром

-

см. главу

2).

о О(п/). Пример: очень медленные алгоритмы (задача о коммивояжере

-

о ней будет рассказано в следующем разделе).

Предположим, вы снова строите сетку из

16 квадратов, и вы можете выбрать
5 алгоритмов. При использовании первого
алгоритма сетка будет построена за время O(log п ). В секунду выполняются
до 10 операций. С временем O(log п) для построения сетки из 16 квадратов
потребуются 4 операции (log 16 равен 4). Итак , сетка будет построена за
0,4 секунды. А если бы было нужно построить 1024 квадрата? На это бы
потребовалось log 1024 = 10 операций, или 1 секунда. Напомню, что эти
для решения этой задачи один из

числа получены при использовании первого алгоритма.

Второй алгоритм работает медленнее: за время О(п). Для построения

16 прямоугольников потребуется 16 операций , а для построения 1024 пря­
моугольников - 1024 операции. Сколько это составит в секундах?
Ниже показано, сколько времени потребуется для построения сетки
с остальными алгоритмами, от самого быстрого до самого медленного:

Pt ""ЧЕСТОО
БЫСТРО
ПPJIMO-

1

..k::=.(.L
)
УГОЛЬНМКО& О ~..,

\6
2S6

~
ОН lL
Ot·L~·) LL L
О<>-!> ;~
~
()(.,..)
-----------

~~.6 с
О.'6с
25.6с
\.0

с

\.1 с

6.4- с

3.4мин
11 мин

2S.& с

1.~ч

1.2 дня

ME.JIЛE.HHO

ьt:.3Ф1 лtм
%,&'/.\d'°мм

5Ах16'""мм

36

Глава

1.

Знакомство с алгоритмами

Существуют и другие варианты времени выполнения, но эти пять встре­
чаются чаще всего.

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

4,

после рассмотрения еще нескольких алгоритмов. А пока перечислим ос­
новные результаты :

1:1 Скорость алгоритмов измеряется не в секундах, а в темпе роста количе­
ства операций.

1:1 По сути формула описывает, насколько быстро возрастает время выпол­
нения алгоритма с увеличением размера входных данных.

1:1 Время выполнения алгоритмов выражается как «О-большое».
1:1 Бремя выполнения O(log п) быстрее О(п), а с увеличением размера спи­
ска, в котором ищется значение, оно становится намного быстрее.

Упражнения
Приведите время выполнения «О-большое» для каждого из следующих
сценариев.

1.3

1.4

Известна фамилия, нужно найти номер в телефонной книге.

Известен номер, нужно найти фамилию в телефонной книге. (Под­

сказка: вам придется провести поиск по всей книге!)

1.5

Нужно прочитать телефоны всех людей в телефонной книге.

1.6

Нужно прочитать телефоны всех людей, фамилии которых начинают­

ся с буквы «А». (Вопрос с подвохом! В нем задействованы концепции,
которые более подробно рассматриваются в главе
вет

-

скорее всего, он вас удивит!)

4.

Прочитайте от­

Упражнения

37

Задача о коммивояжере
Наверное, после прочтения предыдущего раздела вы подумали: «Уж мне-то

точно не попадется алгоритм с временем О(п!)~ Ошибаетесь, и я это сейчас
докажу! Мы рассмотрим алгоритм с очень, очень плохим временем вы­

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

задачей о коммивояжере.

Это коммивояжер.
Он должен объехать

5 городов.

38

Глава

1.

Знакомство с алгоритмами

Коммивояжер хочет побывать в каждом из

5 городов так, чтобы при этом

проехать минимальное общее расстояние. Одно из возможных решений :
нужно перебрать все возможные комбинации порядка объезда городов .

120

13'3

миль

мили

Все расстояния суммируются, после чего выбирается путь с кратчайшим

расстоянием. Для

5 городов можно создать 120 перестановок, поэтому реше­
ние задачи для 5 городов потребует 120 операций. Для 6 городов количество
операций увеличивается до 720 (существуют 720 возможных перестановок) .
А для 7 городов потребуется уже 5040 операций!
ГОРОД~

ОПЕ.РЩИИ

15

Количество операций стремительно растет

В общем случае для вычисления резу льтата при п элементах потребуется
п! (п-факториал) операций. А значит, время выполнения составит О(п!)
(такое время называется факторuальным). При любом сколько-нибудь

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

-

Солнце погаснет раньше.

100+ городов ,

сделать это

Шпаргалка

39

Какой ужасный алгоритм! Значит, коммивояжер должен найти другое
решение, верно? Но у него ничего не получится. Это одна из знаменитых

нерешенных задач в области теории вычислений. Для нее не существует

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

случае для нее можно поискать приближенное решение; за подробностями
обращайтесь к главе

10.

И последнее замечание: если у вас уже есть опыт программирования, почи­

тайте о бинарных деревьях поиска! Эти структуры данных кратко описаны
в последней главе.

Шпаргалка
c:i Бинарный поиск работает намного быстрее простого.
1:1 Время выполнения

O(log п)

быстрее О(п), а с увеличением размера спи­

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

2

Сортировка выбором

В этой главе
~

Вы познакомитесь с массивами и связанными списка­
ми

-

двумя основными структурами данных, которые

используются буквально везде. Мы уже использова­
ли массивы в главе

1 и будем использовать их почти

в каждой главе книги. Массивы чрезвычайно важны,
уделите им внимание! Впрочем, иногда вместо масси­

ва лучше воспользоваться связанным списком. В этой
главе объясняются плюсы и минусы обеих структур

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

~

Вы изучите свой первый алгоритм сортировки . Мно­
гие алгоритмы работают только с отсортированными

данными. Помните бинарный поиск? Он применяется
только к предварительно отсортированному списку.

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

свою версию «с нуля». Однако алгоритм сортировки

выбором поможет перейти к алгоритму быстрой сор­

тировки, описанному в следующей главе. Алгоритм

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

Как работает память

41

Как работает память
Представьте, что вы пришли в театр и хотите оставить свои личные вещи
в гардеробе. Для хранения вещей есть специальные ящики .

-~

~

В каждом ящике помещается один предмет. Вы хотите сдать на хранение

две вещи, поэтому требуете выделить вам два ящика.

.О.&А .Я\411КА,

ПО#.АЛУКСП\

J

ГОСПОJlМН МО#.ЕТ МСПОЛЬ.30&НЬ
&ОТ ЭТИ д&А .

)

42

Глава

2.

Сортировка выбором

И вы оставляете свои две вещи.

JОНТИК

1'

Готово, можно идти на спектакль!

В сущности, именно так работает память вашего компьютера. Она представ­
ляет собой нечто вроде огромного шкафа с множеством ящиков, и у каждого
ящика есть адрес .

~РЕС: fe~ffeeb

1

feOffeeb - адрес ячейки памяти.

Массивы и связанные списки

43

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

нения значения . Если же вам понадобится сохранить несколько элементов,
это можно сделать двумя основными способами: воспользоваться масси­
вом или списком. В следующем разделе мы обсудим массивы и списки, их

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

различаются разные способы.

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

для управления текущими делами. Описания
задач должны храниться в виде списка в памяти.

Что использовать

-

массив или связанный спи­

сок? Для начала попробуем сохранить задачи
в массиве, потому что этот способ более по­
нятен. При использовании массива все задачи
хранятся в памяти непрерывно (то есть рядом

друг с другом).

с.nмс.ок

этт п~мять

ДЕ.f\

ИСПОЛЬЗУЮТ

'\,

J,
1

OБEJI.

ТРЕНМРО6К~

~
% ~
~

ЧАК

~

.a.PYrME

44

Глава

2.

Сортировка выбором

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

-

там лежат чужие вещи!

РАJМЕ.С.ТМТЬ JДЕ.С.Ь

.3Ul.A ЧУ
МЕС.ТО

Н Е.ЛЬ.3.Я,

Y;f.E.

JАН.ЯТО

.J.
ОБЕ.а.

ТРЕ.НМ-

РО8КА

ЧАК

~/~

~
~

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

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

Если вдруг придет еще один друг, места опять не хватит, и вам всем при­

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

3

-

«бронирование мест»: даже если список состоит

задач, вы запрашиваете у компьютера место на

1О

позиций."

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

10

за­

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

Q

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

Q

Если в список будет добавлено более

10 задач,

перемещаться все равно

придется.

В общем, прием неплохой, но его нельзя назвать идеальным. Связанные

списки решают проблему добавления новых элементов.

Массивы и связанные списки

45

Связанные списки
При использовании связанного списка элементы могут размещаться где
угодно в памяти.

ЭТУ ПkMJITb

МС.ПОЛЬЗУЮТ ..апrм Е.

J
ОБЕЛ.

~

~~
~

~~
ТРЕН И-

PO&Kk

fi
~

Чk;_

В каждом элементе хранится адрес следующего элемента списка . Таким

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

ТРЕНМ­

Связанные адреса

РО&Кk

1.3

памяти

Все как в игре «Найди клад». Вы приходите по первому адресу, там написа­

но: «Следующий элемент находится по адресу

123». Вы идете по адресу 123,
847» и т. д. До­

там написано : «Следующий элемент находится по адресу

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

46

Глава

2.

Сортировка выбором

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

забит, и найти шесть соседних мест невозможно . Нечто похожее проис­

ходит и с массивами. Допустим, вы пытаетесь найти для массива блок на

1О

ООО элементов. В памяти можно найти место для

1О

ООО элементов, но

только не смежное. Для массива не хватает места! При хранении данных
в связанном списке вы фактически говорите: «Ладно, тогда садимся на

свободные места и смотрим кино». Если необходимое место есть в памяти,
вы сможете сохранить данные в связанном списке.

Если связанные списки так хорошо справляются со вставкой , то чем тогда

хороши массивы?

Массивы
На сайтах со всевозможными хит-парадами и «пер­
выми десятками» применяется жульническая такти­

ка для увеличения количества просмотров. Вместо

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

и заставляют вас нажимать кнопку

Next

для пере­

хода к следующему элементу. Например, «десятка

лучших злодеев в сериалах» не выводится на одной
странице. Вместо этого вы начинаете с №
и нажимаете

Next на

10

~ЛOJI.EKCKMK

f!;IExr)

кот

(Ньюман из «Сайнфелда»)

каждой странице, пока не доберетесь до №

1 (Густава

Фринг из «Во все тяжкие»). В результате сайту удается показать вам рекла­
му на целых

1О

страницах, но нажимать

Next 9

раз для перехода к первому

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

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

хранится. Вместо этого придется сначала обратиться к элементу №

нать адрес элемента №
элемента №

3".

1 и уз­
2, потом обратиться к элементу № 2 и узнать адрес

и так далее, пока не доберетесь до последнего элемента.

Связанные списки отлично подходят в тех ситуациях, когда данные долж-

Массивы и связанные списки

47

ны читаться последовательно: сначала вы читаете один элемент, по адресу

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

С массивами дело обстоит совершенно иначе. Работая с массивом, вы за­
ранее знаете адрес каждого его элемента. Допустим , массив содержит пять
элементов и вы знаете, что он начинается с адреса

00.

По какому адресу

хранится пятый элемент?

______
____
r
,
\
\
\ ()/\-;h ПJIТЫК
М~С.С.И6

MJ

ПJITM ЭЛЕ.МЕ.НТО6

____.)_ \..._..__

оо

о'1

02

~,

ОЗ

Простейшая математика дает ответ: это адрес

ЭЛЕ.МЕ.НТ

04.

Массивы прекрасно подхо­

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

позицию i-го элемента в памяти невозможно

- нужно обратиться к перво­

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

-

и так далее, пока вы не

доберетесь до i-го.

Терминология
Элементы массива пронумерованы , причем нумерация начинается с О , а не
с

1. Например,

в этом массиве знач ение

1
А значение

1О находится в позиции О.

20 находится

2

в позиции

1.

3

Неопытных программистов этот факт

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

48

Глава

2.

Сортировка выбором

упрощает написание кода по работе с массивами, поэтому программисты
остановились на этом варианте. Почти во всех языках программирования
нумерация элементов массива начинается с О. Вскоре вы к этому привык­
нете.

Позиция элемента называется его индексом. Таким образом, вместо того

чтобы говорить «Значение
«Значение

20

имеет

20 находится в позиции 1», правильно сказать
индекс 1». В этой книге термин «индекс» означает то

же, что и «ПОЗИЦИЯ».

Ниже приведены примеры времени выполнения основных операций с мас­
сивами и списками.

МКСИ&Ы

/

сnнск.н

ЧТЕНИЕ

ЬСП&КА

()Cn)

Q(.n)

= ~ИНЕКНОЕ

0 (.1.)

"' f\ОСТОЯННОЕ.

0(1)

&РЕМА

6 РЕ.МЯ

Вопрос: почему вставка элемента в массив требует времени О(п)? Предполо­
жим, вы хотите вставить элемент в начало массива. Как бы вы это сделали?

Сколько времени на это потребуется? Ответы на эти вопросы вы найдете
в следующем разделе!

Упражнения
2.1

Допустим, вы строите приложение для управления финансами.

1. П РО.П.УКТЫ
2.. ~ино
.3. ЬЕЛОСИПЕJlНЫК

КЛУБ

Упражнения

49

Ежедневно вы записываете все свои траты. В конце месяца вы анали­

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

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

-

массив или список?

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

0

OБE.JI.

0

TPEHllPO&KA

OБE.JI.

.....

Т'РЕ.НМ'РО&К~

,,, .. .,,,
.
.'Q
t""\

0 ЧAEПllТllE
' ' .
, ' ,
- 0 КУПИТЬ ЧА~ -.,,~,-..,.,"
#-. _._,....,:МJ

.

"'1'

(J

·""

Неупорядоченный

\

\

~

\('fПМТЬ 4~~ , _

"',,,,,,,,

D
'

ЧAEПllTllE

,' '

' "

.-

Упорядоченный

Что лучше подойдет для вставки элементов в середину: массивы или списки?
Со списком задача решается изменением указателя в предыдущем элементе.

ТРЕНМ­

РО&К~

1.3
ЧAli.

22

50

Глава

2.

Сортировка выбором

А при работе с массивом придется сдвигать вниз все остальные элементы.

---....
ОБЕ.а.

~

ТРЕНМ-

ЧАЕ-

РО&КА

ПИТИЕ

.~
~~

·~

&HMJ

~

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

Удаление
Что, если вы захотите удалить элемент? И снова список лучше подходит
для этой операции, потому что в нем достаточно изменить указатель в пре­

дыдущем элементе. В массиве при удалении элемента все последующие

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

подобных проблем не бывает.
Ниже приведены примеры времени выполнения основных операций с мас­
сивами и связанными списками.

МАС.С.И&ЬI

с.пис.ки

ЧТЕНИЕ

0(1)

Otn)

ЬСП&КА

0~)

Ou>

'j.Jl.AЛEHИE

Q(.t\)

0(1)

Упражнения

Заметим, что вставка и удаление выполняются за время

51

0(1) только в том

случае, если вы можете мгновенно получить доступ к удаляемому элементу.

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

0(1).
Какая структура данных используется чаще: массивы или списки? Очевидно,
это зависит от конкретного сценария использования. Массивы чрезвычайно
популярны из-за того, что они поддерживают произвольный доступ. Всего

существуют два вида доступа: произвольный и последовательный. При по­
следовательном доступе элементы читаются по одному, начиная с первого.

Связанные списки поддерживают только последовательный доступ. Если вы
захотите прочитать 10-й элемент связанного списка, вам придется прочитать
первые

9 элементов и перейти по ссылкам к

10-му элементу. Я часто говорю,

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

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

структур данных (о которых будет рассказано в книге далее).

Упражнения
2.2

Допустим, вы пишете приложение для приема заказов от посетителей

ресторана. Приложение должно хранить список заказов. Официанты

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

52

Глава

2.

Сортировка выбором

Какую структуру данных вы бы использовали для реализации этой
очереди: массив или связанный список? (Подсказка: связанные списки
хорошо подходят для вставки/удаления, а массивы

для произволь­

-

ного доступа к элементам. Что из этого понадобится в данном случае?)

2.3

Проведем мысленный эксперимент. Допустим,

Facebook

хранит

список имен пользователей. Когда кто-то пытается зайти на сайт

Facebook, система пытается найти имя пользователя.

Если имя входит

в список имен зарегистрированных пользователей, то вход разреша­

ется. Пользователи приходят на

Facebook достаточно

часто, поэтому

поиск по списку имен пользователей будет выполняться часто. Будем

считать, что Facebook использует бинарный поиск для поиска в спи­
ске. Бинарному поиску необходим произвольный доступ - алгоритм
должен мгновенно обратиться к среднему элементу текущей части
списка. Зная это обстоятельство, как бы вы реализовали список поль­
зователей: в виде массива или в виде связанного списка?

2.4

Пользователи также довольно часто создают новые учетные записи на

Предположим, вы решили использовать массив для хране­
ния списка пользователей. Какими недостатками обладает массив для
выполнения вставки? Допустим, вы используете бинарный поиск для

Facebook.

нахождения учетных данных. Что произойдет при добавлении новых
пользователей в массив?

2.5

В действительности

Facebook не использует ни массив, ни связанный

список для хранения информации о пользователях. Рассмотрим ги­

бридную структуру данных: массив связанных списков. Имеется мас­
сив из

26 элементов.

Каждый элемент содержит ссылку на связанный

список. Например, первый элемент массива указывает на связанный

список всех имен пользователей, начинающихся на букву «А». Второй
элемент указывает на связанный список всех имен пользователей, на­

чинающихся на букву «В», и т. д.
}

_

'\. С6язанн111ii сrшсок со 6семц цменамц

_ __..\_:з-r_ "" ~ мл1>зо6аw.tлей на бук8у «А»

~
МАСС.И&

Сортировка выбором

Предположим, пользователь с именем

4:Adit

53

в~ регистрируется на

Facebook и вы хотите добавить его в список. Вы обращаетесь к эле­
1 массива, находите связанный список элемента 1 и добавляете
«Adit в~ в конец списка. Теперь предположим, что зарегистрировать
нужно пользователя 4:Zakhir н~. Вы обращаетесь к элементу 26, ко ­
менту

торый содержит связанный список всех имен, начинающихся с «Z~,

и проверяете, присутствует ли

4:Zakhir н~

в этом списке.

Теперь сравните эту гибридную структуру данных с массивами и свя­

занными списками. Будет ли она быстрее или медленнее каждой ис­
ходной структуры при поиске и вставке? Приводить 4:0-большое~ не

нужно, просто выберите одно из двух: быстрее или медленнее.

Сортировка выбором
А теперь объединим все, что вы узнали, во вто­
ром алгоритме: сортировке выбором. Чтобы ос­
воить этот алгоритм, вы должны понимать, как

работают массивы и списки и «О-большое~.
Допустим, у вас на компьютере записана музы­
ка и для каждого исполнителя хранится счет­

чик воспроизведений.

-пRADIOHEAD
k'l.SHOP.E k'UMAP.
ТНЕ ЫАСk'

k'EY.S

NEUTML Mllk' HOTE:L

THI;

С:ЧЕТЧllК &ОС:-

ПPOllJ&EJl.EHllA

156

141
35
94-

Ьi;Ck'

~~

.SП.Ok'(;.s

61

\./ILCO

111

п

54

Глава

2.

Сортировка выбором

Вы хотите отсортировать список по убыванию счетчика воспроизведений,
чтобы самые любимые исполнители стояли на первых местах . Как это
сделать?

Одно из возможных решений

-

пройти по списку и найти исполнителя

с наибольшим количеством воспроизведений . Этот исполнитель добавля­
ется в новый список.

СЧЕТЧИК &ОС­

П РОИJ 11 EJl.EH М К

RADIOHEAD
Kl.SHOP.~

KUMi\P.

тн~ ЬLАСК K~Y.S

NEUTML MILK HOTEL
ЬЕСК
ТН ~

1.

У

156
141
35

1CПllCOK~

RADIOHEAD

СЧЕТЧИК

llOC-

ПPOИJllEJl.EHИK

156

~

94
9>S

.SТР.01{ ~.S

61

\llLCO

1\1

MDIOHHD
&CEro

2.• .D.OБ~&ЛJIEM
P.i\DIOHHD
& HO&t,!;_ СПИСОК

БОЛЬШЕ

&OCПPOllJ&E..й.EHll;__

Потом то же самое происходит со следующим по количеству воспроизве­
дений исполнителем .

СЧЕТЧИК &ОС­

\
l{[.SHOP.~

l{UMi\P.

тн~ ЫАСI{ l{~Y.S

N~UTP.i\L

MILI{

ПPOICJllEJl.EHMK

141
3S

HOT~L

Э.\-

Ь~СI{

ii

rспмсок ~

RADIOHEAD
l{UMAP.

l{\.SHOP.~

СЧЕТЧИК

llOC-

ПPOИJllEJl.EHИK

156

141

Сортировка выбором

55

Продолжая действовать так, мы получаем отсортированный список.

..

п~

!t.ADIOl-\EAD
Kl.Sl-\01\~

N~UTRAL

С:ЧЕ.ТЧМIС. &ОС-

ПPOMJ&EJlE.HИA

156

KUMAR

14-1

\./ILCO

111
94-

MILK

1-\0T~L

ЬЕСК
TI-\~ .STROK~.S
TI-\~ ЫАСК

KfY.S

~&

61

35

А теперь попробуем оценить происходящее с точки зрения теории вычис­
лений и посмотрим, сколько времени будут занимать операции. Напомним,
что время О(п) означает, что вы по одному разу обращаетесь к каждому
элементу списка. Например, прИ: простом поиске по списку исполнителей

каждый исполнитель будет проверен один раз.

1. RADIOHEAD
2.. KI.SHOP.E KUMAP.
3.

ТНЕ ЬLАСК

KEY.S

1'\

элеменW108

't. HEUTP.AL MILK HOTEL

5.

ЬЕСК

б. ТНЕ

STP.OKJ;;S

1-. \.JILCO

Чтобы найти исполнителя с наибольшим значением счетчика воспроиз­

ведения , необходимо проверить каждый элемент в списке. Как вы уже
видели, это делается за время О(п). Итак, имеется операция, выполняемая

за время О( п ), и ее необходимо выполнить п раз :

56

Глава

2.

Сортировка выбором

\. 11.ADIOHEAD
2.. Kl.SHOP.E KUMAP.

3. TI-\~ Ьli\Ck' k'~.S
't. N~UTP.i\L Mllk' HOT~L
5. ЬЕС.К
6. ТНЕ .STll.OKE.S
т.

4

'· Kl.SHOR~ k'UMi\R
2.. ТНЕ ЫАС.К KEY.S
3. NEUTP.AL MILK HOTEL
't. ЬЕС.К
5. TI-\~ .STP.Ok'~.S

\.

ТНЕ

.STP.OKE.S

6. 'WILCO

'WILC.O

'------v--

~
Q(Y\)

о(\'\)

'------~~---v--.;...-----~---/
t\

элеменмов

Все это требует времени О(п х п), или О(п 2 ).

Пример кода

57

Алгоритмы сортировки очень полезны. Например, теперь вы можете отсор­
тировать:

D имена в телефонной книге;
о даты путешествий;

D сообщения электронной почты (от новых к старым).
Алгоритм сортировки выбором легко объясняется, но медленно работает.
Быстрая сортировка

няется за время О(п

- эффективный алгоритм сортировки, который выпол­
log п). Но мы займемся этой темой в следующей главе!

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

def find Smallest(a r r):
smallest = arr[0]
С· · · ···
smallest_index = 0
с""""".
for i in range(l, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index

Дпя хранения наименьwеrо значения
Дпя хранения индекса наименьwеrо значения

Теперь на основе этой функции можно написать функцию сортировки вы­

бором:

def selectionSort(arr):
С·
newArr = []
for i in range(len(arr)):
smallest = indSmallest(arr) С·
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([S,

З,

6, 2, 10])

Сортирует массив

Находит наименьший эпемент в массиве

и добавnяет

ero в

новый массив

58

Глава

2.

Сортировка выбором

Шпаргалка
1:1 Память компьютера напоминает огромный шкаф с ящиками.
1:1 Если вам потребуется сохранить набор элементов, воспользуйтесь мас­
сивом или списком.

Q
Q

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

1:1 Массивы обеспечивают быстрое чтение.
1:1 Списки обеспечивают быструю вставку и выполнение.
Q

Все элементы массива должны быть однотипными (только целые числа,
только вещественные числа и т. д.).

3

Рекурсия

В этой главе

./

Вы узнаете, что такое рекурсия

-

метод программиро­

вания, используемый во многих алгоритмах. Эrо важная
концепция для понимания дальнейших глав книги .

./

Вы научитесь разбивать задачи на базовый и рекурсив­
ный случай. В стратегии «разделяй и властвуй» (гла­
ва

4) эта

простая концепция используется для решения

более сложных задач.

Эта глава мне самому очень нравится, потому что в ней рассматривается

рекурсия

-

элегантный метод решения задач. Рекурсия относится к числу

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

1:1

Глава содержит множество примеров кода. Самостоятельно выполните

этот код и посмотрите, как он работает.
о Мы будем рассматривать рекурсивные функции. Хотя бы один раз возь­
мите бумагу и карандаш и разберите, как работает рекурсивная функ­

ция: <1Так, я передаю функции factorial значение

5,

потом возвращаю

60

Глава З. Рекурсия

управление и передаю значение

4 функции factorial , которая".»

и т. д.

Такой разбор поможет вам понять, как работает рекурсивная функция .

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

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

Бабушка говорит, что ключ к чемодану, скорее всего, лежит в коробке .

'\_ БОЛЫIШI
КОРОБКА

Рекурсия

61

В коробке лежат другие коробки, а в них лежат маленькие коробочки. Ключ
находится где-то там. Какой алгоритм поиска ключа предложите вы? По­
думайте над алгоритмом, прежде чем продолжить чтение.
Одно из решений может выглядеть так:

с.ло~мть
КОРОБКИ

IKE.

6

КУЧУ

nок~ & КУЧЕ.
OC.ПIOTUI КОРОБКИ
ЬJ.ЯТЬ 11.0l'Olil\.Y

11

OTl\.l'Ь\Tb

1.

Сложить все коробки в кучу.

2.

Взять коробку и открыть.

3.

Если внутри лежит коробка, добавить ее в кучу для последующего по­
иска.

4.

Если внутри лежит ключ, поиск закончен!

5.

Повторить.

62

Глава

3.

Рекурсия

Есть и альтернативное решение.

!'\ 1'0& Е.1'1ПЬ

K~IJl.ЬI~

П1'ЕJl.МЕ.Т
& КО1'05КЕ.

ЕС.ЛМ &ЬI l\kUE.TE.

ЕС.ЛМ &ЬI

"~~•. nомс.к

н~UЕ.ТЕ.

JkKOHЧ Е.1\\

"ою&"'1-

1.

Просмотреть содержимое коробки.

2. Если вы найдете коробку, вернуться к шагу 1.
3.

Если вы найдете ключ, поиск закончен!

Какое решение кажется вам более простым? Первое решение можно постро­

ить на цикле while. Пока куча коробок не пуста, взять очередную коробку
и проверить ее содержимое :

def look_for_key(main_box) :
pile = main_box.make_a_pile_to_look_through()
while pile is not empty:
Ьох = pile . grab_a_box()
for item in Ьох:
if item.is_a_box():
pile.append(item)
elif item.is_a_key():
print "found the key!"
Второй способ основан на рекурсии. Рекурсией называется вызов функцией
самой себя. Второе решение на псевдокоде может выглядеть так:

def look_for_key(b ох):
for item in Ьох:
if item.is_a_box():
look_for_key(item)
--<·
elif item.is_a_key():
print "found the key!"

Рекурсия!

Базовый случай и рекурсивный случай

63

Оба решения делают одно и то же, но второе решение кажется мне более
понятным . Рекурсия применяется тогда, когда решение становится более

понятным. Применение рекурсии не ускоряет работу программы: более
того, решение с циклами иногда работает быстрее. Мне нравится одна ци­

тата Ли Колдуэлла с сайта

Stack Overlow:

~циклы могут ускорить работу

программы . Рекурсия может ускорить работу программиста. Выбирайте,
что важнее в вашей ситуации!~'
Рекурсия используется во многих нужных алгоритмах, поэтому важно по­
нимать эту концепцию .

Базовый случай
u

u

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

да обратного отсчета:
\

> 3 .•. 2 .•• 1
Ее можно записать в рекурсивном виде:

def countdown(i):
print i
countdow n(i-1)
Введите этот код и выполните его. И тут возникает проблема: эта функция
выполняется бесконечно!

p\!,\Mi i

&Ьl.3&НЬ c.ouмiDO"'"
.пл.я i - '

' http:j/stac koverlow.coш/a/72694 / 139117

Бесконечный
цикл

64

>

Глава з. Рекурсия

з

... 2 •.• 1 ••• 0 ••• -1 •. • -2 •••

Чтобы прервать выполнение сценария, нажмите

Ctrl+C.

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

функция состоит из двух частей: базового случая и рекурсивного случая.

В рекурсивном случае функция вызывает сама себя. В базовом случае
функция себя не вызывает" . чтобы предотвратить зацикливание.

Добавим базовый случай в функцию countdown:

def countdown(i):

print i
if i

<= 0:

Базовый случай

....

return
else :
--<· ·· ······
countdow n(i-1)

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

Теперь функция работает так, как было задумано. Это выглядит примерно
так:

Е.С.ЛМ

i <•'

l'А50П

JАКОНЧЕ.НА

t
БAJO&f:)\K
С.ЛУЧАК

& ПPOTll&llOM СЛУЧАЕ.&~­

J&АТЬ c.ouмTDO\.IM .n.ЛJ\

t

PEKYl'C.M&HЬIK
С.ЛУЧАК

1

- '

Стек

65

Стек
В этом разделе рассматривается стек вызовов. Концепция стека вызовов

играет важную роль в программировании вообще; кроме того, ее важно по­
нимать при использовании рекурсии.

Предположим, вы устраиваете вечеринку с барбекю. Вы составляете спи­
сок задач и записываете дела на листках.

Помните, когда мы рассматривали массивы и списки, у вас

-<~

тоже был список задач? Задачи, то есть элементы списка,
можно было добавлять и удалять в произвольных пози­
циях списка. Стопка листков работает куда проще. Новые

(вставленные) элементы добавляются в начало списка,
то есть на верх стопки . Читается только верхний элемент, и он исключается

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

~А НЕСЕНИЕ
(НО6ЫК ЭЛЕМЕНТ

ИJВЛЕЧЕНИЕ
(6ЕРХНИК ЭЛЕМЕНТ

.дОБА6ЛЯЕТU

&Ы&о.а.итu из с.топки

НА 6ЕРХ СТОПКИ)

И ЧИПЕТСJI)

Посмотрим, как работает список задач:

~WЧА
КУПИТЬ
Е..а.У

3А.а.АЧА
И.3 &ЛЕКА E.ТCJI

И.3 С.ТОПКИ

f.\A

ЛИС.ТКЕ НАПМС.АНО:
«!(УПИТЬ Е.дУ-..

IOJllO

КУПИТЬ

БУЛОЧКИ, БYJ>rEl'bl

И ТОРТ

66

Глава

3.

Рекурсия

Такая структура данных называется стеком. Стек

-

простая структура дан­

ных. А теперь самое неожиданное: все это время вы пользовались стеком,

не подозревая об этом!

Стек вызовов
Во внутренней работе вашего компьютера используется стек, называемый
стеком вызовов. Давайте посмотрим , как он работает. Предположим, име­
ется простая функция :

def greet(name):
print "hello, " + name + "!"
greet2(name)
print "getting ready to say Ьуе ... "
Ьуе()

Эта функция приветствует вас, после чего вызывает две другие функции.
Вот эти две функции :

def greet2(name):
print "how are you, " + name + "?"
def Ьуе():
print "ok Ьуе!"
Разберемся, что происходит при вызове функции.

r----------- ----------------------- - - --- ------,
ПРИМЕЧАНИЕ

В языке Python print тоже является функцией. Чтобы не усложнять пример,
мы сделаем вид, что этой функции нет. Просто подыграйте нам.
L------- ---- - ---------------------------------~

Предположим, в программе используется вызов greet ( "maggie"). Сначала

ваш компьютер выделяет блок памяти для этого вызова функции.

L_

__..~

стек

Затем эта память используется. Переменной

67

name присваивается значение

"maggie"; оно должно быть сохранено в памяти.
,/

МАМЕ:

1 MAGGIE

11

Каждый раз , когда вы вызываете функцию , компьютер сохраняет в памяти
значения всех переменных для этого вызова. Далее выводится приветствие

hello, maggie ! , после чего

следует второй вызов

greet2( "maggie" ).

И снова

компьютер выделяет блок памяти для вызова функции.
TE.KYIJ1ИI\
6ЫJО6

ФУНКЦИИ

Ваш компьютер объединяет эти блоки в стек. Второй блок создается над
первым. Вы выводите сообщение

how are you, maggie?, после чего воз­

вращаете управление из вызова функции. Когда это происходит, блок на
вершине стека извлекается из него .

Теперь верхний блок в стеке относится к функции greet; это означает, что
вы вернулись к функции

greet. При вызове функции greet2 функция greet

еще не была завершена. Здесь-то и скрывается истинный смысл этого раз­
дела: когда вы вызываете функцию из другой функции, вызывающая функция

68

Глава

3.

Рекурсия

приостанавливается в частичоо завершеноом состоянии. Все значения пере­
менных этой функции остаются в памяти. А когда выполнение функции

greet2 будет завершено, вы вернетесь к функции greet и продолжите ее
выполнение с того места, где оно прервалось. Сначала выводится сообщение

getting ready to say Ьуе ... , после чего вызывается функция Ьуе.

"

I

ЬУЕ
ьР.ЕЕi
МАМ!;~

1 MAGGIE

11

Блок для этой функции добавляется на вершину стека. Далее выводится
сообщение ok Ьуе ! с выходом из вызова функции.

МАМЕ:

MAGGIE

Управление снова возвращается функции greet. Делать больше нечего, так
что управление возвращается и из функции

greet. Этот стек, в котором со­

хранялись переменные разных функций, называется стеком вызовов.

Упражнения
3.1

Предположим, имеется стек вызовов следующего вида:

<;~ЕЕТ

NA

Упражнения

69

Что можно сказать о текущем состоянии программы на основании этого
стека вызовов?

А теперь посмотрим , как работает стек вызовов с рекурсивными функ­
циями.

Стек вызовов с рекурсией
Рекурсивные функции тоже используют стек вызовов! Посмотрим, как это
делается , на примере функции вычисления факториала. Вызов

factorial(S)

записывается в виде

=

и определяется следующим образом:

5!

По тому же принципу factorial(З) соответствует

5!

5*4*3*2*1.
3*2*1. Рекурсивная функ­

ция для вычисления факториала числа выглядит так:

def fact(x):
if

х ==

1:

return 1
else:
return х * fact(x-1)
В программу включается вызов fact(З). Проанализируем этот вызов
строку за строкой и посмотрим, как изменяется стек вызовов . Стоит на­

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

ко.а.

СП.К 6ЬIJ0606

nEP6ЬI~

fac.t(.Э)

--- -- - - - - - - - - - - - -- -if .}( - -1:

-- - - - - - - - - - - - - - - - - - - - - ~
eLse=
~
-__ __
-- - - - - - ----- - - - - - ;

РЕ.КУРСМ6НЬ11\
6ЬIJ061

retvrn Х * factC.X-1)
~

l'"Ac:1'
)( 1 2
(дG"f

х\3

6bl306 Fi\CT.
"!.. РА6НО 3

~НАЧЕ.НМЕ.

Глава

70

3.

Рекурсия

Fдс:-т

С.Еli.ЧМ: TEKYU1MM
С.ПЛ IПOPOli. &ЫJО&
~НАЧЕНИЕ

Ft\C.T.
РА&НО

х

ЬEPXHMll. &ЫЗО& ФУНК-

t- UMM - ТОТ, KOTOPblli.
6 .П.АННЬ\11. МОМЕНТ
Я&ЛЯЕТС.Я TEKYU1MM

/ z.

f"c.,-

'/..

2.

. -- - - - -

Х

-

/ З

-- - -- - - - - - - - - - -

-

F"ct'
)< 1 2.
l'"Acr

else:

.)(' -, 3

-

-FA C'f' -

-

)1

retvгn х-* faci.(x-1)

Ь ОБОИХ &ЫJО&АХ СУЩЕ­
~ С.Т&УП ПЕРЕМЕННАЯ
С. ИМЕНЕМ
!<:"ИМЕЕТ

_

11

FAC.1'

х 1 2.
f' .... c."'f

х

6

1..,

КОТОРАЯ

ЭТИХ 6Ь\ЗО6АХ

РАЗНЫЕ ЗНАЧЕНИЯ

'-.

ОБРНМТЬС.Я К ЗНАЧЕ­

НИЮ

1' зтоrо &ЫJО&А

....--ВНУТРИ ЭТОГО 6ЬIЗО6А

HE&OJMO~HO

-

М НА­

ОБОРОТ

1s

f ACJ'

)( 1 1
FACI

jf Х= · 1:

')(

' l

fl\.C."f
'J(

1 '3

__... "------- - - - -- - -- - ---oro,

зто У~Е ТРЕ­

ИJ С.ТЕ.КА; ЗТО ОJНАЧА­

тиli. 6ЫJО6 - ПРИ­
ЧЕМ ни о.а.ин &ЫJО&

.а.о С.ИХ ПОР ПК

nEP&blli. БЛОК, КОТО\Грыll. БУДЕТ МJ&ЛЕЧ ЕН
ЕТ, ЧТО ИМЕННО ЭТОТ

&ЫJО& ПЕР&ЫМ &ЕРНЕТ
УПРА&ЛЕНИЕ

ЬО.36РАЩАЕ.Т'

М НЕ JА&ЕРОIИЛС.Я\

~ MJ6PA\llAEТ 1
ЬЫJО& ФУНКЦИИ,

ТОЛЬКО ЧТО &ЕР- ~
HY&lllMll. УПРА&ЛЕНМЕ

~НАЧЕНИЕ '/.. РА&НО 2.

tet"Ur-n -х."

~ ЬО.36РАЩАЕТ

f aGt(?(-1)

2.

_/

.retvr.._ х i: f act6t-1)
J(\!.3_/

r

этот 6Ь\ЗО6

&ЕРНУЛ

2.

~
~

~ ЬО.36РА\JlАЕТ 6

Упражнения

71

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

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

сло~кть
6С.Е КОРОБКИ

6

КУЧУ

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

С.ЛЕ.П.УIОU1АЯ КОРОБКА,

6 КОТОРО~ 6ЬI БУДЕТЕ
ИСКАТЬ КЛIОЧ

....,

'---~------~~---~~--IС УЧ А КОРОБОК

Но в рекурсивном решении никакой кучи не существует.

72

Глава

3.

Рекурсия

li'PO&E.'PllTb

К,_"11.ЬI~
ntEJIJAE.Т
& КО'РО!>КЕ.

EC.Лll &ЬI

EC.Лll &ЬI H,_UE.TE.

1t"UE.TE.
tOIOilN-

.3,_КОНЧ Е.Н\

'"' °"· помс.к

Если кучи нет, то как ваш алгоритм узнает, в каких коробках еще нужно
искать? Пример:

ЬЫ ПРОВЕРЯЕТЕ

ЬНУТРИ ОБНдРУl-И6дЮТСЯ

КОРОБКУ д

КОРОБКИ В И С

ЬЫ ПРОВЕРЯЕТЕ

КОРОБКУ В

ЬЫ ПРОВЕРЯЕТЕ
КОРОБКУ

D

Ь НЕ~ ЛЕl-ИТ
КОРОБКд

D

ОНд ПУСП

Упражнения

73

К этому моменту стек вызовов выглядит примерно так:

J:8

КОРОБКИ, КОТОРЫЕ

ЩЕ НУ~но ПРО&ЕРИТЬ

-----:,;~ \
(30)(

D /-

.

1

1

'
\

I
Вс.>Х А 1, "_,,,
g_I ,'

Во){ В

«Куча коробок~ хранится в стеке! Это стек незавершенных вызовов функ­

ции, каждый из которых ведет собственный незаконченный список коробок

для поиска. Стек в данном случае особенно удобен, потому что вам не нуж­
но отслеживать коробки самостоятельно

-

стек делает это за вас.

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

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

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

Упражнения
3.2

Предположим, вы случайно написали рекурсивную функцию, которая

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

со стеком при бесконечном выполнении рекурсии?

74

Глава

3.

Рекурсия

Шпаргалка
о Когда функция вызывает саму себя, это
называется рекурсией.
о В каждой рекурсивной функции должно

быть два случая: базовый и рекурсивный .
о Стек поддерживает две операции: зане ­
сение и извлечение элементов.

о Все вызовы функций сохраняются в сте­
ке вызовов.

о Если стек вызовов станет очень большим, он займет слишком много
памяти.

4

Быстрая сортировка

В этой главе

./ Вы узнаете о стратегии «разделяй и властвуй». Слу­
чается так, что задача, над которой вы трудитесь,
не решается ни одним из известных вам алгоритмов.

Столкнувшись с такой задачей, хороший программист

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

шения. «Разделяй и властвуй»

-

первая общая стра­

тегия, с которой вы познакомитесь .

./

Далее рассматривается быстрая сортировка

-

эле­

гантный алгоритм сортировки, часто применяемый на

практике. Алгоритм быстрой сортировки использует
стратегию «разделяй и властвуй».

Предыдущая глава была посвящена рекурсии. В этой главе вы воспользу­
етесь новыми знаниями для решения практических задач. Мы исследуем
принцип ~разделяй и властвуй>,>, хорошо известный рекурсивный метод
решения задач.

В этой главе мы постепенно добираемся до полноценных алгоритмов.

В конце концов, алгоритм не особенно полезен, если он способен решать

задачу только одного типа,

-

~разделяй и властвуй~ помогает выработать

новый подход к решению задач. Это всего лишь еще один инструмент в ва-

76

Глава

4.

Быстрая сортировка

шем арсенале. Столкнувшись с новой задачей, не впадайте в ступор. Вместо

этого спросите себя: «А нельзя ли решить эту задачу, применив стратегию
"разделяй и властвуй"?~
К концу этой главы вы освоите свой первый серьезный алгоритм «разделяй

и властвуй~: быструю сортировку. Этот алгоритм сортировки работает на­

много быстрее сортировки выбором (о которой рассказывалось в главе

2).

Он является хорошим примером элегантного кода.

«Разделяй и властвуй»
Возможно, вы не сразу поймете суть стра­
тегии «разделяй и властвуй~, поэтому

мы рассмотрим три примера. Сначала
я приведу наглядный пример. Потом мы

разберем пример кода, который выгля­
дит не так красиво, но, пожалуй, вос­
принимается проще. В завершение будет
рассмотрена быстрая сортировка

-

алгоритм

сортировки, использующий стратегию «разделяй
и властвуй~.
Представьте, что вы фермер, владеющий земельным участком.

1&60

м

:·.~;·1 ',~ ~•'''•'')·"·' 1) , •• " . ' ,,1' ''• 1 l'•'i
1
11\1, :,,".'''(1 ~.'1•;.', 1 •••• ,·: 1,,•••••••
,\ 1•,
;,,,,,, ~111,,

1,,,,, ., .• ,··f'''. 1,•,,
'•(''''1.•
•1·1/'•·
······'''••''''''
J~J.
1'1•''''
.,.,,1··~'·'"···· ·'•
11 1,1•'',•i,, ,, ,, '.':' 1 .:~·.' r;., ·,•'1:1
,,1,,,J,,,•
'1/ i ,., ,, ·' ,", •,,•,, '••','.
,,,,, 1 1'. 1 ,1 1 . ' ' • J •,, •• ·~.~~·~'.•,'•,'
1/ i •); ~ J, 1 ' ' . , , ''t •',, • , '.. 1 ••• , .,
/

6110

м

' / '., '/ \ \ , \ '',, ·,· ' • ,, •• • 1,,,'
.~ :~:·.· ,< •.
1
'1
'
"' " ,.1,,,,,,,,,.,.,•,'
1 '
' /
, • , '
1_,•1 " / { ,• , , ' '•'•»•'

1,, , '.,. \. , ••.• \ ,,'\'•\·,•"',
l••J, 1 ~"' •' •/ ••• •"' ,,'
1 ,'\·,• ••, ••, , , , ,

",,

Вы хотите равномерно разделить землю на одинаковые квадратные участ­

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

«Разделяй и властвуй»

77

-

ЬС.Е УЧАСТКИ

с.лишком

НЕ К6АдРПНЬ\Е

.а.омны Быть

МАЛЕНЬКИЕ

ОJI.ИНАКО6Ь\МИ

Как определить наибольший размер квадрата для участка? Воспользуйтесь
стратегией «разделяй и властвуй~! Алгоритмы на базе этой стратегии яв­
ляются рекурсивными.

Решение задачи методом «разделяй и властвуй ~ состоит из двух шагов:

1.

Сначала определяется базовый случай. Это должен быть простейший
случай из всех возможных.

2.

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

А теперь воспользуемся стратегией «разделяй и властвуй~ для поиска ре­

шения этой задачи. Каков самый большой размер квадрата, который может
использоваться?

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

-

если длина одной стороны кратна длине другой стороны .

50

м

2.5

")
г----~--'1'·''1 •1'

м

, . , •• , , ' ' • ' i

~·,•.·.:·:.••,,•: .'11: ;" ~,'·'
•• ~· ' \ ••• , , ,' : ' 1 ' ; • '• ' ~:
,, '' • ~ ',' '• '" '/' ~ •'• ,''' 't'
•'••,':•.•, ~. •,,:•\ ', '''•'

.:, '' ' '', , ''
/

\

\

;

"..

2.5

::

м

,~,

Предположим , длина одной стороны составляет

25 м,

а длина другой

В этом случае размер самого большого участка составляет
дел после деления будет состоять из двух участков .

25 м

х

25 м,

50

м.

и на­

78

Глава

4.

Быстрая сортировка

Теперь нужно вычислить рекурсивный случай. Здесь-то вам на помощь
и приходит стратегия «разделяй и властвуй ~ . В соответствии с ней при
каждом рекурсивном вызове задача должна сокращаться. Как сократить

эту задачу? Для начала разметим самые большие участки, которые можно
использовать.

НЕ.РКПРЕ.­

.О.6А

.ll.Е.ЛЕ.ННЫК

УЧАСТК~

ОС.ТАТОК

????

~

..... ___
_..J---..--"

..._______,

С.........-- т.-

&ltO М

&ltO м

1100 м

В исходном наделе можно разместить два участка

место. Тут-то и наступает момент истины .

640 х 640, и еще останется
Нераспределенный остаток - это

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

6lt0

ltOO

м

м

НО6ЫК НUЕ.Л, КОТОРЫК ТО#.Е.
НУ~но РАЗБИТЬ НА УЧАСТКИ

Итак, мы начали с надела

1680

х

640,

который необходимо разделить на

участки. Но теперь разделить нужно меньший сегмент

- 640

х

400.

Если

«Разделяй и властвуй»

79

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

что сократили задачу с размера

х

1680

640 до 640

х

400!

Применим тот же алгоритм снова. Если начать

с участка

640

х

400,

то размеры самого большого

квадрата, который можно создать, составляют

400

х

400

м.

'---v--'

400

м

Остается меньший сегмент с размерами

400

х

240 м .

., ••':'' :..., ,•,}
\ .,'

•

1

....

'

~

• •''
' ' " \ ''•
\ •• , ' •• 1 ... \ '· 1

•• '

..

' ·, ''.....• 1' \,'
' • •, , •, '•''"
,•,

'.\''1\••''''

~
'tOO м

2.'tO м

80

Глава

4.

Быстрая сортировка

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

240

Х

160 М.

После очередного отсечения получается еще меньший сегмент.

с.:J!Мм

fR}\бOM

~

~
\бО м

БАJО6ЬIК СЛУЧАК\

Эге, да мы пришли к базовому случаю:

160

кратно

80.

Если разбить этот

сегмент на квадраты, ничего лишнего не останется!

'

/

1

1

О~Jмм J~
~ ._,..,..J
~Ом

с!Ю м

/

Итак, для исходного надела земли самый большой размер участка будет
равен

80

х

80

м.

«Разделяй и властвуй»

81

Вспомните, как работает стратегия ~разделяй и властвуй•:

1.

Определите простейший случай как базовый.

2.

Придумайте, как свести задачу к базовому случаю.

«Разделяй и властвуй~

-

не простой алгоритм, который можно применить

для решения задачи. Скорее, это подход к решению задачи. Рассмотрим
еще один пример.

[2f 4 [6 /

Имеется массив чисел.

Нужно просуммировать все числа и вернуть сумму. Сделать это в цикле
совсем не сложно:

def sum(arr):
total = 0
for х in arr:
total += х
return total
print sum{[l, 2,

з,

4])

Но как сделать то же самое с использованием рекурсивной функции?

Шаr 1: определить базовый случай. Как выглядит самый простой массив,
который вы можете получить? Подумайте, как должен выглядеть про­

стейший случай, и продолжайте читать. Если у вас будет массив с О или

1 элементом, он суммируется достаточно просто.

82

Глава

4.

Быстрая сортировка

БА.30ВЫ~
С.ЛУЧАР~

LJ

О ЭЛЕМЕНТОВ =СУММА 'РА&НА О

[1]

'

ЭЛЕМЕНТ

= С.УММА 'РАВНА т

Итак, с базовым случаем мы определились.
Шаr

2: каждый рекурсивный

вызов должен приближать вас к пустому мас­

сиву. Как уменьшить размер задачи? Один из возможных способов:

- 12
:::.

В любом случае результат равен

12.

2+1Ф

:12

Но во второй версии функции

sum

передается меньший массив. А это означает, что вы сократил и размер своей

задачи!

Функция

sum может работать

по следующей схеме:

ПОЛУЧИТЬ

список

"l
Если сnисок

ПУСТ, 6Е'РНУТЬ О

~

Ь П'РОТИ&НОМ СЛУЧАЕ 'РЕЗУЛЬ-

пт 'РА6ЕН СУММЕ ПЕ'Р6Оrо
ЧИСЛА

6

СПИСКЕ И СУММЫ

оспльноrо сnискА

«Разделяй и властвуй»

А вот как это выглядит в действии.

РЕJУЛЬПТ

oJ

Вспомните, что при рекурсии сохраняется состояние.

1-\М

OJl.MH

М.3 ЗТМХ

6Ы.30606 ФУНКЦИИ НЕ.

ЬСПОМНМТЕ, ЧТО РЕ.КУРСМА

.3А6ЕРmмтu .а.о тоrо,

СОХРАНАЕТ СОСТОАНМЕ ЗTllX

КАК БУЛ.Е.Т ОБНАРУJ!\.Е.Н

ЧАСТИЧНО .3k6E.POIE.HHЫX

БАJО6Ь\К СЛУЧАК\

6Ы.30606 ФYHIЩllll

\sи"'Чll4\6 D

\

l

2+ sum(CillJ)
4+ sum(IO)
J
БА.306ЫК СЛУЧАК\

Т1Е.Р6ЫК 6Ы.306 ФУНКЦИИ,
КОТОРЫК БУДЕТ РЕАЛЬНО

JA6E.POIE.H

Suм(@)

t '

1+ 1~ =-12

j,

~

.,
:,12 ,_

=6.

t
4-+6 =1Ф

_)'

83

84

Глава

4.

Быстрая сортировка

СОВЕТ

Когда вы пишете рекурсивную функцию, в которой задействован массив, ба­
зовым случаем часто оказывается пустой массив или массив из одного эле­

мента. Если вы не знаете, с чего начать,

-

начните с этого.

~----- ----- ------------------------------- ----~
ПАРА СЛОВ О ФУНКЦИОНАЛЬНОМ ПРОГРАММИРОВАНИИ

Зачем применять рекурсию, если задача легко решается с циклом?
Вполне резонный вопрос. Что ж, пора познакомиться с функцио­

нальным программированием!

В языках функционального программирования, таких как

Haskell ,

циклов нет, поэтому для написания подобных функций приходит­
ся применять рекурсию. Если вы хорошо понимаете рекурсию, вам

будет проще изучать функциональные языки. Например, вот как вы­
глядит функция

surn на языке Haskell:

sum [] = 0
" ""." ."" .. " ." .... ...."" "" .. ..... ..... .
sum (x:xs) = х + (sum xs)
" ""." """"" .

Базовый случай
Рекурсивный случай

На первый взгляд кажется, что одна функция имеет два определе­

ния. Первое определение выполняется для базового случая, а вто­
рое

- для рекурсивного случая . Функцию также
Haskell с использованием команды if:

можно записать на

sum arr = if arr == []
then 0
else (head arr) + (sum (tail arr))
Но первое определение проще читается. Так как рекурсия широко

применяется в языке

Haskell, в

него включены всевозможные удоб­

ства для ее использования. Если вам нравится рекурсия или вы хо­

тите изучить новый язык

-

присмотритесь к

Haskell.

Быстрая сортировка

85

Упражнения
4.1
4.2

Напишите код для функции

sum (см. выше).

Напишите рекурсивную функцию для подсчета
элементов в списке.

4.3

Найдите наибольшее число в списке.

4.4

Помните бинарный поиск из главы

1?

Он тоже

относится к классу алгоритмов •разделяй и властвуй•. Сможете ли вы

определить базовый и рекурсивный случай для бинарного поиска?

Быстрая сортировка
Быстрая сортировка относится к алгоритмам сортиров­

ки. Она работает намного быстрее сортировки выбором
и часто применяется в реальных программах. Например,

в стандартную библиотеку С входит функция с име­
нем

qsort, реализующая быструю сортировку.

Быстрая

сортировка также основана на стратегии ~разделяй
и властвуй•.

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

(помните подсказку из предыдущего раздела)? Не­

которые массивы вообще не нуждаются в сорти­
ровке.

СОРТМРО&АТЬ
ПКМЕ

MACCll&bl

НЕ нv.~но

[

]

~ ПУСТО~ MACCll&

(20 \ ~

MKCll&

С OJUlllM ЭЛЕМЕНТОМ

86

Глава

4.

Быстрая сортировка

Пустые массивы и массивы, содержащие всего один элемент, станут базо­
вым случаем. Такие массивы можно просто возвращать в исходном виде

-

сортировать ничего не нужно:

def quick sor t(array):
if len(array) < 2:
return array
Теперь перейдем к массивам большего размера. Массив из двух элементов
тоже сортируется без особых проблем.

~ СР~6НИ6~ЕМ Л.6~ ЭЛЕМЕНП.

ЕСЛИ ПЕР&ЫК ЭЛЕМЕНТ МЕНЬШЕ
&ТОРоrо, МЕНЯЕМ И)( МЕСПМИ

А как насчет массива из трех элементов?

\зз lts (1Ф \
Помните: мы используем стратегию «разделяй и властвуй» . Следователь­

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

~
ОПОРНЫК
ЭЛЕМЕНТ

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

Теперь мы находим элементы, меньшие опорного, и элементы, большие
опорного.

Быстрая сортировка

ЧИСЛА,

ЧИСЛА, БОЛЬ/КИЕ.

ME.Hbll!ME. 33

(ПУСТОК М~ССМ&)

87

33

[ts \1Ф-\ ~ l.s]
f

ОПОРНЬIК
ЭЛЕ.МЕ.НТ

Этот процесс называется разделением. Теперь у вас имеются :

1:1

подмассив всех элементов, меньших опорного;

о опорный элемент;

о подмассив всех элементов, больших опорного.
Два подмассива не отсортированы

они просто выделены из исходного

-

массива. Но если бы они бъuiu отсортированы, то провести сортировку всего
массива было бы несложно.

Если бы подмассивы были отсортированы, то их можно было бы объеди­
нить в порядке ~левый подмассив

-

опорный элемент

-

правый подмас­

сив» и получить отсортированный массив . В нашем примере получается

[ 10, 15] + [ 33] + [] =

[ 10, 15,

33],

то есть отсортированный массив.

Как отсортировать подмассивы? Базовый случай быстрой сортировки
уже знает, как сортировать массивы из двух элементов (левый подмассив)

и пустые массивы (правый подмассив). Следовательно, если применить

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

quicksort([lS, 10]) + [33) + quicksort([])
> [ 10, 15, 33]

.,.."

Отсортированный массив

88

Глава

4.

Быстрая сортировка

Этот метод работает при любом опорном элементе. Допустим, вместо
в качестве опорного был выбран элемент

33

15.

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

элементов. Это делается так:

1.

Выбрать опорный элемент.

2.

Разделить массив на два подмассива: элементы, меньшие опорного,

и элементы, большие опорного.

3.

Рекурсивно применить быструю сортировку к двум подмассивам.

Как насчет массива из четырех элементов?

[3? \ 10 J 1s

l1]

Предположим, опорным снова выбирается элемент

см

/

33.

l <%> [ J

1!; 1 ]

Левый подмассив состоит из трех элементов. Вы уже знаете, как со