Untitled
Untitled
ПОСТРОЕНИЕ И АНАЛИЗ
ВТОРОЕ ИЗДАНИЕ
Стр. 1
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
INTRODUCTION TO
ALGORITHMS
SECOND EDITION
Стр. 2
Томас Кормен
Чарльз Лейзерсон
Рональд Ривест
Клиффорд Штайн
АЛГОРИТМЫ
ПОСТРОЕНИЕ И АНАЛИЗ
ВТОР ОЕ ИЗДАНИЕ
Стр. 3
ББК 32.973.26-018.2.75
В24
УДК 681.3.07
Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн,
Клиффорд.
В24 Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. — М. :
Издательский дом “Вильямс”, 2011. — 1296 с. : ил. — Парал. тит. англ.
ISBN 978-5–8459–0857–5 (рус.)
Фундаментальный труд известных специалистов в области кибернетики досто-
ин занять место на полке любого человека, чья деятельность так или иначе связана
с информатикой и алгоритмами. Для профессионала эта книга может служить на-
стольным справочником, для преподавателя — пособием для подготовки к лекциям
и источником интересных нетривиальных задач, для студентов и аспирантов —
отличным учебником. Каждый может найти в ней именно тот материал, который
касается интересующей его темы, и изложенный именно с тем уровнем сложности
и строгости, который требуется читателю.
Описание алгоритмов на естественном языке дополняется псевдокодом, который
позволяет любому имеющему хотя бы начальные знания и опыт программирова-
ния, реализовать алгоритм на используемом им языке программирования. Строгий
математический анализ и обилие теорем сопровождаются большим количеством
иллюстраций, элементарными рассуждениями и простыми приближенными оцен-
ками. Широта охвата материала и степень строгости его изложения дают основания
считать эту книгу одной из лучших книг, посвященных разработке и анализу алго-
ритмов.
ББК 32.973.26–018.2.75
Все названия программных продуктов являются зарегистрированными торговыми марками
соответствующих фирм.
Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой
бы то ни было форме и какими бы то ни было средствами, будь то электронные или механиче-
ские, включая фотокопирование и запись на магнитный носитель, если на это нет письменного
разрешения издательства MIT Press.
Стр. 4
ОГЛАВЛЕНИЕ
Введение 30
Часть I. Основы 43
Глава 1. Роль алгоритмов в вычислениях 46
Глава 2. Приступаем к изучению 57
Глава 3. Рост функций 87
Глава 4. Рекуррентные соотношения 109
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 140
Часть II. Сортировка и порядковая статистика 173
Глава 6. Пирамидальная сортировка 178
Глава 7. Быстрая сортировка 198
Глава 8. Сортировка за линейное время 220
Глава 9. Медианы и порядковые статистики 240
Часть III. Структуры данных 255
Глава 10. Элементарные структуры данных 260
Глава 11. Хеш-таблицы 282
Глава 12. Бинарные деревья поиска 316
Глава 13. Красно-черные деревья 336
Глава 14. Расширение структур данных 365
Часть IV. Усовершенствованные методы разработки и анализа 383
Глава 15. Динамическое программирование 386
Глава 16. Жадные алгоритмы 442
Глава 17. Амортизационный анализ 482
Часть V. Сложные структуры данных 511
Глава 18. B-деревья 515
Глава 19. Биномиальные пирамиды 537
Стр. 5
6 Оглавление
Стр. 6
СОДЕРЖАНИЕ
Введение 30
Часть I. Основы 43
Введение 44
Глава 1. Роль алгоритмов в вычислениях 46
1.1 Алгоритмы 46
Какие задачи решаются с помощью алгоритмов? 47
Структуры данных 50
Методические указания 50
Сложные задачи 51
Упражнения 52
1.2 Алгоритмы как технология 52
Эффективность 52
Алгоритмы и другие технологии 54
Упражнения 55
Задачи 55
Заключительные замечания 56
Глава 2. Приступаем к изучению 57
2.1 Сортировка вставкой 57
Инварианты цикла и корректность сортировки вставкой 59
Соглашения, принятые при составлении псевдокода 61
Упражнения 63
2.2 Анализ алгоритмов 64
Анализ алгоритма, работающего по методу вставок 66
Стр. 7
8 Содержание
Стр. 8
Содержание 9
Стр. 9
10 Содержание
Стр. 10
Содержание 11
Стр. 11
12 Содержание
Стр. 12
Содержание 13
Удаление 325
Упражнения 327
12.4 Случайное построение бинарных деревьев поиска 328
Упражнения 331
Задачи 332
Заключительные замечания 335
Глава 13. Красно-черные деревья 336
13.1 Свойства красно-черных деревьев 336
Упражнения 339
13.2 Повороты 340
Упражнения 341
13.3 Вставка 342
Анализ 350
Упражнения 350
13.4 Удаление 351
Анализ 356
Упражнения 356
Задачи 357
Заключительные замечания 364
Глава 14. Расширение структур данных 365
14.1 Динамические порядковые статистики 366
Выборка элемента с заданным рангом 367
Определение ранга элемента 368
Поддержка размера поддеревьев 369
Упражнения 371
14.2 Расширение структур данных 372
Расширение красно-черных деревьев 373
Упражнения 374
14.3 Деревья отрезков 375
Упражнения 380
Задачи 381
Заключительные замечания 382
Стр. 13
14 Содержание
Стр. 14
Содержание 15
Стр. 15
16 Содержание
Упражнения 504
Задачи 505
Заключительные замечания 510
Стр. 16
Содержание 17
Стр. 17
18 Содержание
Стр. 18
Содержание 19
Циклы 667
Представление кратчайших путей 668
Ослабление 669
Свойства кратчайших путей и ослабления 671
Краткое содержание главы 672
24.1 Алгоритм Беллмана-Форда 672
Упражнения 676
24.2 Кратчайшие пути из одной вершины в ориентированных
ациклических графах 677
Упражнения 679
24.3 Алгоритм Дейкстры 680
Анализ 684
Упражнения 686
24.4 Разностные ограничения и кратчайшие пути 687
Линейное программирование 687
Системы разностных ограничений 688
Графы ограничений 690
Решение систем разностных ограничений 692
Упражнения 692
24.5 Доказательства свойств кратчайших путей 694
Неравенство треугольника 694
Влияние ослабления на оценки кратчайшего пути 695
Ослабление и деревья кратчайших путей 697
Упражнения 700
Задачи 702
Заключительные замечания 706
Глава 25. Кратчайшие пути между всеми парами вершин 708
Краткое содержание главы 710
25.1 Задача о кратчайших путях и умножение матриц 711
Структура кратчайшего пути 711
Рекурсивное решение задачи о кратчайших путях
между всеми парами вершин 712
Вычисление весов кратчайших путей в восходящем
порядке 712
Улучшение времени работы 714
Упражнения 716
25.2 Алгоритм Флойда-Варшалла 718
Структура кратчайшего пути 718
Рекурсивное решение задачи о кратчайших путях
между всеми парами вершин 719
Стр. 19
20 Содержание
Стр. 20
Содержание 21
Стр. 21
22 Содержание
Упражнения 839
28.3 Решение систем линейных уравнений 839
Обзор LUP-разложения 841
Прямая и обратная подстановки 842
Вычисление LU-разложения 845
Вычисление LUP-разложения 848
Упражнения 852
28.4 Обращение матриц 853
Вычисление обратной матрицы из LUP-разложения 853
Умножение матриц и обращение матрицы 854
Упражнения 857
28.5 Симметричные положительно определенные матрицы
и метод наименьших квадратов 858
Метод наименьших квадратов 861
Упражнения 865
Задачи 865
Заключительные замечания 867
Глава 29. Линейное программирование 869
Политическая задача 869
Общий вид задач линейного программирования 872
Краткий обзор задач линейного программирования 872
Приложения линейного программирования 876
Алгоритмы решения задач линейного программирования 877
29.1 Стандартная и каноническая формы задач линейного
программирования 877
Стандартная форма 878
Преобразование задач линейного программирования
в стандартную форму 879
Преобразование задач линейного программирования
в каноническую форму 882
Упражнения 885
29.2 Формулирование задач в виде задач линейного
программирования 886
Кратчайшие пути 887
Максимальный поток 887
Поиск потока с минимальными затратами 888
Многопродуктовый поток 889
Упражнения 891
29.3 Симплекс-алгоритм 892
Пример симплекс-алгоритма 893
Стр. 22
Содержание 23
Замещение 897
Формальный симплекс-алгоритм 899
Завершение 905
Упражнения 907
29.4 Двойственность 908
Упражнения 914
29.5 Начальное базисное допустимое решение 914
Поиск начального решения 914
Основная теорема линейного программирования 920
Упражнения 921
Задачи 922
Заключительные замечания 924
Глава 30. Полиномы и быстрое преобразование Фурье 926
Полиномы 926
Краткое содержание главы 928
30.1 Представление полиномов 928
Представление, основанное на коэффициентах 929
Представление, основанное на значениях в точках 929
Быстрое умножение полиномов, заданных
в коэффициентной форме 932
Упражнения 934
30.2 ДПФ и БПФ 935
Комплексные корни из единицы 935
Дискретное преобразование Фурье 938
Быстрое преобразование Фурье 938
Интерполяция в точках, являющихся комплексными
корнями из единицы 941
Упражнения 942
30.3 Эффективные реализации БПФ 943
Итеративная реализация БПФ 944
Параллельная схема БПФ 947
Упражнения 949
Задачи 949
Заключительные замечания 953
Глава 31. Теоретико-числовые алгоритмы 954
Размер входных наборов данных и стоимость
арифметических вычислений 955
31.1 Элементарные обозначения, принятые в теории чисел 956
Делимость и делители 956
Простые и составные числа 956
Стр. 23
24 Содержание
Стр. 24
Содержание 25
Стр. 25
26 Содержание
Стр. 26
Содержание 27
Упражнения 1157
35.2 Задача о коммивояжере 1157
35.2.1 Задача о коммивояжере с неравенством треугольника 1158
35.2.2 Общая задача о коммивояжере 1161
Упражнения 1163
35.3 Задача о покрытии множества 1164
Жадный приближенный алгоритм 1166
Анализ 1166
Упражнения 1169
35.4 Рандомизация и линейное программирование 1170
Рандомизированный приближенный алгоритм для
задачи о MAX-3-CNF выполнимости 1170
Аппроксимация взвешенного вершинного покрытия
с помощью линейного программирования 1172
Упражнения 1175
35.5 Задача о сумме подмножества 1176
Точный алгоритм с экспоненциальным временем работы 1176
Схема аппроксимации с полностью полиномиальным
временем работы 1178
Упражнения 1182
Задачи 1182
Заключительные замечания 1186
Стр. 27
28 Содержание
Стр. 28
Содержание 29
Стр. 29
Введение
Преподавателю
Эта книга задумана так, что разнообразие описываемых в ней тем сочетает-
ся с полнотой изложения. Она может стать полезной при чтении разнообразных
курсов, — от курса по структурам данных для студентов до курса по алгоритмам
для аспирантов. Поскольку в книге намного больше материала, чем требуется
Стр. 30
Введение 31
для обычного курса, рассчитанного на один семестр, можно выбрать только тот
материал, который лучше всего соответствует курсу, который вы собираетесь пре-
подавать.
Курсы удобно разрабатывать на основе отдельных глав. Книга написана так,
что ее главы сравнительно независимы одна от другой. В каждой главе материал
излагается по мере увеличения его сложности и разбит на разделы. В студенческом
курсе можно использовать только более легкие разделы, а в аспирантском — всю
главу в полном объеме.
В книгу вошли более 920 упражнений и свыше 140 задач. Упражнения даются
в конце каждого раздела, а задачи — в конце каждой главы. Упражнения пред-
ставлены в виде кратких вопросов для проверки степени освоения материала.
Некоторые из них простые и предназначены для самоконтроля, в то время как
другие — посложнее и могут быть рекомендованы в качестве домашних заданий.
Решение задач требует больших усилий, и с их помощью часто вводится новый
материал. Обычно задачи сформулированы так, что в них содержатся наводящие
вопросы, помогающие найти верное решение.
Разделы и упражнения, которые больше подходят для аспирантов, чем для
студентов, обозначены звездочкой (). Они не обязательно более сложные, чем
те, возле которых звездочка отсутствует; просто для их понимания может пона-
добиться владение более сложным математическим аппаратом. Для того чтобы
справиться с упражнениями со звездочкой, может понадобиться более основа-
тельная подготовка или неординарная сообразительность.
Студенту
Надеемся, что этот учебник станет хорошим введением в теорию алгоритмов.
Авторы попытались изложить каждый алгоритм в доступной и увлекательной
форме. Чтобы облегчить освоение незнакомых или сложных алгоритмов, каждый
из них описывается поэтапно. В книге также приводится подробное объясне-
ние математических вопросов, необходимых для того, чтобы понять проводимый
анализ алгоритмов. Для тех читателей, которые уже в некоторой мере знакомы
с какой-то темой, материал глав организован таким образом, чтобы эти читатели
могли опустить вводные разделы и перейти непосредственно к более сложному
материалу.
Книга получилась довольно большой, поэтому не исключено, что в курсе лек-
ций будет представлена лишь часть изложенного в ней материала. Однако авторы
попытались сделать ее такой, чтобы она стала полезной как сейчас в качестве
учебника, способствующего усвоению курса лекций, так и позже, в профессио-
нальной деятельности, в качестве настольного справочного пособия для матема-
тиков или инженеров.
Стр. 31
32 Введение
Профессионалу
Широкий круг вопросов, которые излагаются в этой книге, позволяет говорить
о том, что она станет прекрасным учебником по теории алгоритмов. Поскольку
каждая глава является относительно самостоятельной, читатель сможет сосредо-
точить внимание на вопросах, интересующих его больше других.
Основная часть обсуждаемых здесь алгоритмов обладает большой практи-
ческой ценностью. Поэтому не обойдены вниманием особенности реализации
алгоритмов и другие инженерные вопросы. Часто предлагаются реальные альтер-
нативы алгоритмам, представляющим преимущественно теоретический интерес.
Если вам понадобится реализовать любой из приведенных алгоритмов, будет
достаточно легко преобразовать приведенный псевдокод в код на вашем любимом
языке программирования. Псевдокод разработан таким образом, чтобы каждый ал-
горитм был представлен ясно и лаконично. Вследствие этого не рассматриваются
обработка ошибок и другие связанные с разработкой программного обеспечения
вопросы, требующие определенных предположений, касающихся конкретной сре-
ды программирования. Авторы попытались представить каждый алгоритм просто
и непосредственно, не используя индивидуальные особенности того или иного
языка программирования, что могло бы усложнить понимание сути алгоритма.
Коллегам
В книге приведена обширная библиография и представлены указания на совре-
менную литературу. В конце каждой главы даются “заключительные замечания”,
содержащие исторические подробности и ссылки. Однако эти замечания не могут
служить исчерпывающим руководством в области алгоритмов. Возможно, в это
будет сложно поверить, но даже в такую объемную книгу не удалось включить
многие интересные алгоритмы из-за недостатка места.
Несмотря на огромное количество писем от студентов с просьбами предоста-
вить решения задач и упражнений, политика авторов — не приводить ссылки на
Стр. 32
Введение 33
Стр. 33
34 Введение
Стр. 34
Введение 35
Web-узел
Еще одно изменение по сравнению с первым изданием данной книги заклю-
чается в том, что теперь книга имеет свой Web-узел: http://mitpress.mit.
edu/algorithms/. С помощью этого Web-узла можно сообщить об ошибках,
получить список известных ошибок или внести предложения; авторы будут рады
узнать мнение читателей. Особенно приветствуются идеи по поводу новых задач
и упражнений, однако их следует предлагать вместе с решениями.
Авторы выражают сожаление, что не могут лично ответить на все замечания.
Стр. 35
36 Введение
Стр. 36
Введение 37
Стр. 37
38 Введение
Стр. 38
Введение 39
(Paul Beame), Ричард Бигль (Richard Beigel), Маргрит Бетке (Margrit Betke), Алекс
Блейкмор (Alex Blakemore), Бобби Блюмоуф (Bobby Blumofe), Александр Браун
(Alexander Brown), Ксавье Кэйзин (Xavier Cazin), Джек Чен (Jack Chan), Ричард
Ченг (Richard Chang), Чинхуа Чен (Chienhua Chen), Йен Ченг (Ien Cheng), Хун
Чой (Hoon Choi), Дрю Коулс (Drue Coles), Кристиан Коллберг (Christian Collberg),
Джордж Коллинз (George Collins), Эрик Конрад (Eric Conrad), Питер Цазар (Peter
Csaszar), Пол Дитц (Paul Dietz), Мартин Дитцфельбингер (Martin Dietzfelbinger),
Скот Дрисдейл (Scot Drysdale), Патриция Илай (Patricia Ealy), Яков Эйзенберг
(Yaakov Eisenberg), Майкл Эрнст (Michael Ernst), Майкл Форменн (Michael For-
mann), Недим Фреско (Nedim Fresko), Хал Габов (Hal Gabow), Марек Галецки
(Marek Galecki), Игал Гальперин (Igal Galperin), Луиза Гаргано (Luisa Gargano),
Джон Гейтли (John Gately), Розарио Дженарио (Rosario Genario), Майэли Гереб
(Mihaly Gereb), Рональд Гринберг (Ronald Greenberg), Джерри Гроссман (Jerry
Grossman), Стефен Гуттери (Stephen Guattery), Александр Хартемик (Alexander
Hartemik), Энтони Хилл (Anthony Hill), Томас Гофмейстер (Thomas Hofmeister),
Мэтью Хостеттер (Mathew Hostetter), Юй-Чун Ху (Yih-Chun Hu), Дик Джонсон-
баух (Dick Johnsonbaugh), Марцин Юрдзинки (Marcin Jurdzinki), Набил Каэйл
(Nabil Kahale), Фумияки Камайя (Fumiaki Kamiya), Ананд Канагала (Anand Kana-
gala), Марк Кентровиц (Mark Kantrowitz), Скотт Карлин (Scott Karlin), Дин Келли
(Dean Kelley), Сэнджей Канна (Sanjay Khanna), Халук Конук (Haluk Konuk), Дайна
Кравец (Dina Kravets), Джон Кроугер (Jon Kroger), Бредли Казмаул (Bradley Kusz-
maul), Тим Ламберт (Tim Lambert), Хенг Лау (Hang Lau), Томас Ленгауэр (Thomas
Lengauer), Джордж Мадрид (George Madrid), Брюс Маггс (Bruce Maggs), Вик-
тор Миллер (Victor Miller), Джозеф Мускат (Joseph Muskat), Танг Нгуйен (Tung
Nguyen), Михаил Орлов (Michael Orlov), Джеймс Парк (James Park), Сионбин
Парк (Seongbin Park), Иоаннис Паскалидис (Ioannis Paschalidis), Боз Патт-Шамир
(Boaz Patt-Shamir), Леонид Пешкин (Leonid Peshkin), Патрицио Поблит (Patricio
Poblete), Ира Пол (Ira Pohl), Стивен Понцио (Stephen Ponzio), Кьелл Пост (Kjell
Post), Тодд Пойнор (Todd Poynor), Колин Препскиус (Colin Prepscius), Шолом Ро-
зен (Sholom Rosen), Дейл Рассел (Dale Russell), Гершель Сейфер (Hershel Safer),
Карен Зайдель (Karen Seidel), Джоэль Сейфирес (Joel Seiferas), Эрик Селиджман
(Erik Seligman), Стэнли Селков (Stanley Selkow), Джеффри Шаллит (Jeffrey Shal-
lit), Грэг Шеннон (Greg Shannon), Мика Шарир (Micha Sharir), Саша Шен (Sasha
Shen), Норман Шульман (Norman Shulman), Эндрю Зингер (Andrew Singer), Дэни-
ел Слитор (Daniel Sleator), Боб Слоан (Bob Sloan), Майкл Софка (Michael Sofka),
Фолькер Струмпен (Volker Strumpen), Лон Саншайн (Lon Sunshine), Джули Сас-
сман (Julie Sussman), Астерио Танака (Asterio Tanaka), Кларк Томборсон (Clark
Thomborson), Нильс Томмесен (Nils Thommesen), Гомер Тильтон (Homer Tilton),
Мартин Томпа (Martin Tompa), Андрей Тум (Andrei Toom), Фельзер Торстен (Felzer
Torsten), Хайенду Вэйшнав (Hirendu Vaishnav), М. Вельдхорст (M. Veldhorst), Люка
Венути (Luca Venuti), Джайн Вонг (Jian Wang), Майкл Веллман (Michael Wellman),
Стр. 39
40 Введение
Джерри Винер (Gerry Wiener), Рональд Вильямс (Ronald Williams), Дэвид Вольф
(David Wolfe), Джефф Вонг (Jeff Wong), Ричард Ваунди (Richard Woundy), Нил
Юнг (Neal Young), Гайан Ю (Huaiyuan Yu), Тайан Юксинг (Tian Yuxing), Джо
Зачари (Joe Zachary), Стив Жанг (Steve Zhang), Флориан Щоук (Florian Zschoke)
и Ури Цвик (Uri Zwick).
Многие наши коллеги написали подробные обзоры или заполнили длинные
бланки опросов. Авторы благодарят Нэнси Амато (Nancy Amato), Джима Аспне-
са (Jim Aspnes), Кевина Комптона (Kevin Compton), Вильяма Иванса (William
Evans), Питера Гекса (Peter Gacs), Майкла Гольдвассера (Michael Goldwasser),
Андржея Проскуровски (Andrzej Proskurowski), Виджея Рамачандрана (Vijaya Ra-
machandran) и Джона Райфа (John Reif). Мы также благодарим тех, кто участвовал
в опросе и вернул его результаты. Это Джеймс Абелло (James Abello), Джош Би-
нело (Josh Benaloh), Брайан Бересфорд-Смит (Bryan Beresford-Smith), Кеннет Бла
(Kenneth Blaha), Ганс Бодлаендер (Hans Bodlaender), Ричард Бори (Richard Borie),
Тед Браун (Ted Brown), Доменико Кантоун (Domenico Cantone), М. Чен (M. Chen),
Роберт Цимиковски (Robert Cimikowski), Вильям Клоксин (William Clocksin), Па-
уль Калл (Paul Cull), Рик Декер (Rick Decker), Мэтью Дикерсон (Matthew Dick-
erson), Роберт Дуглас (Robert Douglas), Маргарет Флек (Margaret Fleck), Майкл
Гудрич (Michael Goodrich), Сюзанн Гамбруш (Susanne Hambrusch), Дин Гендрикс
(Dean Hendrix), Ричард Джонсонбау (Richard Johnsonbaugh), Кирякос Калоркоти
(Kyriakos Kalorkoti), Шринивас Канканахалли (Srinivas Kankanahalli), Хикио Кох
(Hikyoo Koh), Стивен Линделль (Steven Lindell), Еррол Ллойд (Errol Lloyd), Энди
Лопес (Andy Lopez), Дайан Рей Лопес (Dian Rae Lopez), Джордж Лакер (George
Lucker), Дэвид Мейер (David Maier), Чарльз Мартель (Charles Martel), Ксайнонг
Менг (Xiannong Meng), Дэвид Маунт (David Mount), Альберто Поликрити (Al-
berto Policriti), Анджей Проскуровски (Andrzej Proskurowski), Кирк Прус (Kirk
Pruhs), Ив Робер (Yves Robert), Гуна Сизараман (Guna Seetharaman), Стэнли Сел-
ков (Stanley Selkow), Роберт Слоан (Robert Sloan), Чарльз Стил (Charles Steele),
Джерад Тель (Gerard Tel), Мурали Варанаси (Murali Varanasi), Бернд Уолтер (Bernd
Walter) и Альдин Райт (Alden Wright). Авторы хотели бы учесть все внесенные
предложения. Единственная проблема заключается в том, что если бы это было
сделано, объем второго издания мог бы превысить 3000 страниц!
Второе издание готовилось к публикации в LATEX 2ε . Майкл Даунс (Michael
Downes) преобразовал LATEX-сценарии из “классической” версии LATEX в LATEX 2ε
и изменил текстовые файлы таким образом, чтобы в них использовались эти сце-
нарии. Помощь в составлении текста в формате LATEX также оказал Дэвид Джонс
(David Jones). Рисунки ко второму изданию созданы авторами в программе Mac-
Draw Pro. Как и в первом издании, предметный указатель составлен с помощью
Windex, — программы на C, написанной авторами, а библиография подготовлена
с помощью BIBTEX. Айоркор Миллз-Титти (Ayorkor Mills-Tettey) и Роб Лизерн
Стр. 40
Введение 41
Стр. 41
От издательства
Стр. 42
ЧАСТЬ I
Основы
Стр. 43
Введение
Эта часть книги заставит вас задуматься о вопросах, связанных с разработкой
и анализом алгоритмов. Она была запланирована как вводный курс, в котором
рассматриваются способы определения алгоритмов, некоторые стратегии их раз-
работки, использующиеся в этой книге, а также применяемые при анализе алго-
ритмов различные основополагающие идеи. Кратко рассмотрим содержание глав
первой части.
В главе 1 рассматривается понятие алгоритма и его роль в современных
вычислительных системах. В ней приводится определение алгоритма и даются
некоторые примеры. Здесь также обосновывается положение о том, что алгорит-
мы — это такой же технологический продукт, как, например, аппаратное обеспече-
ние, графические интерфейсы пользователя, объектно-ориентированные системы
или сети.
В главе 2 читатель получит возможность ознакомиться с алгоритмами, с помо-
щью которых решается задача о сортировке последовательности из n чисел. Эти
алгоритмы сформулированы в виде псевдокода. Несмотря на то, что используе-
мый псевдокод напрямую не преобразуется ни в один из общепринятых языков
программирования, он вполне адекватно передает структуру алгоритма, поэтому
достаточно компетентный программист легко сможет реализовать его на любом
языке программирования. Для изучения выбраны алгоритм сортировки вставкой,
в котором используется инкрементный подход, и алгоритм сортировки слиянием,
который характеризуется применением рекурсивного метода, известного также
как метод “разделяй и властвуй” (метод разбиения). В обоих алгоритмах вре-
мя выполнения возрастает с ростом количества сортируемых элементов, однако
скорость этого роста зависит от выбранного алгоритма. В этой главе будет опре-
делено время работы изучаемых алгоритмов; кроме того, вы познакомитесь со
специальными обозначениями для выражения времени работы алгоритмов.
В главе 3 дается точное определение обозначений, введенных в главе 2 (ко-
торые называются асимптотическими обозначениями). В начале главы 3 опре-
деляется несколько асимптотических обозначений для оценки времени работы
алгоритма сверху и/или снизу. Остальные разделы главы в основном посвяще-
ны описанию математических обозначений. Их предназначение не столько в том,
чтобы ознакомить читателя с новыми математическими концепциями, сколько
в том, чтобы он смог убедиться, что используемые им обозначения совпадают
с принятыми в данной книге.
В главе 4 представлено дальнейшее развитие метода “разделяй и властвуй”,
введенного в главе 2. В частности, в главе 4 представлены методы решения рекур-
рентных соотношений, с помощью которых описывается время работы рекурсив-
ных алгоритмов. Бо́льшая часть главы посвящена обоснованию “метода контроля”
(master method), который используется для решения рекуррентных соотношений,
Стр. 44
Часть I. Основы 45
Стр. 45
ГЛАВА 1
Роль алгоритмов в вычислениях
1.1 Алгоритмы
Говоря неформально, алгоритм (algorithm) — это любая корректно опреде-
ленная вычислительная процедура, на вход (input) которой подается некоторая
величина или набор величин, и результатом выполнения которой является выход-
ная (output) величина или набор значений. Таким образом, алгоритм представляет
собой последовательность вычислительных шагов, преобразующих входные ве-
личины в выходные.
Алгоритм также можно рассматривать как инструмент, предназначенный для
решения корректно поставленной вычислительной задачи (computational prob-
lem). В постановке задачи в общих чертах задаются отношения между входом
и выходом. В алгоритме описывается конкретная вычислительная процедура, с по-
мощью которой удается добиться выполнения указанных отношений.
Например, может понадобиться выполнить сортировку последовательности
чисел в неубывающем порядке. Эта задача часто возникает на практике и служит
благодатной почвой для ознакомления на ее примере со многими стандартными
методами разработки и анализа алгоритмов. Задача сортировки (sorting problem)
формально определяется следующим образом.
Стр. 46
Глава 1. Роль алгоритмов в вычислениях 47
Стр. 47
48 Часть I. Основы
Стр. 48
Глава 1. Роль алгоритмов в вычислениях 49
их решения. В книге также показано, как решить многие конкретные задачи, в том
числе те, что перечислены ниже.
• Пусть имеется карта дорог, на которой обозначены расстояния между каж-
дой парой соседних перекрестков. Наша цель — определить кратчайший
путь от одного перекрестка к другому. Количество возможных маршрутов
может быть огромным, даже если исключить те из них, которые содержат
самопересечения. Как найти наиболее короткий из всех возможных марш-
рутов? При решении этой задачи карта дорог (которая сама по себе является
моделью настоящих дорог) моделируется в виде графа (мы подробнее по-
знакомимся с графами в главе 10 и приложении Б). Задача будет заключаться
в определении кратчайшего пути от одной вершины графа к другой. Эффек-
тивное решение этой задачи представлено в главе 24.
• Пусть дана последовательность A1 , A2 , . . . , An , образованная n матрица-
ми, и нам нужно найти произведение этих матриц. Поскольку матричное
произведение обладает свойством ассоциативности, существует несколь-
ко корректных порядков умножения. Например, если n = 4, перемноже-
ние матриц можно выполнять любым из следующих способов (опреде-
ляемых скобками): (A1 (A2 (A3 A4 ))), (A1 ((A2 A3 ) A4 )), ((A1 A2 ) (A3 A4 )),
((A1 (A2 A3 )) A4 ) или (((A1 A2 ) A3 ) A4 ). Если все эти матрицы квадратные
(т.е. одинакового размера), порядок перемножения не влияет на продолжи-
тельность процедуры. Если же матрицы различаются по размеру (но при
этом их размеры соответствуют правилам матричного умножения), то по-
рядок их перемножения может очень сильно влиять на время выполнения
процедуры. Количество всевозможных вариантов, различающихся порядком
перемножения матриц, растет с увеличением количества матриц по экспо-
ненциальному закону, поэтому для перебора всех этих вариантов может
потребоваться довольно длительное время. Из главы 15 мы узнаем, как эта
задача намного эффективнее решается с помощью общего метода, извест-
ного как динамическое программирование.
• Пусть имеется уравнение ax ≡ b (modn), где a, b и n — целые числа, и нуж-
но найти все целые x по модулю n, удовлетворяющие этому уравнению.
Оно может не иметь решения, может иметь одно или несколько решений.
Можно попытаться применить метод, заключающийся в последовательной
подстановке в уравнение чисел x = 0, 1, . . . , n−1, но в главе 31 представлен
более эффективный метод.
• Пусть имеется n принадлежащих плоскости точек, и нужно найти выпуклую
оболочку этих точек. Выпуклой оболочкой точек называется минимальный
выпуклый многоугольник, содержащий эти точки. Для решения этой задачи
удобно воспользоваться такой наглядной картиной: если представить точки
в виде вбитых в доску и торчащих из нее гвоздей, то выпуклую оболочку
Стр. 49
50 Часть I. Основы
можно получить, намотав на них резинку таким образом, чтобы все гвоз-
ди вошли внутрь замкнутой линии, образуемой резинкой. Каждый гвоздь,
вокруг которого обвивается резинка, становится вершиной выпуклой обо-
лочки (рис. 33.6). В качестве набора вершин может выступать любое из
2n подмножеств множества точек. Однако недостаточно знать, какие точ-
ки являются вершинами выпуклой оболочки, нужно еще указать порядок
их обхода. Таким образом, чтобы найти выпуклую оболочку, приходится
перебрать множество вариантов. В главе 33 описаны два хороших метода
определения выпуклой оболочки.
Приведенные выше случаи применения алгоритмов отнюдь не являются ис-
черпывающими, однако на их примере выявляются две общие характеристики,
присущие многим интересным алгоритмам.
1. Есть множество вариантов-кандидатов, большинство из которых решения-
ми не являются. Поиск среди них нужной комбинации является довольно
трудоемким.
2. Задачи имеют практическое применение. Простейший пример среди пере-
численных задач — определение кратчайшего пути, соединяющего два пере-
крестка. Любая компания, занимающаяся авто- или железнодорожными пе-
ревозками, финансово заинтересована в том, чтобы определить кратчайший
маршрут. Это способствовало бы снижению затрат труда и расходов горю-
чего. Маршрутизатору Internet также нужно иметь возможность находить
кратчайшие пути в сети, чтобы как можно быстрее доставлять сообщения.
Структуры данных
В книге представлен ряд структур данных. Структура данных (data struc-
ture) — это способ хранения и организации данных, облегчающий доступ к этим
данным и их модификацию. Ни одна структура данных не является универсаль-
ной и не может подходить для всех целей, поэтому важно знать преимущества
и ограничения, присущие некоторым из них.
Методические указания
Данную книгу можно рассматривать как “сборник рецептов” для алгоритмов.
Правда, однажды вам встретится задача, для которой вы не сможете найти опуб-
ликованный алгоритм (например, таковы многие из приведенных в книге упраж-
нений и задач). Данная книга научит вас методам разработки алгоритмов и их
анализа. Это позволит вам разрабатывать корректные алгоритмы и оценивать их
эффективность самостоятельно.
Стр. 50
Глава 1. Роль алгоритмов в вычислениях 51
Сложные задачи
Большая часть этой книги посвящена эффективным алгоритмам. Обычной
мерой эффективности для нас является скорость и время, в течение которого
алгоритм выдает результат. Однако существуют задачи, для которых неизвестны
эффективные методы их решения. В главе 34 рассматривается интересный вопрос,
имеющий отношение к подобным задачам, известным как NP-полные.
Почему же NP-полные задачи представляют интерес? Во-первых, несмотря
на то, что до сих пор не найден эффективный алгоритм их решения, также не
доказано, что такого алгоритма не существует. Другими словами, неизвестно, су-
ществует ли эффективный алгоритм для NP-полных задач. Во-вторых, набор NP-
полных задач обладает замечательным свойством. Оно заключается в том, что
если эффективный алгоритм существует хотя бы для одной из этих задач, то его
можно сформулировать и для всех остальных. Эта взаимосвязь между NP-пол-
ными задачами и отсутствие методов их эффективного решения вызывает еще
бо́льший интерес к ним. В третьих, некоторые NP-полные задачи похожи (но не
идентичны) на задачи, для которых известны эффективные алгоритмы. Небольшое
изменение формулировки задачи может значительно ухудшить эффективность са-
мого лучшего из всех известных алгоритмов.
Полезно располагать знаниями о NP-полных задачах, поскольку в реальных
приложениях некоторые из них возникают неожиданно часто. Если перед вами
встанет задача найти эффективный алгоритм для NP-полной задачи, скорее всего,
вы потратите много времени на безрезультатные поиски. Если же вы покажете, что
данная задача принадлежит к разряду NP-полных, то можно будет вместо самого
лучшего из всех возможных решений попробовать найти достаточно эффективное.
Рассмотрим конкретный пример. Компания грузового автотранспорта имеет
один центральный склад. Каждый день грузовики загружаются на этом складе
и отправляются по определенному маршруту, доставляя груз в несколько мест.
В конце рабочего дня грузовик должен вернуться на склад, чтобы на следующее
утро его снова можно было загрузить. Чтобы сократить расходы, компании нужно
выбрать оптимальный порядок доставки груза в различные точки. При этом рас-
стояние, пройденное грузовиком, должно быть минимальным. Эта задача хорошо
известна как “задача о коммивояжере”, и она является NP-полной. Эффективный
алгоритм решения для нее неизвестен, однако при некоторых предположениях
можно указать такие алгоритмы, в результате выполнения которых полученное
расстояние будет ненамного превышать минимально возможное. Подобные “при-
ближенные алгоритмы” рассматриваются в главе 35.
Стр. 51
52 Часть I. Основы
Упражнения
1.1-1. Приведите реальные примеры задач, в которых возникает одна из таких
вычислительных задач: сортировка, определение оптимального порядка
перемножения матриц, поиск выпуклой оболочки.
1.1-2. Какими еще параметрами, кроме скорости, можно характеризовать алго-
ритм на практике?
1.1-3. Выберите одну из встречавшихся вам ранее структур данных и опишите
ее преимущества и ограничения.
1.1-4. Что общего между задачей об определении кратчайшего пути и задачей
о коммивояжере? Чем они различаются?
1.1-5. Сформулируйте задачу, в которой необходимо только наилучшее реше-
ние. Сформулируйте также задачу, в которой может быть приемлемым
решение, достаточно близкое к наилучшему.
Эффективность
Алгоритмы, разработанные для решения одной и то же задачи, часто очень
сильно различаются по эффективности. Эти различия могут быть намного зна-
чительнее, чем те, что вызваны применением неодинакового аппаратного и про-
граммного обеспечения.
Стр. 52
Глава 1. Роль алгоритмов в вычислениях 53
Стр. 53
54 Часть I. Основы
Стр. 54
Глава 1. Роль алгоритмов в вычислениях 55
Упражнения
1.2-1. Приведите пример приложения, для которого необходимо алгоритмиче-
ское наполнение на уровне приложений, и дайте характеристику функ-
ций, входящих в состав этих алгоритмов.
1.2-2. Предположим, на одной и той же машине проводится сравнительный
анализ реализаций двух алгоритмов сортировки, работающих по методу
вставок и по методу слияния. Для сортировки n элементов методом вста-
вок необходимо 8n2 шагов, а для сортировки методом слияния — 64n lg n
шагов. При каком значении n время сортировки методом вставок превы-
сит время сортировки методом слияния?
1.2-3. При каком минимальном значении n алгоритм, время работы которого
определяется формулой 100n2 , работает быстрее, чем алгоритм, время
работы которого выражается как 2n , если оба алгоритма выполняются на
одной и той же машине?
Задачи
1-1. Сравнение времени работы алгоритмов
Ниже приведена таблица, строки которой соответствуют различным функ-
циям f (n), а столбцы — значениям времени t. Определите максималь-
ные значения n, для которых задача может быть решена за время t, если
Стр. 55
56 Часть I. Основы
Заключительные замечания
Имеется множество учебников, посвященных общим вопросам, которые име-
ют отношение к алгоритмам. К ним относятся книги Ахо (Aho), Хопкрофта
(Hopcroft) и Ульмана (Ullman) [5,6], Бейза (Baase) и Ван Гельдера (Van Gelder)
[26], Брассарда (Brassard) и Бретли (Bratley) [46,47], Гудрича (Goodrich) и Та-
мазии (Tamassia) [128], Горовица (Horowitz), Сани (Sahni) и Раджисекарана (Ra-
jasekaran) [158], Кингстона (Kingston) [179], Кнута (Knuth) [182,183,185], Козе-
на (Kozen) [193], Манбера (Manber) [210], Мельхорна (Mehlhorn) [217,218,219],
Пурдома (Purdom) и Брауна (Brown) [252], Рейнгольда (Reingold), Ньевергель-
та (Nievergelt) и Део (Deo) [257], Седжевика (Sedgewick) [269], Скьены (Skiena)
[280] и Вильфа (Wilf) [315]. Некоторые аспекты разработки алгоритмов, имеющие
большую практическую направленность, обсуждаются в книгах Бентли (Bentley)
[39,40] и Гоннета (Gonnet) [126]. Обзоры по алгоритмам можно также найти в кни-
гах Handbook of Theoretical Computer Science, Volume A [302] и CRC Handbook on
Algorithms and Theory of Computation [24]. Обзоры алгоритмов, применяющихся
в вычислительной биологии, можно найти в учебниках Гасфилда (Gusfield) [136],
Певзнера (Pevzner) [240], Сетубала (Setubal) и Мейдениса (Meidanis) [272], а также
Вотермена (Waterman) [309].
Стр. 56
ГЛАВА 2
Приступаем к изучению
Стр. 57
58 Часть I. Основы
♣♣♣
7
♣
♣♣
5♣ ♣
4 ♣♣ ♣♣ ♣
10
2 ♣
♣ ♣♣ ♣ ♣
♣
♣♣ ♣
7
♣ ♣♣ ♣
♣
♣
5♣4 2♣
♣♣♣
♣♣ ♣
10
Стр. 58
Глава 2. Приступаем к изучению 59
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
а) 5 2 4 6 1 3 б) 2 5 4 6 1 3 в) 2 4 5 6 1 3
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
г) 2 4 5 6 1 3 д) 1 2 4 5 6 3 е) 1 2 3 4 5 6
Стр. 59
60 Часть I. Основы
Стр. 60
Глава 2. Приступаем к изучению 61
Стр. 61
62 Часть I. Основы
Стр. 62
Глава 2. Приступаем к изучению 63
Упражнения
2.1-1. Используя в качестве модели рис. 2.2, проиллюстрируйте работу алгорит-
ма INSERTION_SORT по упорядочению массива A = 31, 41, 59, 26, 41, 58.
2.1-2. Перепишите процедуру INSERTION_SORT так, чтобы она выполняла сор-
тировку не в невозрастающем, а в неубывающем порядке.
2.1-3. Рассмотрим задачу поиска.
Вход: последовательность n чисел A = a1 , a2 , . . . , an и величина v.
Выход: индекс i, обладающий свойством v = A [i], или значение NIL,
если в массиве A отсутствует значение v.
Составьте псевдокод линейного поиска, при работе которого выполня-
ется сканирование последовательности в поиске значения v. Докажите
корректность алгоритма с помощью инварианта цикла. Убедитесь, что
Стр. 63
64 Часть I. Основы
Стр. 64
Глава 2. Приступаем к изучению 65
Стр. 65
66 Часть I. Основы
Стр. 66
Глава 2. Приступаем к изучению 67
Стр. 67
68 Часть I. Основы
n
n
T (n) = c1 n + c2 (n − 1) + c4 (n − 1) + c5 t j + c6 (tj − 1)+
j=2 j=2
n
+ c7 (tj − 1) + c8 (n − 1) .
j=2
T (n) = c1 n + c2 (n − 1) + c4 (n − 1) + c5 (n − 1) + c8 (n − 1) =
= (c1 + c2 + c4 + c5 + c8 ) n − (c2 + c4 + c5 + c8 ) .
n
n (n + 1)
j= −1
2
j=2
и
n
n (n − 1)
(j − 1) =
2
j=2
5
Это правило не всегда применимо к такому ресурсу, как память. Если инструкция оперирует
с m словами памяти и выполняется n раз, то это еще не означает, что всего при этом потребляется
mn слов памяти.
Стр. 68
Глава 2. Приступаем к изучению 69
Это время работы можно записать как an2 + bn + c, где константы a, b и c зависят
от ci . Таким образом, это квадратичная функция от n.
Обычно время работы алгоритма фиксировано для определенных входных
данных, как в случае сортировки вставкой, однако в последующих главах мы
ознакомимся с некоторыми интересными алгоритмами, поведение которых носит
вероятностный характер. Время их работы может меняться даже для одних и тех
же входных данных.
Стр. 69
70 Часть I. Основы
Порядок возрастания
Для облегчения анализа процедуры INSERTION_SORT были сделаны некоторые
упрощающие предположения. Во-первых, мы проигнорировали фактическое вре-
мя выполнения каждой инструкции, представив эту величину в виде некоторой
константы ci . Далее мы увидели, что учет всех этих констант дает излишнюю ин-
формацию: время работы алгоритма в наихудшем случае выражается формулой
an2 + bn + c, где a, b, и c — некоторые константы, зависящие от стоимостей ci .
Таким образом, мы игнорируем не только фактические стоимости команд, но и их
абстрактные стоимости ci .
Теперь введем еще одно абстрактное понятие, упрощающее анализ. Это ско-
рость роста (rate of growth), или порядок роста (order of growth), времени рабо-
ты, который и интересует нас на самом деле. Таким образом, во внимание будет
приниматься только главный член формулы (т.е. в нашем случае an2 ), поскольку
при больших n членами меньшего порядка можно пренебречь. Кроме того, по-
стоянные множители при главном члене также будут игнорироваться, так как для
оценки вычислительной эффективности алгоритма с входными данными большо-
го объема они менее важны, чем порядок роста. Таким образом, время работы
6
Далее в книге строгий термин “математическое ожидание” некоторой величины зачастую для
простоты изложения заменяется термином “ожидаемое значение”, например, “ожидаемое время
работы алгоритма” означает “математическое ожидание времени работы алгоритма”. — Прим. ред.
Стр. 70
Глава 2. Приступаем к изучению 71
алгоритма, работающего по методу вставок, в наихудшем случае равно Θ n2
(произносится “тета от n в квадрате”). В этой главе Θ-обозначения используются
неформально; их строгое определение приводится в главе 3.
Обычно один алгоритм считается эффективнее другого, если время его работы
в наихудшем случае имеет более низкий порядок роста. Из-за наличия постоян-
ных множителей и второстепенных членов эта оценка может быть ошибочной,
если входные данные невелики.Однако
если объем входных данных значитель-
ный, то, например, алгоритм Θ n 2 в наихудшем случае работает быстрее, чем
алгоритм Θ n3 .
Упражнения
2.2-1. Выразите функцию n3 /1000 − 100n2 − 100n + 3 в Θ-обозначениях.
2.2-2. Рассмотрим сортировку элементов массива A, которая производится так.
Сначала определяется наименьший элемент массива A, который ставится
на место элемента A [1], затем производится поиск второго наименьше-
го элемента массива A, который ставится на место элемента A [2]. Этот
процесс продолжается для первых n − 1 элементов массива A. Запи-
шите псевдокод этого алгоритма, известного как сортировка выбором
(selection sort). Какой инвариант цикла сохраняется для этого алгоритма?
Почему его достаточно выполнить для первых n − 1 элементов, а не для
всех n элементов? Определите время работы алгоритма в наилучшем
и наихудшем случаях и запишите его в Θ-обозначениях.
2.2-3. Рассмотрим алгоритм линейного поиска (см. упражнение 2.1-3). Для
скольких элементов входной последовательности в среднем нужно про-
извести проверку, если предполагается, что все элементы массива с рав-
ной вероятностью могут иметь искомое значение? Что происходит в наи-
худшем случае? Чему равно время работы алгоритма линейного поис-
ка в среднем и в наихудшем случае (в Θ-обозначениях)? Обоснуйте
ваш ответ.
2.2-4. Каким образом можно модифицировать почти каждый алгоритм, чтобы
получить оптимальное время работы в наилучшем случае?
Стр. 71
72 Часть I. Основы
Стр. 72
Глава 2. Приступаем к изучению 73
Стр. 73
74 Часть I. Основы
4 for i ← 1 to n1
5 do L[i] ← A[p + i − 1]
6 for j ← 1 to n2
7 do R[j] ← A[q + j]
8 L[n1 + 1] ← ∞
9 R[n2 + 1] ← ∞
10 i←1
11 j←1
12 for k ← p to r
13 do if L[i] R[j]
14 then A[k] ← L[i]
15 i←i+1
16 else A[k] ← R[j]
17 j ←j+1
Подробно опишем работу процедуры MERGE. В строке 1 вычисляется длина
n1 подмассива A [p..q], а в строке 2 — длина n2 подмассива A [q + 1..r]. Далее
в строке 3 создаются массивы L (“левый” — “left”) и R (“правый” — “right”),
длины которых равны n1 + 1 и n2 + 1 соответственно. В цикле for в строках 4
и 5 подмассив A [p..q] копируется в массив L [1..n1 ], а в цикле for в строках 6 и 7
подмассив A [q + 1..r] копируется в массив R [1..n2 ]. В строках 8 и 9 последним
элементам массивов L и R присваиваются сигнальные значения.
Как показано на рис. 2.3, в результате копирования и добавления сигнальных
карт получаем массив L с последовательностью чисел 2, 4, 5, 7, ∞ и массив R
с последовательностью чисел 1, 2, 3, 6, ∞. Светло-серые ячейки массива A со-
держат конечные значения, а светло-серые ячейки массивов L и R — значения,
которые еще только должны быть скопированы обратно в массив A. В светло-се-
рых ячейках находятся исходные значения из подмассива A [9..16] вместе с двумя
сигнальными картами. В темно-серых ячейках массива A содержатся значения,
которые будут заменены другими, а в темно-серых ячейках массивов L и R —
значения, уже скопированные обратно в массив A. В частях рисунка а–з показано
состояние массивов A, L и R, а также соответствующие индексы k, i и j перед
каждой итерацией цикла в строках 12–17. В части и показано состояние масси-
вов и индексов по завершении работы алгоритма. На данном этапе подмассив
A [9..16] отсортирован, а два сигнальных значения в массивах L и R — един-
ственные элементы, оставшиеся в этих массивах и не скопированные в массив A.
В строках 10–17, проиллюстрированных на рис. 2.3, выполняется r − p + 1 основ-
ных шагов, в ходе каждого из которых производятся манипуляции с инвариантом
цикла, описанным ниже.
Стр. 74
Глава 2. Приступаем к изучению 75
8 9 10 11 12 13 14 15 16 17 8 9 10 11 12 13 14 15 16 17
A ... 2 4 5 7 1 2 3 6 ... A ... 1 4 5 7 1 2 3 6 ...
k k
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 ∞ R 1 2 3 6 ∞ L 2 4 5 7 ∞ R 1 2 3 6 ∞
i j i j
а) б)
8 9 10 11 12 13 14 15 16 17 8 9 10 11 12 13 14 15 16 17
A ... 1 2 5 7 1 2 3 6 ... A ... 1 2 2 7 1 2 3 6 ...
k k
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 ∞ R 1 2 3 6 ∞ L 2 4 5 7 ∞ R 1 2 3 6 ∞
i j i j
в) г)
8 9 10 11 12 13 14 15 16 17 8 9 10 11 12 13 14 15 16 17
A ... 1 2 2 3 1 2 3 6 ... A ... 1 2 2 3 4 2 3 6 ...
k k
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 ∞ R 1 2 3 6 ∞ L 2 4 5 7 ∞ R 1 2 3 6 ∞
i j i j
д) е)
8 9 10 11 12 13 14 15 16 17 8 9 10 11 12 13 14 15 16 17
A ... 1 2 2 3 4 5 3 6 ... A ... 1 2 2 3 4 5 6 6 ...
k k
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 ∞ R 1 2 3 6 ∞ L 2 4 5 7 ∞ R 1 2 3 6 ∞
i j i j
ж) з)
8 9 10 11 12 13 14 15 16 17
A ... 1 2 2 3 4 5 6 7 ...
k
1 2 3 4 5 1 2 3 4 5
L 2 4 5 7 ∞ R 1 2 3 6 ∞
i j
и)
Рис. 2.3. Операции, выполняемые в строках 10–17 процедуры MERGE(A, 9, 12, 16),
когда в подмассиве A [9..16] содержится последовательность 2, 4, 5, 7, 1, 2, 3, 6
Стр. 75
76 Часть I. Основы
Стр. 76
Глава 2. Приступаем к изучению 77
Отсортированная последовательность
1 2 2 3 4 5 6 7
Слияние
2 4 5 7 1 2 3 6
Слияние Слияние
2 5 4 7 1 3 2 6
5 2 4 7 1 3 2 6
Исходная последовательность
Стр. 77
78 Часть I. Основы
Стр. 78
Глава 2. Приступаем к изучению 79
Стр. 79
80 Часть I. Основы
T(n) cn cn
T(n/2) T(n/2) cn /2 cn /2
а) б) в)
cn cn
cn /2 cn /2 cn
lg n
cn /4 cn /4 cn /4 cn /4 cn
..
.
c c c c c ... c c cn
г) Всего: cn lg n + cn
Стр. 80
Глава 2. Приступаем к изучению 81
Упражнения
2.3-1. Используя в качестве образца рис. 2.4, проиллюстрируйте работу алго-
ритма сортировки методом слияний для массива A = 3, 41, 52, 26, 38, 57,
9, 49.
Стр. 81
82 Часть I. Основы
является T (n) = n lg n.
2.3-4. Сортировку вставкой можно представить в виде рекурсивной последо-
вательности следующим образом. Чтобы отсортировать массив A [1..n],
сначала нужно выполнить сортировку массива A [1..n − 1], после чего
в этот отсортированный массив помещается элемент A [n]. Запишите
рекуррентное уравнение для времени работы этой рекурсивной версии
алгоритма сортировки вставкой.
2.3-5. Возвращаясь к задаче поиска (см. упражнение 2.1-3), нетрудно заметить,
что если последовательность A отсортирована, то значение среднего эле-
мента этой последовательности можно сравнить с искомым значением v
и сразу исключить половину последовательности из дальнейшего рас-
смотрения. Двоичный (бинарный) поиск (binary search) — это алгоритм,
в котором такая процедура повторяется неоднократно, что всякий раз
приводит к уменьшению оставшейся части последовательности в два ра-
за. Запишите псевдокод алгоритма бинарного поиска (в итерационном
или рекурсивном виде). Докажите, что время работы этого алгоритма
в наихудшем случае возрастает как Θ (lg n).
2.3-6. Обратите внимание, что в цикле while в строках 5–7 процедуры INSER-
TION_SORT в разделе 2.1, используется линейный поиск для просмотра
(в обратном порядке) отсортированного подмассива A [1..j − 1]. Можно
ли использовать бинарный поиск (см. упражнение 2.3-5) вместо линейно-
го, чтобы время работы этого алгоритма в наихудшем случае улучшилось
и стало равным Θ (n lg n)?
2.3-7. Пусть имеется множество S, состоящее из n целых чисел, и отдельное
целое число x; необходимо определить, существуют ли во множестве S
два элемента, сумма которых равна x. Разработайте алгоритм решения
этой задачи, время работы которого возрастало бы с увеличением n как
Θ (n lg n).
Стр. 82
Глава 2. Приступаем к изучению 83
Задачи
2-1. Сортировка вставкой для небольших подмассивов, возникающих
при сортировке слиянием
Несмотря на то, что с увеличением количества сортируемых элемен-
тов время сортировки методом слияний в наихудшем случае
растет как
Θ (n lg n), а время сортировки методом вставок — как Θ n2 , благода-
ря постоянным множителям для малых n сортировка методом вставок
выполняется быстрее. Таким образом, есть смысл использовать сорти-
ровку методом вставок в процессе сортировки методом слияний, когда
подзадачи становятся достаточно маленькими. Рассмотрите модифика-
цию алгоритма сортировки, работающего по методу слияний, когда n/k
подмассивов длины k сортируются методом вставок, после чего они объ-
единяются с помощью обычного механизма слияния. Величина k должна
быть найдена в процессе решения задачи.
а) Покажите, что n/k подмассивов, в каждом из которых находится
k элементов, в наихудшем случае можно отсортировать по методу
вставок за время Θ (nk).
б) Покажите, что в наихудшем случае время, требуемое для объедине-
ния этих подмассивов, равно Θ (n lg (n/k)).
в) Допустим, что время работы модифицированного алгоритма в наи-
худшем случае равно Θ (nk + n lg (n/k)). Определите максималь-
ное асимптотическое (в Θ-обозначениях) значение k как функцию
от n, для которого асимптотическое время работы модифицирован-
ного алгоритма равно времени работы стандартного алгоритма сор-
тировки методом слияния.
г) Как следует выбирать параметр k на практике?
2-2. Корректность пузырьковой сортировки
Пузырьковый метод — популярный алгоритм сортировки. В его осно-
ве лежит многократная перестановка соседних элементов, нарушающих
порядок сортировки:
BUBBLESORT(A)
1 for i ← 1 to length[A]
2 do for j ← length[A] downto i + 1
3 do if A[j] < A[j − 1]
4 then Поменять местами A[j] ↔ A[j − 1]
а) Пусть A — выходной массив, полученный в результате работы про-
цедуры BUBBLESORT(A). Чтобы доказать, что этот алгоритм работает
Стр. 83
84 Часть I. Основы
где n = length [A]. Что еще необходимо доказать, чтобы стало оче-
видно, что в ходе работы алгоритма BUBBLESORT действительно вы-
полняется сортировка входного массива?
В следующих двух пунктах доказываются неравенства (2.3).
б) Дайте точную формулировку инварианта цикла for в строках 2–4,
и докажите, что он сохраняется. Доказательство должно иметь та-
кую же структуру доказательства инварианта цикла, которая исполь-
зовалась в аналогичных доказательствах в данной главе.
в) С помощью условия завершения инварианта цикла, доказанного
в пункте б, сформулируйте инвариант цикла for в строках 1–4, кото-
рый бы позволил доказать неравенства (2.3). Доказательство должно
иметь такую же структуру доказательства инварианта цикла, кото-
рая использовалась в аналогичных доказательствах в данной главе.
г) Определите время пузырьковой сортировки в наихудшем случае
и сравните его со временем сортировки методом вставок.
2-3. Корректность правила Горнера
В приведенном ниже фрагменте кода реализовано правило Горнера (Hor-
ner’s rule), позволяющее вычислить значение полинома
n
P (x) = ak xk =
k=0
= a0 + x (a1 + x (a2 + · · · + x (an−1 + xan ) . . .))
1 y←0
2 i←n
3 while i ≥ 0
4 do y ← ai + x · y
5 i←i−1
а) Определите асимптотическое время работы приведенного выше
фрагмента кода.
б) Напишите псевдокод, реализующий алгоритм обычного вычисления
полинома, когда каждое слагаемое полинома вычисляется отдельно.
Стр. 84
Глава 2. Приступаем к изучению 85
n−(j+1)
y= ak+i+1 xk .
k=0
Стр. 85
86 Часть I. Основы
Заключительные замечания
В 1968 году Кнут (Knuth) опубликовал первый из трех томов, объединен-
ных названием The Art of Computer Programming (Искусство программирования)
[182,183,185]. Этот том стал введением в современные компьютерные алгоритмы
с акцентом на анализе времени их работы, а весь трехтомник до сих пор остается
интереснейшим и ценным пособием по многим темам, представленным в дан-
ной книге. Согласно Кнуту, слово “алгоритм” происходит от имени персидского
математика девятнадцатого века аль-Хорезми (al-Khowârizmı̂).
Ахо (Aho), Хопкрофт (Hopcroft) и Ульман (Ullman) [5] являются сторонника-
ми асимптотического анализа алгоритмов, являющегося средством сравнения их
относительной производительности. Они также популяризируют применение ре-
куррентных соотношений для описания времени работы рекурсивных алгоритмов.
Кнут [185] с энциклопедической полнотой рассмотрел многие алгоритмы сор-
тировки. Его сравнение алгоритмов сортировки включает в себя подробный ана-
лиз с точным подсчетом шагов, подобный тому, что был проведен в этой книге
для сортировки методом вставок. В ходе обсуждения Кнутом алгоритма сорти-
ровки вставкой приводится несколько вариаций этого алгоритма. Важнейшей из
них является сортировка по Шеллу (D.L. Shell), который использовал сортировку
методом вставок для упорядочения периодических последовательностей, чтобы
получить более производительный алгоритм сортировки.
В книге Кнута также описана сортировка слиянием. В книге упоминается,
что в 1938 году была создана механическая машина, способная за один проход
объединять две стопки перфокарт. По всей видимости, первым программу для сор-
тировки методом слияния (предназначенную для компьютера EDVAC) в 1945 году
разработал Джон фон Нейман (J. von Neumann), который был одним из первых
создателей теории вычислительных машин.
Ранние этапы развития в области доказательства корректности программ опи-
саны Гризом (Gries) [133], который считает, что первая статья по этой теме была
написана Науром (P. Naur). Авторство понятия инварианта цикла Гриз припи-
сывает Флойду (R.W. Floyd). В учебнике Митчелла (Mitchell) [222] описывается
прогресс, достигнутый в области доказательства корректности программ в насто-
ящее время.
Стр. 86
ГЛАВА 3
Рост функций
Стр. 87
88 Часть I. Основы
Θ-обозначения
В главе 2 было показано, что время работы алгоритма сортировки 2 методом
вставок в наихудшем случае выражается функцией T (n) = Θ n . Давайте раз-
беремся в смысле данного обозначения. Для некоторой функции g (n) запись
Θ (g (n)) обозначает множество функций
Стр. 88
Глава 3. Рост функций 89
c2 g (n) cg (n)
f (n)
f (n)
cg (n)
c1 g (n)
n n n
n0 n0 n0
f (n) = Θ( g (n)) f (n) = O( g (n)) f (n) = Ω( g (n))
а) б) в)
Стр. 89
90 Часть I. Основы
Стр. 90
Глава 3. Рост функций 91
O-обозначения
В Θ-обозначениях функция асимптотически ограничивается сверху и снизу.
Если же достаточно определить только асимптотическую верхнюю границу,
используются O-обозначения. Для данной функции g (n) обозначение O (g (n))
(произносится “о большое от g от n” или просто “о от g от n”) означает множество
функций, таких что
Стр. 91
92 Часть I. Основы
случае выражается как O n2 : “стоимость” каждой итерации во внутреннем цик-
ле ограничена сверху константой O (1), индексы i и j — числом n, а внутренний
цикл выполняется самое большее один раз для каждой из n2 пар значений i и j.
Поскольку O-обозначения описывают верхнюю границу, то в ходе их исполь-
зования для ограничения времени работы алгоритма в наихудшем случае мы по-
лучаем верхнюю границу
этой величины для любых входных данных. Таким
образом, граница O n2 для времени работы алгоритма в наихудшем случае при-
менима для времени решения задачи с любыми входными
2 данными, чего нель-
зя сказать о Θ-обозначениях. Например, оценка Θ n для времени сортировки
вставкой в наихудшем случае неприменима для произвольных входных данных.
Например, в главе 2 мы имели возможность убедиться, что если входные элемен-
ты уже отсортированы, время работы алгоритма сортировки вставкой оценивается
как Θ (n).
Если подходить формально, то неправильно говорить,
что время, необходимое
для сортировки по методу вставок, равняется O n2 , так как для данного n факти-
ческое время работы алгоритма изменяется в зависимости
2 от конкретных входных
n ”, то подразумевается, что
данных. Когда говорят, что “время работы равно O
существует функция f (n), принадлежащая O n2 и такая, что при любом вводе
размера n время решения задачи с данным вводом ограничено сверху значени-
ем функции
f (n). Это равнозначно тому, что в наихудшем случае время работы
равно O n2 .
Ω-обозначения
Аналогично тому, как в O-обозначениях дается асимптотическая верхняя гра-
ница функции, в Ω-обозначениях дается ее асимптотическая нижняя граница.
Для данной функции g (n) выражение Ω (g (n)) (произносится “омега большое от
g от n” или просто “омега от g от n”) обозначает множество функций, таких что
В качестве примера
применения этой теоремы отметим, что из соотношения
an2 + bn + c = Θ n2 для произвольных констант a, b и c, где a > 0, непосред-
Стр. 92
Глава 3. Рост функций 93
ственно следует, что an2 + bn + c = O n2 и an2 + bn + c = Ω n2 . На практике
терема 3.1 применяется не для получения асимптотических верхней и нижней
границ, как это сделано выше, а наоборот — для определения асимптотически
точной оценки с помощью асимптотических верхней и нижней границ.
Поскольку Ω-обозначения используются для определения нижней границы
времени работы алгоритма в наилучшем случае, они также дают нижнюю границу
времени работы алгоритма для произвольных входных данных.
Итак, время работы
2 алгоритма сортировки вставкой находится в пределах
между Ω (n) и O n , т.е. между линейной и квадратичной функциями от n. Бо-
лее того, эти границы охватывают асимптотику настолько плотно, насколько это
возможно: например, нижняя оценка для времени работы алгоритма сортировки
вставкой не может быть равной Ω n2 , потому что существуют входные данные,
для которых эта сортировка выполняется за время Θ (n) (когда входные элементы
уже отсортированы), что не противоречит утверждению о том, что
время работы
алгоритма сортировки вставкой в наихудшем случае равно Ω n2 , поскольку су-
ществуют
входные данные, для которых этот алгоритм работает в течение времени
Ω n2 . Когда говорят, что время работы (без каких-либо уточнений) алгоритма
равно Ω (g (n)), при этом подразумевается, что независимо от того, какие входные
данные выбраны для данного размера n, при достаточно больших n время работы
алгоритма представляет собой как минимум константу, умноженную на g (n).
Стр. 93
94 Часть I. Основы
o-обозначения
Верхняя асимптотическая граница, предоставляемая O-обозначениями, мо-
жет описывать
асимптотическое
поведение функции с разной точностью. Грани-
ца 2n2 = O n2 дает правильное представление об асимптотическом поведении
Стр. 94
Глава 3. Рост функций 95
функции, а граница 2n = O n2 его не обеспечивает. Для обозначения того, что
верхняя граница не является асимптотически точной оценкой функции, приме-
няются o-обозначения. Приведем формальное определение множества o (g (n))
(произносится как “о малое от g от n”):
ω-обозначения
По аналогии, ω-обозначения соотносятся с Ω-обозначениями так же, как o-
обозначения с O-обозначениями. С помощью ω-обозначений указывается нижний
предел, не являющийся асимптотически точной оценкой. Один из возможных
способов определения ω-обозначения следующий:
Стр. 95
96 Часть I. Основы
Сравнение функций
Асимптотические сравнения обладают некоторыми свойствами отношений
обычных действительных чисел, показанными далее. Предполагается, что функ-
ции f (n) и g (n) асимптотически положительны.
Транзитивность
Из f (n) = Θ (g (n)) и g (n) = Θ (h (n)) следует f (n) = Θ (h (n)) .
Из f (n) = O (g (n)) и g (n) = O (h (n)) следует f (n) = O (h (n)) .
Из f (n) = Ω (g (n)) и g (n) = Ω (h (n)) следует f (n) = Ω (h (n)) .
Из f (n) = o (g (n)) и g (n) = o (h (n)) следует f (n) = o (h (n)) .
Из f (n) = ω (g (n)) и g (n) = ω (h (n)) следует f (n) = ω (h (n)) .
Рефлексивность
f (n) = Θ (f (n)) ,
f (n) = O (f (n)) ,
f (n) = Ω (f (n)) .
Симметричность
f (n) = Θ (g (n)) справедливо тогда и только тогда, когда g (n) = Θ (f (n)) .
Перестановочная симметрия
f (n) = O (g (n)) справедливо тогда и только тогда, когда g (n) = Ω (f (n)) ,
f (n) = o (g (n)) справедливо тогда и только тогда, когда g (n) = ω (f (n)) .
f (n) = O (g (n)) ≈ a b,
f (n) = Ω (g (n)) ≈ a b,
f (n) = Θ (g (n)) ≈ a = b,
f (n) = o (g (n)) ≈ a < b,
f (n) = ω (g (n)) ≈ a > b.
Говорят, что функция f (n) асимптотически меньше функции g (n), если f (n) =
= o (g (n)), и асимптотически больше функции g (n), если f (n) = ω (g (n)).
Однако одно из свойств действительных чисел в асимптотических обозначе-
ниях не выполняется.
Стр. 96
Глава 3. Рост функций 97
Упражнения
3.1-1. Пусть f (n) и g (n) — асимптотически неотрицательные функции. Дока-
жите с помощью базового определения Θ-обозначений, что max(f (n),
g(n)) = Θ (f (n) + g (n)).
3.1-2. Покажите, что для любых действительных констант a и b, где b > 0,
справедливо соотношение
(n + a)b = Θ nb . (3.2)
Стр. 97
98 Часть I. Основы
Монотонность
Функция f (n) является монотонно неубывающей (monotonically increasing),
если из неравенства m n следует неравенство f (m) f (n). Аналогично,
функция f (n) является монотонно невозрастающей (monotonically decreasing),
если из неравенства m n следует неравенство f (m) f (n). Функция f (n)
монотонно возрастающая (strictly increasing), если из неравенства m < n следу-
ет неравенство f (m) < f (n) и монотонно убывающая (strictly decreasing), если
из неравенства m < n следует, что f (m) > f (n).
n/a
/b
= n/ab
, (3.4)
n/a /b = n/ab , (3.5)
a/b
(a + (b − 1)) /b, (3.6)
a/b (a − (b − 1)) /b. (3.7)
Модульная арифметика
Для любого целого числа a и любого натурального n величина a mod n пред-
ставляет собой остаток от деления a на n:
Стр. 98
Глава 3. Рост функций 99
Полиномы
Полиномом степени d от аргумента n называется функция p (n) следующе-
го вида:
d
p (n) = ai ni ,
i=0
Показательные функции
Для всех действительных чисел a > 0, m и n справедливы следующие тожде-
ства:
a0 = 1,
a1 = a,
a−1 = 1/a,
(am )n = amn ,
(am )n = (an )m ,
am an = am+n
Стр. 99
100 Часть I. Основы
где символ “!” обозначает факториал, определенный ниже в этом разделе. Для
всех действительных x справедливо следующее неравенство:
ex 1 + x (3.11)
1 + x ex 1 + x + x2 (3.12)
Стр. 100
Глава 3. Рост функций 101
Стр. 101
102 Часть I. Основы
Факториалы
Обозначение n! (читается “n факториал”) определяется для целых чисел n 0
следующим образом:
1 при n = 0,
n! =
n · (n − 1)! при n > 0,
т.е. n! = 1 · 2 · 3 · . . . · n.
Верхнюю границу факториала можно записать в виде n! nn , поскольку все
множители, которые определяют значение факториала, не превышают n. Однако
эта оценка является грубой. Более точное приближение верхней (а также нижней)
границы дает формула Стирлинга:
√ n n
1
n! = 2πn 1+Θ (3.17)
e n
где e — основание натурального логарифма. Можно доказать (см. упражнение 3.2-3),
что
n! = o (nn ) ,
n! = ω (2n ) ,
lg (n!) = Θ (n lg n) (3.18)
Функциональная итерация
Чтобы указать, что функция f (n) последовательно i раз применяется к аргу-
менту n, мы будем использовать обозначение f (i) (n). Дадим формальное опре-
деление. Пусть функция f (n) задана на множестве действительных чисел. Для
неотрицательных целых i можно дать такое рекурсивное определение:
n при i = 0,
(i)
f (n) = (i−1) .
f f (n) при i > 0.
Стр. 102
Глава 3. Рост функций 103
lg∗ 2 = 1,
lg∗ 4 = 2,
lg∗ 16 = 3,
lg∗ 65536 = 4,
lg∗ 265536 = 5.
Числа Фибоначчи
Числа Фибоначчи определяются с помощью следующего рекуррентного со-
отношения:
F0 = 0,
F1 = 1, (3.21)
Fi = Fi−1 + Fi−2 , i 2.
Таким образом, числа Фибоначчи образуют последовательность, в которой каждое
очередное число представляет собой сумму двух предыдущих:
Стр. 103
104 Часть I. Основы
φi − φi
Fi = √ , (3.23)
5
которое
можно доказать методом индукции
√ (см. упражнение 3.2-6). Поскольку
i √
φ < 1, то выполняются неравенства φ / 5 < 1/ 5 < 1/2. Таким образом, i-е
√
число Фибоначчи Fi равно φi / 5, округленному до ближайшего целого числа.
Следовательно, числа Фибоначчи возрастают как показательная функция.
Упражнения
3.2-1. Покажите, что если функции f (n) и g (n) — монотонно неубывающие,
то функции f (n) + g (n) и f (g (n)) также монотонно неубывающие.
Кроме того, если к тому же функции f (n) и g (n) — неотрицательные,
то монотонно неубывающей является также функция f (n) · g (n).
3.2-2. Докажите уравнение (3.15).
3.2-3. Докажите уравнение (3.18). Кроме того, докажите, что n! = ω (2n ) и n! =
= o (nn ).
3.2-4. Является ли функция lg n
! полиномиально ограниченной? Является ли
полиномиально ограниченной функция lg lg n
?
3.2-5. Какая из функций является асимптотически бо́льшей: lg (lg∗ n) или
lg∗ (lg n)?
3.2-6. Докажите методом математической индукции, что i-е число Фибоначчи
удовлетворяет следующему равенству:
φi − φi
Fi = √ ,
5
Стр. 104
Глава 3. Рост функций 105
Задачи
3-1. Асимптотическое поведение полиномов
Пусть p (n) представляет собой полином степени d от n:
d
p (n) = ai ni ,
i=0
Стр. 105
106 Часть I. Основы
∗ √ lg n
lg (lg∗ n) 2lg n 2 n2 n! (lg n)!
n
(3/2)n n3 lg2 n lg (n!) 22 n1/lg n
ln ln n lg∗ n n · 2n nlg lg n ln n 1
√
2lg n (lg n)lg n en 4lg n (n + 1)! lg n
√
lg∗ (lg n)
n+1
2 2 lg n n 2n n lg n 2 2
Стр. 106
Глава 3. Рост функций 107
где функция f (i) (n) должна быть корректно определена для всех i. Други-
ми словами, величина fc∗ (n) — это функция f , последовательно применя-
ющаяся столько раз, сколько это необходимо для уменьшения аргумента
до значения, не превышающего c.
Для каждой из приведенных ниже функций f (n) и констант c дайте
максимально точную оценку функции fc∗ (n).
f (n) c fc∗ (n)
а. n−1 0
б. lg n 1
в. n/2 1
г. n/2 2
√
д. n 2
√
е. n 1
ж. n1/3 2
з. n/ lg n 2
Стр. 107
108 Часть I. Основы
Заключительные замечания
Кнут (Knuth) [182] попытался выяснить происхождение O-обозначений и об-
наружил, что впервые они появились в 1892 году в учебнике Бахманна (P. Bach-
mann) по теории чисел. O-обозначения были введены в 1909 году Ландау (E. Lan-
dau) при обсуждении распределения простых чисел. Введение Ω- и Θ-обозначений
приписываются Кнуту [186], который исправил неточность популярного в литера-
туре, но технически неаккуратного применения O-обозначений как для верхней,
так и для нижней асимптотических границ. Многие продолжают использовать O-
обозначения там, где более уместны были бы Θ-обозначения. Дальнейшее об-
суждение исторического развития асимптотических обозначений можно найти
у Кнута [182, 186], а также Брассарда (Brassard) и Брейтли (Bratley) [46].
Определения асимптотических обозначений у разных авторов иногда разли-
чаются, однако в большинстве часто встречающихся ситуаций они дают согласу-
ющиеся результаты. В некоторых альтернативных случаях подразумевается, что
функции не являются асимптотически неотрицательными, поэтому ограничению
подлежит их абсолютное значение.
Равенство (3.19) было получено Роббинсом (Robbins) [260]. Другие свойства
элементарных математических функций можно найти в любом хорошем справоч-
нике по математике, например, справочнике Абрамовича (Abramowitch) и Стеган
(Stegun) [1] или Цвиллингера (Zwillinger) [320], а также в книгах по вычислитель-
ной математике, таких как книги Апостола (Apostol) [18] или Томаса (Thomas)
и Финни (Finney) [296]. В книге Кнута [182], а также Грехема (Graham), Кнута
и Паташника (Patashnik) [132] содержится множество материала по дискретной
математике, который используется в информатике.
Стр. 108
ГЛАВА 4
Рекуррентные соотношения
Как было сказано в главе 2, если алгоритм рекуррентно вызывает сам себя,
время его работы часто можно описать с помощью рекуррентного соотноше-
ния. Рекуррентное соотношение (recurrence) — это уравнение или неравенство,
описывающее функцию с использованием ее самой, но только с меньшими аргу-
ментами. Например, мы узнали, что время работы процедуры MERGE_SORT T (n)
в самом неблагоприятном случае описывается с помощью следующего рекуррент-
ного соотношения:
Θ (1) при n = 1,
T (n) = (4.1)
2T (n/2) + Θ (n) при n > 1.
где a 1, b > 1, а функция f (n) — это заданная функция; для применения этого
метода необходимо запомнить три различных случая, но после этого определение
Стр. 109
110 Часть I. Основы
Технические детали
На практике в процессе формулировки и решения рекуррентных соотноше-
ний определенные технические моменты опускаются. Так, например, есть одна
особенность, о которой часто умалчивают, — это допущение о том, что аргу-
мент функции является целочисленным. Обычно время работы T (n) алгоритма
определено лишь для целочисленных n, поскольку в большинстве алгоритмов ко-
личество входных элементов выражается целым числом. Например, рекуррентное
соотношение, описывающее время работы процедуры MERGE_SORT в наихудшем
случае, на самом деле записывается так:
Θ (1) при n = 1,
T (n) = (4.2)
T ( n/2
) + T (n/2) + Θ (n) при n > 1.
Граничные условия — еще один пример технических особенностей, которые
обычно игнорируются. Поскольку время работы алгоритма с входными данными
фиксированного размера выражается константой, то в рекуррентных соотноше-
ниях, описывающих время работы алгоритмов, для достаточно малых n обычно
справедливо соотношение T (n) = Θ (1). Поэтому для удобства граничные усло-
вия рекуррентных соотношений, как правило, опускаются и предполагается, что
для малых n время работы алгоритма T (n) является константой. Например, ре-
куррентное соотношение (4.1) обычно записывается как
T (n) = 2T (n/2) + Θ (n) , (4.3)
без явного указания значений T (n) для малых n. Причина состоит в том, что хотя
изменение значения T (1) приводит к изменению решения рекуррентного соотно-
шения, это решение обычно изменяется не более, чем на постоянный множитель,
а порядок роста остается неизменным.
Формулируя и решая рекуррентные соотношения, мы часто опускаем гранич-
ные условия, а также тот факт, что аргументами неизвестных функций являются
целые числа. Мы продвигаемся вперед без этих деталей, а потом выясняем, важ-
ны они или нет. Даже если технические детали, которые опускаются при анализе
алгоритмов, несущественны, то важно убедиться, что они не влияют на поря-
док роста решения. В подобных рассуждениях помогает опыт, а также некоторые
теоремы. В этих теоремах формулируются условия, когда упомянутые детали не
влияют на асимптотическое поведение рекуррентных соотношений, возникающих
при анализе алгоритмов (см. теорему 4.1). Однако в данной главе мы не будем
опускать технические детали, так как это позволит продемонстрировать некото-
рые тонкости, присущие методам решения рекуррентных соотношений.
Стр. 110
Глава 4. Рекуррентные соотношения 111
Стр. 111
112 Часть I. Основы
Стр. 112
Глава 4. Рекуррентные соотношения 113
Тонкие нюансы
Иногда бывает так, что можно сделать правильное предположение об асимп-
тотическом поведении решения рекуррентного соотношения, но при этом возни-
кают трудности, связанные с выполнением доказательства по методу математиче-
ской индукции. Обычно проблема заключается в том, что выбрано недостаточно
сильное предположение индукции, которое не позволяет провести подробное рас-
смотрение. Натолкнувшись на такое препятствие, пересмотрите предположение
индукции, избавившись от членов низшего порядка. При этом часто удается про-
вести строгое математическое доказательство.
Рассмотрим рекуррентное соотношение:
Можно предположить, что его решение — O (n). Попытаемся показать, что для
правильно выбранной константы c выполняется неравенство T (n) cn. Подста-
вив предполагаемое решение в рекуррентное соотношение, получим выражение
Стр. 113
114 Часть I. Основы
Остерегайтесь ошибок
Используя асимптотические обозначения, легко допустить ошибку. Например,
для рекуррентного соотношения легко “доказать”, что T (n) = O (n), предполо-
жив справедливость соотношения T (n) cn, а затем выписав цепочку соотно-
шений
T (n) 2 (c n/2) + n cn + n =
= O (n) , ← не верно!!!
Замена переменных
Иногда с помощью небольших алгебраических преобразований удается до-
биться того, что неизвестное рекуррентное соотношение становится похожим на
то, с которым мы уже знакомы. Например, рассмотрим следующее рекуррентное
соотношение: √
T (n) = 2T n + lg n,
которое выглядит довольно сложным. Однако его можно упростить, выполнив
замену переменных. Для удобства мы не станем беспокоиться об округлении
√
таких значений, как n, до целых чисел. Воспользовавшись заменой m = lg n,
получим:
T (2m ) = 2T 2m/2 + m.
Теперь можно переименовать функцию S (m) = T (2m ), после чего получается
новое рекуррентное соотношение:
S (m) = 2S (m/2) + m,
Стр. 114
Глава 4. Рекуррентные соотношения 115
Упражнения
4.1-1. Покажите, что O (lg n) является решением рекуррентного соотношения
T (n) = T ( n/2
) + 1.
4.1-2. Мы убедились, что O (n lg n) является решением рекуррентного соотно-
шения T (n) = 2T (n/2) + n. Покажите, что Ω (n lg n) также являет-
ся решением этого рекуррентного соотношения. Отсюда можно сделать
вывод, что решением рассматриваемого рекуррентного соотношения яв-
ляется Θ (n lg n).
4.1-3. Покажите, что преодолеть трудность, связанную с граничным условием
T (1) = 1 в рекуррентном соотношении (4.4), можно путем выбора дру-
гого предположения индукции, не меняя при этом граничных условий.
4.1-4. Покажите, что Θ (n lg n) является решением “точного” рекуррентного
соотношения (4.2) для сортировки слиянием.
4.1-5. Покажите, что O (n lg n) является решением рекуррентного соотношения
T (n) = 2T (n/2 + 17) + n.
√
4.1-6. Решите рекуррентное соотношение T (n) = 2T ( n) + 1 с помощью
замены переменных. Решение должно быть асимптотически точным. При
решении игнорируйте тот факт, что значения являются целыми числами.
Стр. 115
116 Часть I. Основы
Стр. 116
Глава 4. Рекуррентные соотношения 117
c ( 4n ) c ( 4n ) c ( 4n )
2 2 2
T ( 4n ) T ( 4n ) T ( 4n )
а) б) в)
cn2 cn2
c ( 4n ) c ( 4n ) c ( 4n )
2 2 2
3
16 cn2
log4 n
c ( 16n ) c ( 16n ) c ( 16n ) c ( 16n ) c ( 16n ) c ( 16n ) c ( 16n ) c ( 16n ) c ( 16n )
2 2 2 2 2 2 2 2 2
( 163 )2 cn2
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) ... T(1) T(1) T(1) Θ(nlog4 3 ) …
nlog4 3
2
г) Всего: O(n )
Рис. 4.1. Построение дерева рекурсии для рекуррентного соотношения T (n) = 3T (n/4)+
+ cn2
Стр. 117
118 Часть I. Основы
Таким образом,
для исходного рекуррентного соотношения T (n) = 3T (n/4) +
+ Θ n2 получен предполагаемый вид решения T (n) = O n2 . В рассматри-
ваемом примере коэффициенты при cn2 образуют геометрическую прогрессию,
а их сумма, согласно уравнению (A.6), ограничена сверху константой 16/13. По-
скольку вклад корня дерева в полное время работы равен cn2 , время работы корня
представляет собой некоторую постоянную часть от общего времени работы всего
дерева в целом. Другими словами, полное время работы всего дерева в основном
определяется временем работы его корня.
В действительности, если O n2 в действительности представляет собой
верхнюю границу (в чем мы вскоре убедимся), то эта граница должна быть асимп-
тотически точной оценкой. Почему? Потому что первый рекурсивный вызов
дает
вклад в общее время работы алгоритма, который выражается как Θ n2 , поэтому
нижняя граница решения рекуррентного соотношения представляет собой Ω n2 .
Теперь с помощью метода подстановок
2 проверим корректность нашей догад-
ки, т.е. убедимся, что T (n) = O
2 n — верхняя граница рекуррентного соотноше-
ния T (n) = 3T (n/4)+Θ n . Нам надо показать, что для некоторой константы
d > 0 выполняется неравенство T (n) dn2 . Используя ту же константу c > 0,
что и раньше, получаем:
Стр. 118
Глава 4. Рекуррентные соотношения 119
cn cn
c( 3n ) c( 23n ) cn
log3 2 n
...
...
Всего: O(n lg n)
Стр. 119
120 Часть I. Основы
Упражнения
4.2-1. Определите с помощью дерева рекурсии асимптотическую верхнюю гра-
ницу рекуррентного соотношения T (n) = 3T (n/2) + n. Проверьте
ответ методом подстановок.
4.2-2. Обратившись к дереву рекурсии, докажите, что решение рекуррентного
соотношения T (n) = T (n/3) + T (2n/3) + cn, где c — константа, ведет
себя как Ω (n lg n).
4.2-3. Постройте дерево рекурсии для рекуррентного соотношения T (n) =
= 4T (n/2)+cn, где c — константа, и найдите точную асимптотическую
границу его решения. Проверьте ее с помощью метода подстановок.
4.2-4. Найдите с помощью дерева рекурсии точную асимптотическую оценку
решения рекуррентного соотношения T (n) = T (n − a) + T (a) + cn, где
a 1 и c > 0 — константы.
4.2-5. Найдите с помощью дерева рекурсии точную асимптотическую оценку
решения рекуррентного соотношения T (n) = T (αn)+T ((1 − α) n)+cn,
где 0 < α < 1 и c > 0 — константы.
Стр. 120
Глава 4. Рекуррентные соотношения 121
Основная теорема
Основной метод базируется на приведенной ниже теореме.
где выражение n/b интерпретируется либо как n/b, либо как n/b
. Тогда асимп-
тотическое поведение функции T (n) можно выразить следующим образом.
1. Если f (n) = O nlogb a−ε для некоторой константы ε > 0, то T (n) =
= Θ nlogb a .
Стр. 121
122 Часть I. Основы
2. Если f (n) = Θ nlogb a , то T (n) = Θ nlogb a lg n .
log a+ε
3. Если f (n) = Ω n b для некоторой константы ε > 0, и если
af (n/b) cf (n) для некоторой константы c < 1 и всех достаточно боль-
ших n, то T (n) = Θ (f (n)).
Стр. 122
Глава 4. Рекуррентные соотношения 123
T (n) = T (2n/3) + 1,
T (n) = 3T (n/4) + n lg n
выполняются условия a = 3, b = 4, f (n) = n lg n, и nlogb a = nlog4 3 = O n0.793 .
Поскольку f (n) = Ω nlog4 3+ε , где ε ≈ 0.2, применяется случай 3 (если удастся
показать выполнение условия регулярности для функции f (n)). При достаточно
больших n условие af (n/b) = 3 (n/4) lg (n/4) (3/4) n lg n = cf (n) выполняет-
ся при c = 3/4. Следовательно, согласно случаю 3, решение этого рекуррентного
соотношения — T (n) = Θ (n lg n).
К рекуррентному соотношению
T (n) = 2T (n/2) + n lg n
основной метод неприменим, несмотря на то, что оно имеет надлежащий вид:
a = 2, b = 2, f (n) = n lg n, и nlogb a = n. Может показаться, что к нему применим
случай 3, поскольку функция f (n) = n lg n асимптотически больше, чем nlogb a =
= n. Однако проблема заключается в том, что данная функция не полиномиально
больше. Отношение f (n)/nlogb a = (n lg n)/n = lg n асимптотически меньше
функции nε для любой положительной константы ε. Следовательно, рассматрива-
емое рекуррентное соотношение находится “в промежуточном состоянии” между
случаями 2 и 3. (См. упражнение 4.4-2.)
Упражнения
4.3-1. С помощью основной теоремы найдите точные асимптотические грани-
цы следующих рекуррентных соотношений.
а) T (n) = 4T (n/2) + n.
б) T (n) = 4T (n/2) + n2 .
в) T (n) = 4T (n/2) + n3 .
4.3-2. Рекуррентное соотношение T (n) = 7T (n/2) + n2 описывает время ра-
боты алгоритма A. Время работы альтернативного алгоритма A выража-
ется рекуррентным соотношением T (n) = aT (n/4) + n2 . Чему равно
наибольшее целое значение a, при котором алгоритм A работает асимп-
тотически быстрее, чем алгоритм A.
Стр. 123
124 Часть I. Основы
Стр. 124
Глава 4. Рекуррентные соотношения 125
В этом
случае
наилучшей верхней границей, как легко доказать, является T (n) =
= O n2 . Во избежание подобных ошибок, мы никогда не будем использовать
асимптотические обозначения на ограниченной области определения функции,
если только из контекста не будет вполне очевидно, что именно мы собираемся
делать.
Стр. 125
126 Часть I. Основы
f (n) f (n)
f ( n b) f ( n b) f ( n b) af (n b )
a a a
log b n
2
f (n b 2 ) f (n b 2 ) ... f (n b 2 ) f (n b 2 ) f (n b 2 ) ... f (n b 2 ) f (n b 2 ) f (n b 2 ) ... f (n b 2 ) a 2 f (n b )
a a a a a a a a a
... ... ... ... ... ... ... ... ... ...
Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) ... Θ(l) Θ(l) Θ(l) Θ(nlogb a )
nlogb a
Всего: Θ(nlogb a ) + ∑ a j f (n b j )
Стр. 126
Глава 4. Рекуррентные соотношения 127
logb n−1
g (n) = aj f n/bj , (4.7)
j=0
logb n−1
= nlogb a−ε (bε )j =
j=0
bε logb n − 1
logb a−ε
=n =
bε − 1
ε
logb a−ε n − 1
=n .
bε − 1
Стр. 127
128 Часть I. Основы
Как и в случае 1, оценим сумму, стоящую под знаком Θ, но на этот раз геомет-
рическая прогрессия не получается. В самом деле, нетрудно убедиться, что все
слагаемые суммы одинаковы:
logb n−1 n logb a logb n−1
a j
j logb a
a =n =
bj blogb a
j=0 j=0
logb n−1
logb a
=n 1=
j=0
= nlogb a logb n.
доказывающее случай 2.
Случай 3 доказывается аналогично. Поскольку функция f (n) фигурирует
в определении (4.7) функции g (n), и все слагаемые функции g (n) неотрица-
тельные, можно заключить, что g (n) = Ω (f (n)) для точных степеней числа b.
Согласно нашему предположению, для некоторой константы c < 1 соотношение
af (n/b) cf (n) справедливо для n b, откуда f (n/b) (c/a) f (n).
всех
Итерируя j раз, получаем, что f n/bj (c/a)j f (n), или, что то же самое,
aj f n/bj cj f (n). После подстановки в уравнение (4.7) и некоторых упроще-
ний получаем геометрическую прогрессию. В отличие от прогрессии из случая 1,
члены данной прогрессии убывают (при рассмотрении приведенных преобразо-
Стр. 128
Глава 4. Рекуррентные соотношения 129
Таким образом, можно прийти к заключению, что g (n) = Θ (f (n)) для точных
степеней числа b. Этим доказательством случая 3 завершается доказательство
леммы.
в случае 2 —
T (n) = Θ nlogb a + Θ nlogb a lg n =
= Θ nlogb a lg n ,
Стр. 129
130 Часть I. Основы
а в случае 3, поскольку f (n) = Ω nlogb a+ε —
T (n) = Θ nlogb a + Θ (f (n)) =
= Θ (f (n)) .
T (n) = aT ( n/b
) + f (n) (4.10)
n,
n/b
,
n/b
/b
, .
n/b
/b
/b
,
..
.
Стр. 130
Глава 4. Рекуррентные соотношения 131
f (n) f (n)
a a a
log b n
2
f (n2 ) f (n2 ) ... f (n2 ) f (n2 ) f (n2 ) ... f (n2 ) f (n2 ) f (n2 ) ... f (n2 ) a 2 f (n b )
a a a a a a a a a
... ... ... ... ... ... ... ... ... ..
.
Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) Θ(l) ... Θ(l) Θ(l) Θ(l) Θ(nlogb a )
Θ(nlogb a )
Âñåãî: Θ(nlogb a ) + ∑ a j f (n b j )
n0 n,
n
n1 + 1,
b
n 1
n2 2 + + 1,
b b
n 1 1
n3 3 + 2 + + 1,
b b b
..
.
n b n b n b b
nlogb n < + < log n−1 + = + = b+ = O (1) ,
blogb n b−1 b b b−1 n/b b − 1 b−1
Стр. 131
132 Часть I. Основы
log
b n−1
того же вида, что и уравнение (4.6) (с тем отличием, что здесь n — произвольное
целое число, а не точная степень числа b).
Теперь можно приступить к оценке суммы
logb n−1
g (n) = aj f (nj ), (4.14)
j=0
Стр. 132
Глава 4. Рекуррентные соотношения 133
доказать справедливость границы f (nj ) = O nlogb a−ε . Это делается аналогично
доказательству в случае 2, хотя алгебраические выкладки при этом оказываются
несколько более сложными.
Итак, мы доказали соблюдение верхних границ в основной теореме для всех
целых n. Соблюдение нижних границ доказывается аналогично.
Упражнения
4.4-1. Приведите простое и точное выражение для nj в уравнении (4.12) для
случая, когда b — положительное целое число (а не произвольное дей-
ствительное).
4.4-2. Покажите, что если выполняется соотношение f (n) = Θ nlogb a lgk n ,
где k 0, то решение
основного рекуррентного соотношения —T (n) =
= Θ nlogb a lgk+1 n . Для простоты рассмотрите только случай целых
степеней b.
4.4-3. Покажите, что в случае 3 основной теоремы одно из условий излишнее
в том плане, что из условия регулярности af (n/b) cf (n) для некото-
рой константы
log ca+ε
< 1 следует, что существует константа ε > 0, такая что
f (n) = Ω n b .
Задачи
4-1. Примеры рекуррентных соотношений
Определите верхнюю и нижнюю асимптотические границы функции
T (n) для каждого из представленных ниже рекуррентных соотношений.
Считаем, что при n 2T (n) — константа. Попытайтесь сделать эту
оценку как можно более точной и обоснуйте свой ответ.
а) T (n) = 2T (n/2) + n3 .
б) T (n) = T (9n/10) + n.
в) T (n) = 16T (n/4) + n2 .
г) T (n) = 7T (n/3) + n2 .
д) T (n) = 7T (n/2) + n2 .
√
е) T (n) = 2T (n/4) + n.
ж) T (n) = T (n − 1) + n.
√
з) T (n) = T ( n) + 1.
4-2. Поиск отсутствующего целого числа
Массив A [1..n] содержит все целые числа от 0 до n за исключением
одного. Отсутствующее число можно легко определить за время O (n),
Стр. 133
134 Часть I. Основы
Стр. 134
Глава 4. Рекуррентные соотношения 135
где √
1+ 5
φ= = 1.61803 . . .
2
и √
1 − 5
φ = = −0.61803 . . . .
2
∞
в) Покажите, что F (z) = √1 φi−φ i z i .
5
i=0
√
г) Докажите, что Fi = φi /
5 (округленное до ближайшего
целого) для
всех i > 0. (Указание: обратите внимание на то, что φ < 1.)
Стр. 135
136 Часть I. Основы
1
СБИС — это аббревиатура от “сверхбольшие интегральные схемы” (микросхемы, созданные по
технологии, которая используется при производстве большинства современных микропроцессоров).
Стр. 136
Глава 4. Рекуррентные соотношения 137
Другими словами, при любом выборе двух срок и двух столбцов из масси-
ва Монжа (при этом элементы массива на пересечении выбранных строк
и столбцов образуют прямоугольник) сумма элементов в левом верхнем
и правом нижнем углах полученного прямоугольника не превышает сум-
му элементов в левом нижнем и правом верхнем его углах. Приведем
пример массива Монжа:
10 17 13 28 23
17 22 16 29 23
24 28 22 34 24
11 13 6 17 7
45 44 32 37 23
36 33 19 21 6
75 66 51 53 34
A [i, j] + A [i + 1, j + 1] A [i, j + 1] + A [i + 1, j] .
37 23 22 32
21 6 7 10
53 34 30 31
32 13 9 6
43 21 15 8
Стр. 137
138 Часть I. Основы
Заключительные замечания
Рекуррентные соотношения изучались еще с 1202 года, со времен Леонар-
до Фибоначчи (L. Fibonacci). А. де Муавр (A. De Moivre) впервые использовал
метод производящих функций (см. задачу 4-5) для решения рекуррентных соот-
ношений. Основной метод был принят на вооружение после появления работы
Бентли (Bentley), Хакена (Haken) и Сакса (Saxe) [41], в которой был предложено
расширение метода, обоснованного в упражнении 4.4-2. Кнут (Knuth) и Лью (Liu)
[205] показали, каким образом можно решать линейные рекуррентные соотноше-
ния с использованием производящих функций. Подробное обсуждение методов
решения рекуррентных соотношений можно найти в книгах Пурдома (Purdom)
и Брауна (Brown) [252], а также Грехема (Graham), Кнута и Паташника (Patash-
nik) [132].
Некоторые исследователи, в число которых входят Акра (Akra) и Баззи (Bazzi)
[13], Роура (Roura) [262] и Верма (Verma) [306], предложили методы решения
более общих рекуррентных соотношений для алгоритмов разбиения. Ниже пред-
ставлены результаты Акра и Баззи. Их метод подходит для решения рекуррентных
соотношений вида
k
T (n) = ai T (n/bi ) + f (n) , (4.15)
i=1
Стр. 138
Глава 4. Рекуррентные соотношения 139
Стр. 139
ГЛАВА 5
Вероятностный анализ
и рандомизированные алгоритмы
Стр. 140
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 141
Стр. 141
142 Часть I. Основы
Вероятностный анализ
Вероятностный анализ — это анализ задачи, при котором используются ве-
роятности тех или иных событий. Чаще всего он используется при определении
времени работы алгоритма. Иногда такой анализ применяется и для оценки других
величин, таких как стоимость найма в процедуре HIRE_ASSISTANT. Для проведения
вероятностного анализа необходимо располагать знаниями (или сделать предпо-
ложение) о распределении входных данных. При этом в ходе анализа алгоритма
вычисляется математическое ожидание времени его работы. На эту величину вли-
яет распределение входных величин, поэтому производится усреднение времени
работы по всем возможным входным данным.
Делая предположение о распределении входных величин, нужно быть очень
осторожным. В некоторых задачах такие предположения вполне оправданны и поз-
воляют воспользоваться вероятностным анализом как методом разработки эффек-
тивных алгоритмов и как средством для более глубокого понимания задачи. В дру-
гих задачах разумное описание распределения входных величин не удается, и в
таких случаях вероятностный анализ неприменим.
В задаче о найме сотрудника можно предположить, что претенденты приходят
на собеседование в случайном порядке. Что это означает в контексте рассмат-
риваемой задачи? Предполагается, что любых двух кандидатов можно сравнить
и решить, кто из них квалифицированнее, т.е. в принципе всех кандидатов мож-
но расположить в определенном порядке. (Определение полностью упорядочен-
ных множеств приведено в приложении Б.) Таким образом, каждому кандидату
можно присвоить уникальный порядковый номер от 1 до n. Назовем операцию
присвоения порядкового номера i-му претенденту rank (i) и примем соглаше-
ние, что более высокий ранг соответствует специалисту с более высокой квали-
фикацией. Упорядоченное множество rank (1) , rank (2) , . . . , rank (n) является
перестановкой множества 1, 2, . . . , n. Утверждение, что кандидаты приходят на
собеседование в случайном порядке, эквивалентно утверждению, что вероятность
любого порядка рангов одинакова и равна количеству перестановок чисел от 1 до
n, т.е. n!. Другими словами, ранги образуют случайную равновероятную пере-
Стр. 142
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 143
Рандомизированные алгоритмы
Чтобы провести вероятностный анализ, нужно иметь некоторые сведения
о распределении входных данных. Во многих случаях мы знаем о них очень ма-
ло. Даже если об этом распределении что-то известно, может случиться так, что
знания, которыми мы располагаем, нельзя численно смоделировать. Несмотря на
это вероятность и случайность часто можно использовать в качестве инструмен-
та при разработке и анализе алгоритмов, путем придания случайного характера
части алгоритма.
В задаче о найме сотрудника все выглядит так, как будто кандидатов присы-
лают на собеседование в случайном порядке, но на самом деле у нас нет никакой
возможности узнать, так ли это на самом деле. Поэтому, чтобы разработать рандо-
мизированный алгоритм для этой задачи, необходимо повысить степень контроля
над порядком поступления претендентов на должность. Внесем в модель неболь-
шие изменения. Допустим, бюро по трудоустройству подобрало n кандидатов.
Работодатель договаривается, чтобы ему заранее прислали список кандидатов,
и каждый день самостоятельно случайным образом выбирает, с кем из претен-
дентов проводить собеседование. Несмотря на то, что работодатель по-прежнему
ничего не знает о претендентах на должность, задача существенно изменилась.
Теперь не нужно гадать, будет ли очередность кандидатов случайной; вместо это-
го мы взяли этот процесс под свой контроль и сами сделали случайным порядок
проведения собеседований.
В общем случае алгоритм называется рандомизированным (randomized), если
его поведение определяется не только набором входных величин, но и значе-
ниями, которые выдает генератор случайных чисел. Будем предполагать, что
в нашем распоряжении имеется генератор дискретных случайных чисел RANDOM.
При вызове процедура RANDOM(a, b) возвращает целое число, принадлежащее
интервалу от a до b и равномерно распределенное в этом интервале. Например,
RANDOM(0, 1) с вероятностью 1/2 выдает 0 и с той же вероятностью — 1. В ре-
зультате вызова RANDOM(3, 7) числа 3, 4, 5, 6 и 7 возвращаются с вероятностью
1/5. Вероятность возврата процедурой RANDOM любого целого числа не зависит
от того, какие числа были возвращены в предыдущем вызове этой процедуры.
Процедуру RANDOM можно представить в виде рулетки с (b − a + 1) делениями.
На практике большинство сред программирования предоставляют в распоряже-
ние программиста генератор псевдослучайных чисел, т.е. детерминированный
алгоритм, который возвращающий числа, которые ведут себя при статистическом
анализе как случайные.
Стр. 143
144 Часть I. Основы
Упражнения
5.1-1. Покажите, что из предположения о том, что в строке 4 алгоритма HIRE_
ASSISTANT всегда можно определить, какой кандидат лучше, следует, что
мы знаем общий порядок рангов кандидатов.
5.1-2. Опишите реализацию процедуры RANDOM(a, b), которая может исполь-
зовать только один вызов — процедуры RANDOM(0, 1). Чему равно ма-
тематическое ожидание времени работы вашей реализации и как оно
зависит от a и b?
5.1-3. Предположим, что нам надо выводить 0 и 1 с вероятностью 50%. В на-
шем распоряжении имеется процедура BIASED_RANDOM, которая с ве-
роятностью p выдает 0, и с вероятностью 1 − p — число 1; значение
p нам неизвестно. Сформулируйте алгоритм, использующий в качестве
подпрограммы процедуру BIASED_RANDOM и возвращающий равномер-
но распределенные числа 0 и 1, т.е. вероятность вывода каждого из них
равна 50%. Чему равно математическое ожидание времени работы такой
процедуры и как оно зависит от p?
Стр. 144
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 145
E [XH ] = E [I {H}] =
= 1 · Pr {H} + 0 · Pr {T } =
= 1 · (1/2) + 0 · (1/2) =
= 1/2.
Таким образом, математическое ожидание того, что выпадет орел, равно 1/2. Как
показано в приведенной ниже лемме, математическое ожидание индикаторной
случайной величины, связанной с событием A, равно вероятности этого события.
E [XA ] = E [I {A}] =
= 1 · Pr {A} + 0 · Pr Ā =
= Pr {A} .
n
X= Xi .
i=1
Стр. 145
146 Часть I. Основы
Нам надо вычислить математическое ожидание выпадения орла. Для этого при-
меним операцию математического ожидания к обеим частям приведенного выше
уравнения: n
E [X] = E Xi .
i=1
Стр. 146
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 147
n
E [X] = x Pr {X = x},
x=1
Стр. 147
148 Часть I. Основы
Упражнения
5.2-1. Чему равна вероятность того, что в процедуре HIRE_ASSISTANT будет на-
нят ровно один кандидат, если предполагается, что собеседование с кан-
дидатами проводится в случайном порядке?
5.2-2. Чему равна вероятность того, что в процедуре HIRE_ASSISTANT будет
нанято ровно два кандидата, если предполагается, что собеседование
с кандидатами проводится в случайном порядке? Чему равна вероятность
того, что будет нанято ровно n кандидатов?
5.2-3. Вычислите математическое ожидание суммы очков на n игральных ко-
стях с помощью индикаторных случайных величин.
5.2-4. Решите с помощью индикаторных случайных величин задачу, известную
как задача о гардеробщике. Каждый из n посетителей ресторана сдает
свою шляпу в гардероб. Гардеробщик возвращает шляпы случайным
образом. Чему равно математическое ожидание количества посетителей,
получивших обратно свои собственные шляпы?
Стр. 148
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 149
Стр. 149
150 Часть I. Основы
Стр. 150
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 151
При сравнении леммы 5.2 и леммы 5.3 проявляется различие между вероят-
ностным анализом и рандомизированными алгоритмами. В лемме 5.2 делается
предположение о виде входных данных. В лемме 5.3 такие предположения от-
сутствуют, хотя для рандомизации входных величин требуется дополнительное
время. В оставшейся части настоящего раздела обсуждаются некоторые вопросы,
связанные с входными данными, которые подверглись случайной перестановке.
Стр. 151
152 Часть I. Основы
Стр. 152
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 153
Стр. 153
154 Часть I. Основы
Стр. 154
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 155
Упражнения
5.3-1. У профессора возникли возражения против инварианта цикла, использу-
ющегося при доказательстве леммы 5.5. Он сомневается, что этот инвари-
ант выполняется перед первой итерацией. Согласно его доводам, пустой
подмассив не содержит никаких размещений из 0 элементов, поэтому
вероятность того, что в таком подмассиве находится то или иное разме-
щение, должна быть равна 0. Из этих рассуждений следует, что инвариант
цикла перед первой итерацией не выполняется. Перепишите процедуру
RANDOMIZE_IN_PLACE таким образом, чтобы связанный с нею инвари-
ант цикла перед первой итерацией применялся к непустому подмассиву,
и соответствующим образом модифицируйте доказательство леммы 5.5.
5.3-2. Профессор решил разработать алгоритм, в результате выполнения кото-
рого получались бы все случайные перестановки, кроме тождественной.
Он предложил такую процедуру:
PERMUTE_WITHOUT_IDENTITY(A)
1 n ← length[A]
2 for i ← 1 to n − 1
3 do Обменять A[i] ↔ A[RANDOM(i + 1, n)]
Добьется ли профессор поставленной цели с помощью этого кода?
5.3-3. Предположим, что вместо того, чтобы менять местами элемент A [i] со
случайно выбранным элементом из подмассива A [i..n], мы меняем его
местами с любым случайно выбранным элементом массива A:
PERMUTE_WITH_ALL(A)
1 n ← length[A]
2 for i ← 1 to n
3 do Обменять A[i] ↔ A[RANDOM(1, n)]
Получится ли в результате выполнения этого кода равномерная случай-
ная перестановка? Обоснуйте ваш ответ.
Стр. 155
156 Часть I. Основы
PERMUTE_BY_CYCLIC(A)
1 n ← length[A]
2 offset ← RANDOM(1, n)
3 for i ← 1 to n
4 do dest ← i + offset
5 if dest > n
6 then dest ← dest −n
7 B[dest] ← A[i]
8 return B
Стр. 156
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 157
!
n
Bk = Ai ,
i=1
где Ai — событие, состоящее в том, что день рождения i-го человека отличается
от дня рождения j-го человека для всех i < j. Поскольку мы можем записать
Стр. 157
158 Часть I. Основы
Стр. 158
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 159
Согласно уравнению (5.7) вероятность того, что дни рождения двух людей совпа-
дают, равна 1/n, поэтому, в соответствии с леммой 5.1, получаем:
k
k
X= Xij .
i=1 j=i+1
Стр. 159
160 Часть I. Основы
b
E [ni ] = .
b−i+1
Пользуясь линейностью математического ожидания, получаем:
b
b
b
b b
1
E [n] = E ni = E [ni ] = =b = b (ln b + O (1)) .
b−i+1 i
i=1 i=1 i=1 i=1
Стр. 160
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 161
Для k = 2 lg n
можно записать
Pr Ai,2lg n = 1/22lg n 1/22 lg n = 1/n2 ,
Стр. 161
162 Часть I. Основы
n
2lg n −1
n
E [L] = j Pr {Lj } = j Pr {Lj } + j Pr {Lj } <
j=0 j=0 j=2lg n
2lg n −1
n
< (2 lg n
) Pr {Lj } + n Pr {Lj } =
j=0 j=2lg n
2lg n −1
n
= 2 lg n
Pr {Lj } + n Pr {Lj } <
j=0 j=2lg n
< 2 lg n
· 1 + n · (1/n) = O (lg n) .
Стр. 162
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 163
n
Pr {Lj } 1 − O (1/n) . (5.12)
j=(lg n)/2+1
Стр. 163
164 Часть I. Основы
Стр. 164
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 165