Author: Седжвик Р.
Tags: компьютерные технологии языки программирования трансляторы программирование алгоритмы структуры данных
ISBN: 5-93772-083-0
Year: 2003
Text
РОБЕРТ СЕДЖВИК Принстонский Университет
третья редакция
ЧШй
Роберт Седжвик обладает настоящим талантом просто и
доступно объяснять сложнейшие вещи. Использование
реальных программ, занимающих менее одной страницы
которые к тому же легко понять - вот одно из
несомненных достоинств книги. Рисунки, программы и
таблицы оказывают существенную помощь в усвоении
материала и выгодно отличают эту книгу от других.
- Уильям А. Вард
Университет Южной Алабамы
A ADDISON-WESLEY
▼▼ Pearson Education
DiaSofit
Фундаментальные
алгоритмы
Роберт Седжвик
Фундаментальные алгоритмы на С
Части 1-5
Анализ / Структуры данных / Сортировка /
Поиск / Алгоритмы на графах
DiaSoft
Москва • Санкт-Петербург • Киев
2003
in С
PARTS 1-5
FUNDAMENTALS
DATA STRUCTURES
SORTING
SEARCHING
GRAPH ALGORITHMS
Robert Sedgewick
Pг i n с с t о п. U и i v с rs i i v
Л AD DI SON-WESLEY
Boston • San Francisco • New York • Toronto • Montreal
London • Munich • Paris • Madrid
Capetown • Sydney • Tokyo • Singapore • Mexico City
Фундаментальные
алгоритмы
ЧАСТИ 1-5
АНАЛИЗ
СТРУКТУРЫ ДАННЫХ
СОРТИРОВКА
ПОИСК
АЛГОРИТМЫ НА ГРАФАХ
Роберт Седжвик
т
ж DiaSoft
Москва • Санкт-Петербург • Киев
2003
ББК 32.973.2
УДК 681.3.06(075)
С 88
Седжвик Роберт
С 88 Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/
Алгоритмы на графах: Пер. с англ./Роберт Седжвик. - СПб: ООО «ДиаСофтЮП»,
2003.- 1136 с.
ISBN 5-93772-083-0
Эта книга посвящена глубокому исследованию всех основополагающих концепций и алгорит¬
мов, которые, несомненно, относятся к категории “вечных”. Тщательным образом проштудировав
их, вы получите знания, которые никогда не устареют и которыми вы будете пользоваться всегда.
Краткость, точность, выверенность, актуальность, изобилие примеров и учебных заданий - вот
лишь небольшой перечень очевидных достоинств книги. Иллюстрация алгоритмов на одном из
наиболее эффективных языков программирования С лишний раз подчеркивает их популярность и
“вечность”. Подробно рассматривается широчайший спектр фундаментальных алгоритмов и алго¬
ритмов на графах. Большое внимание уделяется рабочим характеристикам алгоритмов, а также их
математическому выводу.
Книгу можно использовать в качестве курса лекций (как студентами, так и преподавателями),
справочного пособия или просто “романа”, получая при этом ни с чем не сравнимое удовольствие.
»
ББК 32.973.2
Научное издание
Роберт Седжвик
ФУНДАМЕНТАЛЬНЫЕ АЛГОРИТМЫ НА С
Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах
Заведующий редакцией С.Н.Козлов
Научный редактор Ю.Н.Артемепко
Верстка Т.Н.Артеменко
Главный дизайнер О. А.Шадрин
H/K
ООО «ДиаСофтЮП», 196105, Санкт-Петербург, пр. Ю.Гагарина, д. 1,ком. 108.
Лицензия №000328 от 9 декабря 1999 г.
Сдано в набор 10.01.2003. Подписано в печать 28.02.2003. Формат 70x100/16.
Бумага типографская. Гарнитура Таймс. Печать офсетная. Печ.л. 71.
Тираж 2000 экз. Заказ № 98
Отпечатано с готовых диапозитивов в ФГУП ордена Трудового Красного Знамени «Техническая книга»
Министерства Российской Федерации по делам печати, телерадиовещания и средств массовых коммуникаций
198005, Санкт-Петербург, Измайловский пр., 29.
Authorized translation from the English language edition, entitled ALGORITHMS IN C, PARTS 1-5 (BUNDLE):
FUNDAMENTALS, DATA STRUCTURES, SORTING, SEARCHING, AND GRAPH ALGORITHMS, 3rd Edition by
SEDGEWICK, ROBERT, published by Pearson Education, Inc, publishing as Addison Wesley,
Copyright © 2002
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including
photocopying, recording or by any information storage retrieval system, without permission from the Pearson Education, Inc.
Russian language edition published by DiaSoft LTD.,
Copyright © 2003
Лицензия предоставлена издательством Addison Wesley. (Pearson Education, Inc.)
Все права зарезервированы, включая право на полное или частичное воспроизведение в какой бы то ни было форме.
ISBN 5-93772-083-0 (рус.) © Перевод на русский язык. ООО «ДиаСофтЮП», 2003
ISBN 0-201-31452-5 (англ.) © Addison Wesley, 2002
ISBN 0-201-31663-3 (англ.) © Addison Wesley, 2002
© Оформление. ООО «ДиаСофтЮП», 2003
Гигиеническое заключение № 77.99.6.953.П.438.2.99 от 04.02.1999
Оглавление
Часть 1. Анализ 17
Глава 1. Введение 18
1.1 Алгоритмы 19
1.2 Пример задачи связности 21
1.3 Алгоритмы объединения-поиска 25
1.4 Перспективы 36
1.5 Обзор тем 38
Глава 2. Принципы анализа алгоритмов 40
2.1 Реализация и эмпирический анализ 41
2.2 Анализ алгоритмов 45
2.3 Рост функций 48
2.4 О-нотация 54
2.5 Простейшие рекурсии 59
2.6 Примеры анализа алгоритмов 63
2.7 Гарантии, предсказания и ограничения 68
Ссылки к части 1 72
Часть 2. Структуры данных 74
Глава 3. Элементарные структуры данных 75
3.1 Строительные блоки 76
3.2 Массивы 86
3.3 Связные списки 92
3.4 Обработка простых списков 98
3.5 Распределение памяти под списки 106
3.6 Строки 109
3.7 Составные структуры данных 114
Глава 4. Абстрактные типы данных 124
4.1 Абстрактные объекты и коллекции объектов 128
4.2 АТД стека магазинного типа 131
4.3 Примеры клиентских программ, использующих АТД стека 134
4.4 Реализации АТД стека 140
4.5 Создание нового АТД 144
4.6 Очереди FIFO и обобщенные очереди 147
4.7 Повторяющиеся и индексные элементы 155
4.8 АТД первого класса 160
4.9 Пример использования АТД в приложениях 170
4.10 Перспективы 175
6
Фундаментальные алгоритмы на С. Части 1—5
Глава 5. Рекурсия и деревья 177
5.1 Рекурсивные алгоритмы 178
5.2 Разделяй и властвуй 185
5.3 Динамическое программирование 199
5.4 Деревья 206
5.5 Математические свойства бинарных деревьев 215
5.6 Обход дерева 218
5.7 Рекурсивные алгоритмы бйнарных деревьев , 224
5.8 Обход графа 229
5.9 Перспективы 235
Ссылки к части 2 236
Часть 3. Сортировка 237
Глава 6. Элементарные методы сортировки 238
6.1 Правила игры 240
6.2 Сортировка выбором 246
6.3 Сортировка вставками 247
6.4 Пузырьковая сортировка 250
6.5 Характеристики производительности элементарных методов сортировки 252
6.6 Сортировка методом Шелла 258
6.7 Сортировка других типов данных 267
6.8 Сортировка по индексам и указателям 271
6.9 Сортировка связных списков 278
6.10 Метод распределяющего подсчета 282
Глава 7. Быстрая сортировка 285
7.1 Базовый алгоритм 286
7.2 Характеристики производительности быстрой сортировки 291
7.3 Размер стека 295
7.4 Подфайлы небольших размеров 299
7.5 Метод разделения с вычислением медианы из трех элементов 302
7.6 Дублированные ключи 307
7.7 Строки и векторы 310
7.8 Выборка 312
Глава 8. Слияние и сортировка слиянием 316
8.1 Двухпутевое слияние 318
8.2 Абстрактное обменное слияние 320
8.3 Нисходящая сортировка слиянием 322
8.4 Усовершенствования базового алгоритма 325
8.5 Восходящая сортировка слиянием 328
8.6 Производительность сортировки слиянием 331
8.7 Реализация сортировки слиянием, ориентированная на связные списки 335
8.8 Возврат к рекурсии 338
Оглавление
Глава 9. Очереди по приоритетам и пирамидальная сортировка 340
9.1 Элементарные реализации 344
9.2 Пирамидальная структура данных 347
9.3 Алгоритмы для сортирующих деревьев 349
9.4 Пирамидальная сортировка 356
9.5 Абстрактный тип данных очереди по приоритетам 363
9.6 Очередь по приоритетам для индексных элементов 368
9.7 Биномиальные очереди 372
Глава 10. Поразрядная сортировка 383
10.1 Биты, байты и слова 385
10.2 Бинарная быстрая сортировка 388
10.3 Поразрядная сортировка*MSD 394
10.4 Трехпутевая поразрядная быстрая сортировка 402
10.5 Поразрядная сортировка LSD 406
10.6 Рабочие характеристики поразрядных сортировок 410
10.7 Сортировки с сублинейным временем выполнения 414
Глава 11. Методы сортировки специального назначения 419
11.1 Четно-нечетная сортировка слиянием Бэтчера 421
11.2 Сети сортировки 426
11.3 Внешняя сортировка 434
11.4 Различные реализации сортировки слиянием 441
11.5 Параллельная процедура сортировки слиянием 448
Ссылки к части 3 453
Часть 4. Поиск 455
Глава 12. Таблицы символов и деревья бинарного поиска 456
12.1 Абстрактный тип данных таблицы символов 458
12.2 Поиске использованием индексации по ключам 463
12.3 Последовательный поиск 466
12.4 Бинарный поиск 472
12.5 Деревья бинарного поиска 477
12.6 Характеристики производительности деревьев бинарного поиска 483
12.7 Реализация индексов при помощи таблиц символов 486
12.8 Вставка в корень в деревьях бинарного поиска 490
12.9 Реализации других функций АТД с помощью BST-дерева 495
Глава 13. Сбалансированные деревья 504
13.1 Рандомизированные BST-деревья 508
13.2 Расширенные деревья бинарного поиска 514
13.3 Нисходящие 2-3-4-деревья 520
13.4 Красно-черные, или RB-деревья 525
13.5 Списки пропусков 535
13.6 Характеристики производительности 543
О Фундаментальные алгоритмы на С. Части 1—5
Глава 14. Хеширование 547
14.1 Хеш-функции 548
14.2 Раздельное связывание 558
14.3 Линейное зондирование 562
14.4 Двойное хеширование 567
14.5 Динамические хеш-таблицы 573
14.6 Перспективы 577
Глава 15. Поразрядный поиск 582
15.1 Деревья цифрового поиска 583
15.2 Trie-д еревья 588
15.3 Patricia-деревья 597
15.4 Многопутевые trie-деревья и TST-деревья *. 605
15.5 Алгоритмы индексирования текстовых строк 652
Глава 16. Внешний поиск 627
16.1 Правила игры 629
16.2 Индексно-последовательный доступ 631
16.3 В-деревья 634
16.4 Расширяемое хеширование 646
16.5 Перспективы 657
Ссылки к части 4 660
Предметный указатель к частям 1-4 663
Часть 5. Алгоритмы на графах 673
Глава 17. Свойства и типы графов 674
17.1 Глоссарий 678
17.2 АТД графа 687
17.3 Представление графа в виде матрицы смежности 691
17.4 Представление графа в виде списка смежных вершин 697
17.5 Вариации, расширения и затраты 700
17.6 Генераторы графов 709
17.7 Простые, эйлеровы и гамильтоновы пути 720
17.8 Задачи обработки графов 734
Глава 18. Поиск на графах 744
18.1 Исследование лабиринта 745
i 8.2 Поиск в глубину 750
18.3 АТД-функции поиска на графе 755
18.4 Свойства лесов DFS 760
18.5 Алгоритмы DFS 767
18.6 Отделимость и бисвязность 774
18.7 Поиск в ширину 782
18.8 Обобщенный поиск на графах 792
18.9 Анализ алгоритмов на графах 800
Оглавление
Глава 19. Орграфы и ориентированные ациклические графы 807
19.1 Глоссарий и правила игры 810
19.2 Анатомия поиска DFS в орграфах 819
19.3 Достижимость и транзитивное замыкание 828
19.4 Отношения эквивалентности и частичные порядки 840
19:5 Графы DAG 844
19.6 Топологическая сортировка 849
19.7 Достижимость в графе DAG 859
19.8 Сильные компоненты в орграфах 862
19.9 Еще раз о транзитивном замыкании 872
19.10 Перспективы 876
Глава 20. Минимальные остовные деревья 880
20.1 Представления 883
20.2 Принципы, положенные в основу алгоритмов построения дерева MST 889
20.3 Алгоритм Прима и поиск по приоритету 896
20.4 Алгоритм Крускала 907
20.5 Алгоритм Борувки 913
20.6 Сравнения и усовершенствования 916
20.7 Эвклидово дерево MST 922
Глава 21. Кратчайшие пути 925
21.1 Основные принципы 933
21.2 Алгоритм Дейкстры 938
21.3 Все кратчайшие пути 948
21.4 Кратчайшие пути в ациклических сетях 956
21.5 Эвклидовы сети 964
21.6 Сведение 969
21.7 Отрицательные веса 984
21.8 Перспективы 1001
Глава 22. Потоки в сетях 1003
22.1 Транспортные сети 1010
22.2 Алгоритм поиска максимального потока методом аугментального пути 1022
22.3 Алгоритмы определения максимальных потоков
методом выталкивания превосходящего потока 1047
22.4 Сведение к максимальному потоку 1061
22.5 Потоки минимальной стоимости 1079
22.6 Сетевой симплексный алгоритм 1089
22.7 Сведение к задаче о потоке минимальной стоимости 1108
22.8 Перспективы 1117
Ссылки, использованные в пятой части 1121
Предметный указатель к части 5 1123
Предисловие
Зта книга знакомит вас с наиболее важными из применяемых на сегодняшний день
компьютерных алгоритмов, а также обучает, фундаментальным технологиям, кото¬
рые непосредственно адресованы все возрастающему количеству разработчиков,
нуждающихся в подобных знаниях. Она может быть использована как учебник для сту¬
дентов второго, третьего или четвертого курсов факультетов, связанных с компьютер¬
ными науками, после того как студенты овладели основными навыками и ознакомле¬
ны с компьютерными системами. Книга также может быть полезной для тех, кто
занимается самообразованием, или служить в качестве справочника для тех, кого ин¬
тересует разработка компьютерных систем или прикладных программ, поскольку она
содержит программные реализации полезных алгоритмов и подробную информацию о
рабочих характеристиках этих алгоритмов. В более широкой перспективе эту книгу
можно рассматривать как подходящее введение в данную предметную область.
В новом издании текст был полностью переработан, в него было включено более
тысячи новых упражнений, более сотни новых рисунков и десятки новых программ.
Кроме того, все рисунки были снабжены подробными комментариями. Этот новый
материал охватывает как новые темы, так и более полно поясняет многие классичес¬
кие алгоритмы. Большое внимание, уделенное в книге абстрактным типам данных,
расширяет сферу применения приведенных программ и делает их более пригодными
для современных сред программирования. Читатели, знакомые с предыдущими изда¬
ниями книги, найдут в ней множество новой информации; каждый читатель найдет в
книге большой объем учебного материала, который позволит успешно изучить наибо¬
лее важные понятия.
Вследствие большого объема нового материала, мы разбили новое издание на два
тома (каждый примерно равен по объему предыдущему изданию), первый из них пе¬
ред вами. Этот том охватывает фундаментальные понятия, структуры данных, алгоритмы
сортировки и алгоритмы поиска; во втором томе рассматриваются более развитые алго¬
ритмы и более сложные приложения, построенные на базе абстракций и методов, разра¬
ботанных в первом томе. Почти весь материал по основным принципам и структурам
данных, изложенный в этом издании, в предыдущих изданиях книги не рассматривался.
Эта книга адресована не только программистам и студентам, изучающим программи¬
рование и компьютерные науки. Практически каждый, кто пользуется компьютером, же¬
лает работать на нем быстрее или решать более сложные задачи. Алгоритмы, приведенные
в этой книге, представляют квинтэссенцию знаний, накопленную более чем за 50 лет, без
которых нельзя обойтись в многочисленных приложениях для эффективного использова¬
ния компьютера. От задач моделирования систем из N тел в физике и до задач анали!б ге¬
нетического кода в молекулярной биологии, описанные здесь базовые методы стали важ¬
ными составляющими современных научных исследований; от систем баз данных до
механизма поиска в Internet они стали базовыми компонентами современных про¬
граммных систем. По мере того, как сфера применения компьютерных приложений
становится все шире, возрастает влияние многих из рассмотренных здесь базовых ме¬
тодов. Данная книга может быть использована как источник информации для студен¬
тов и профессионалов, заинтересованных в ознакомлении и эффективном использова¬
нии описанных фундаментальных алгоритмов как основных инструментальных средств
для любых компьютерных приложений, какие они намерены разрабатывать.
Предисловие 1 1
Графы и алгоритмы на графах активно проникают во все современные компью¬
терные приложения. В этой книге описаны широко известные методы решения задач
обработки графов, которые возникают на практике. Ее основная цель заключается в
том, чтобы сделать эти методы и основные принципы, составляющие их основу, дос¬
тупными для все большего числа людей, которые в них нуждаются. Предлагаемый ма¬
териал книги представлен таких образом, что сначала излагаются начальные сведения,
начиная с базовой информации и основных понятий, с постепенным переходом к
анализу классических методов, и завершается изучением современных технологий, ко¬
торые все еще находятся на стадии разработки. Тщательно подобранные примеры,
подробные рисунки и завершенные программные реализации сопровождаются под¬
робным описанием алгоритмов и приложений.
Книга исключительно полезна на ранних стадиях курса обучения компьютерным
наукам, сразу после того, как студенты получат основные навыки программирования
и ознакомятся с компьютерными системами, и в то же время перед тем, как присту¬
пят к изучению специальных курсов по современным областям компьютерных наук
или прикладных вычислительных систем. Эта книга будет полезна как материал для
самообразования или как справочное пособие для специалистов, занятых разработкой
компьютерных систем или компьютерных приложений, поскольку она содержит про¬
граммные реализации полезных алгоритмов и подробные данные о рабочих характе¬
ристиках этих алгоритмов. Широкая перспектива, открывающаяся перед ними, делает
эту книгу подходящим введением в указанную выше область знаний.
Автор полностью переделал текст книги для этого издания и добавил несколько
тысяч упражнений, сотни новых иллюстраций, десятки новых программ и снабдил все
рисунки и программы развернутыми комментариями. Этот новый материал содержит
как описание новых тем, так и более полный анализ многих классических алгоритмов.
На протяжении всей книги основное внимание уделяется абстрактным типам данных,
которые существенно расширяют область применения программ и делают их исполь¬
зование более эффективным. Те, кто знаком с предыдущими изданиями настоящей
книги, найдут в ней много новой информации; все читатели найдут в ней массу по¬
лезного педагогического материала, который обеспечивает четкое понимание основ¬
ных понятий.
Книга предназначена не только для программистов и студентов, изучающих компь¬
ютерные науки. Все, кто работает с компьютером, хотят работать быстрее и решать
все более крупные задачи. Алгоритмы, которые мы изучаем, представляют собой об¬
ласть знаний, быстро развивавшуюся в течение последних пятидесяти лет и ставшую
основой для эффективного использования компьютера на широком множестве прило¬
жений. Начиная с задач моделирования систем из N тел в физике и заканчивая задача¬
ми анализа генетического кода в молекулярной биологии, описанные здесь^базовые
методы стали основной частью современных научных исследований; от систем баз
данных до механизмов поиска в Intenet они стали важной частью современных про¬
граммных систем. По мере того, как сфера применения компьютерных приложений
становится все шире, возрастает значение многих из базовых алгоритмов, особенно
фундаментальных алгоритмов на графах, описание которых дано в этом томе. Назна¬
чение этой книги состоит в том, чтобы стать источником информации для студентов и
профессионалов, чтобы они понимали и при необходимости искусно использовали ал¬
горитмы на графах в любом компьютерном приложении, каким бы оно ни было.
12 Фундаментальные алгоритмы на С. Части 1—5
Круг рассматриваемых вопросов
Книга содержит 22 главы, сгруппированных в виде пяти основных частей: основ¬
ные понятия, структуры данных, сортировка, поиск и алгоритмы на графах. Приве¬
денные в ней описания призваны ознакомить читателей с основными свойствами мак¬
симально широкого круга фундаментальных алгоритмов. Описанные здесь алгоритмы
находят широкое применение на протяжении многих лет и являются существенно важ¬
ными как для профессиональных программистов, так и для студентов, изучающих
компьютерные науки. Все описанные в книге хитроумные методы, от биномиальных
очередей до trie-деревьев, относятся к базовым концепциям, лежащим в основе ком¬
пьютерных наук. Основной целью при написании этих книг было собрать воедино
фундаментальные методы из этих различных областей дискретной математики с целью
ознакомления с лучшими методами решения задач с помощью компьютера.
По достоинству вы сможете оценить собранный в книге материал, имея за плечами
курсы по изучению основных принципов разработки и анализа алгоритмов и опыт
программирования на языках высокого уровня, таких как C++, Java, или С. Эта кни¬
га предполагает наличие у читателя соответствующей подготовки. Данный том предпо¬
лагает знание массивов, связных списков, абстрактных типов данных (АТД), в нем ис¬
пользуются очереди по приоритету, таблицы символов, АТД объединения-поиска -
все эти понятия подробно рассматриваются в частях 1-4 (и во многих других коммен¬
тариях к алгоритмам и структурах данных).
Базовые свойства графов и алгоритмов на графах разработаны на базе основных
понятий, в то же время для их полного понимания очень часто необходимо глубоко
погружаться в пучину сложных математических выкладок. Несмотря на то что обсуж¬
дение современных математических понятий носит конспективный характер, на уров¬
не общих рассуждений и описаний, от читателя, тем не менее, требуется более высо¬
кая математическая подготовка, чем для работы с материалами, содержащимися в
частях 1-4. Несмотря на это, читатели, обладающие различными уровнями математи¬
ческой подготовки, извлекут для себя немалую пользу из этой книги. К такому подхо¬
ду вынуждает следующее обстоятельство: некоторые элементарные алгоритмы на гра¬
фах, которые могут быть понятны и использоваться каждым, лишь немногим
отличаются от развитых алгоритмов, которые понимает далеко не каждый. Основная
цель в подобных случаях — поместить важные алгоритмы в контекст других методов, а
не требовать изучения всего математического материала. Однако строгий подход, на
котором настаивают высококвалифицированные математики, часто приводит нас к со¬
зданию хороших программ, в связи с чем автор стремился сохранить баланс между
формальным подходом, на котором настаивают теоретики, и изложением материала,
рекомендуемом практиками, не жертвуя при этом строгостью.
Использование материала в рамках учебных курсов
Что касается стиля изложения материала, то в этом плане преподавателю предос¬
тавляется свобода в широких пределах, в зависимости от предпочтений преподавателя
и подготовки студентов. Описанные в книге алгоритмы широко использовались в те¬
чение многих лет, они представляют собой совокупность знаний, необходимых как
программисту-практику, так и студенту, изучающему теорию вычислительных систем.
В данной книге содержится объем основного материала, достаточный для того, чтобы
ее можно было использовать в качестве учебника по курсу алгоритмов и структур
Предисловие 13
данных, в то же время она содержит достаточно материала, чтобы быть использован¬
ной в качестве учебника по курсу алгоритмов на графах. Возможно, одни преподава¬
тели будут уделять основное внимание реализациям и практическим вопросам, а дру¬
гие - анализу и теоретическим исследованиям.
Данная книга ориентирована на изучение алгоритмов, которые, скорее всего, бу¬
дут использованы на практике. В ней содержится достаточно подробная информация
об инструментальных средствах, позволяющих читателям уверенно реализовывать, от¬
лаживать и запускать в работу алгоритмы решения различных задач или снабжать при¬
ложения необходимыми функциональными возможностями. В книгу включены полные
реализации рассматриваемых в ней методов, равно как и описание работы этих про¬
грамм на специально подобранном множестве примеров. Поскольку мы работаем с
реальными программными кодами, а не пользуемся псевдокодами, эти программы
можно быстро запустить в работу в рамках практических приложений.
Действительно, одним из практических применений этих алгоритмов было создание
сотен иллюстраций для данной книги. Благодаря этим иллюстрациям, суть многих ал¬
горитмов становится понятной на интуитивном уровне.
В книге подробно рассматриваются рабочие характеристики алгоритмов и ситуа¬
ции, в которых эти алгоритмы могут быть полезны. В контексте прослеживается связь
с анализом алгоритмов и теорией вычислительных систем. Чтобы показать, почему
предпочтение отдается тому или иному алгоритму, там, где это уместно, приводятся
результаты эмпирических и аналитических исследований. В представляющих интерес
случаях дается описание взаимосвязи между рассматриваемыми практическими алго¬
ритмами и чисто теоретическими результатами. Специальная информация по рабочим
характеристикам алгоритмов и их реализациям обобщается, выделяется и обсуждается
на протяжении всей книги.
Язык программирования
Во всех реализациях используется язык программирования С. Каждый конкретный
язык программирования имеет свои преимущества и недостатки; мы используем язык
С, так как он легко доступен и обладает свойствами, которые требуются для наших
приложений. Программные реализации можно легко перевести на любой другой со¬
временный язык программирования, так как в языке С имеется лишь небольшое чис¬
ло конструкций, характерных только для него. Мы используем стандартные идиомы
языка С там, когда в этом возникает необходимость, но назначение этой книги состо¬
ит не в том, чтобы служить справочным пособием по программированию на С.
В эту редакцию книги включено множество новых программ, многие из старых
программ были переделаны, главным образом, в силу того, чтобы их можно было ис¬
пользовать как реализации абстрактных типов данных. Обширные эмпирические ис¬
следования и сравнения программ проводятся на протяжении всего текста книги.
Цель данной книги заключается в том, чтобы представить алгоритмы в максималь¬
но простой и понятной форме. Везде, где это возможно, мы стремились сохранить
этот стиль, чтобы сходные по выполняемым действиям программы выглядели похожи¬
ми. Для многих алгоритмов в этой книге это подобие сохраняется независимо от язы¬
ка: быстрая сортировка (если выбирать какой-либо яркий пример) так и остается бы¬
строй сортировкой независимо от того, какой язык выбран для реализации ее
алгоритма: Algol-60, Basic, Fortran, Smalltalk, Ada, Pascal, C, PostScript, Java или ка¬
14 Фундаментальные алгоритмы на С. Части 1—5
кой-то другой из бесчисленного множества языков и сред программирования, в кото¬
рых она показала себя эффективным методом сортировки.
Мы стремимся к изящным, компактным, эффективным и переносимым реализаци¬
ям, однако мы придерживаемся той точки зрения, что главное - это эффективность,
поэтому мы стараемся не упустить из виду рабочие характеристики создаваемых нами
программ на всех стадиях разработки.
Благодарности
Многие читатели прислали мне исключительно полезные отзывы о предыдущих из¬
даниях этой книги. В частности, в течение ряда лет предварительные наброски книги
апробировались на сотнях студентов в Принстоне и Брауне. Особую благодарность хо¬
телось бы выразить Трине Эйвери (Tina Avery) и Тому Фримену (Tom Freeman) за
оказанную помощь в выпуске первого издания; Джанет Инсерпи (Janet Incerpi) за
проявленные ею творческий подход и изобретательность, чтобы заставить аппаратные
и программные средства нашей примитивной и давно устаревшей компьютеризиро¬
ванной издательской системы напечатать первое издание книги; Марку Брауну (Mark
Brown) за его участие в исследованиях по визуализации алгоритмов, которые во мно¬
гом способствовали появлению в книге многочисленных рисунков, а также Дэйву
Хенсону (Dave Hanson) и Эндрю Эппелю (Andrew Appel) за их постоянную готов¬
ность ответить на мои вопросы, связанные с языками программирования. Я хотел бы
также поблагодарить многочисленных читателей, приславших отзывы на различные из¬
дания этой книги, в том числе Гая Олмсу, Джона Бентли, Марка Брауна, Джея Гри-
шера, Аллана Хейдона, Кеннеди Лемке, Юди Манбер, Дану Ричардс, Джона Рейфа,
М. Розенфельда, Стивена Сейдмана, Майка Квина и Вильяма Варда.
При подготовке нового издания я имел удовольствие работать с Питером Гордоном
(Peter Gordon), Дебби Лафферти (Debbie Lafferty) из издательства Addison-Wesley, кото¬
рые терпеливо опекали этот проект с момента его зарождения. Большое удовольствие до¬
ставила мне совместная работа с другими штатными сотрудниками этого издательства. Ха¬
рактер проекта сделал подготовку издания данной книги несколько непривычной задачей
для многих из них, и я высоко ценю проявленную ими снисходительность.
В процессе написания этой книги я приобрел трех новых наставников и хочу осо¬
бо выразить им свою признательность. Во-первых, Стиву Саммиту (Steve Summit), ко¬
торый внимательно проверил на техническом уровне первые варианты рукописи и
предоставил буквально тысячи подробных комментариев, особенно в отношении про¬
грамм. Стив хорошо понимал мое стремление снабдить книгу изящными и эффектив¬
ные реализациями, и его комментарии помогли мне не только обеспечить определен¬
ное единообразие реализаций, но и существенно улучшить многие из них. Во-вторых,
хочу поблагодарить Лин Дюпре (Lyn Dupre) за тысячи подробных комментариев в от¬
ношении рукописи, которые помогли не только избежать и исправить грамматические
ошибки, но и (что значительно важнее) выработать последовательный и связный стиль
написания, что позволило собрать воедино устрашающую массу технического материа¬
ла. Я исключительно благодарен полученной возможности поучиться у Стива и Лин -
их вклад в разработку этой книги оказался решающим.
Многое из написанного здесь я узнал из лекций и трудов Дона Кнута (Don
Knuth) - моего наставника в Стэнфорде. Хотя непосредственно Дон и не участвовал
в написании этой книги, его влияние можно почувствовать на всем ее протяжении,
ибо именно он поставил изучение алгоритмов на научную основу, благодаря чему во¬
Предисловие 15
обще стало возможным появление подобного рода книг. Мой друг и коллега Филлип
Флажоле (Philippe Flajolet), благодаря которому анализ алгоритмов стал вполне сфор¬
мировавшейся областью исследований, оказал такое же влияние этот труд.
Я глубоко признателен за оказанную мне поддержку Принстонскому университету,
Брауновскому университету и Национальному институту исследований в области ин¬
форматики и автоматики (INRIA - Institute de Recherche en Informatique and
Automatique), где я проделал большую часть работы над книгой, а также Институту
исследований проблем безопасности и Исследовательскому центру компании Xerox в
Пало-Альто, где была проделана часть работы во время моих визитов туда. В основу
многих глав этой книги положены исследования, которые щедро финансировались
Национальным научным фондом и Отделом военно-морских исследований. И в заклю¬
чение, я благодарю Билла Боуэна (Bill Bowen), Аарона Лемоника (Aaron Lemonick) и
Нейла Руденштайна (Neil Rudenstine) за то, что они способствовали созданию в
Принстоне академической обстановки, в которой я получил возможность подготовить
эту книгу, несмотря на множество других возложенных на меня обязанностей.
Роберт Седжвик
Марли-де-Руа, Франция, февраль 1983 г.
Принстон, Нью-Джерси, январь 1990 г.
Джеймстаун, Род-Айленд, август 2001 г.
Адаму, Эндрю, Бретт, Робби и, в первую очередь, Линде посвящается.
Примечания к упражнениям
Классификация упражнений - это занятие, сопряженное с рядом трудностей, по¬
скольку читатели такой книги, как эта, обладают различным уровнем знаний и опыта.
Тем не менее, определенное указание не помешает, поэтому многие упражнения по¬
мечены одним из четырех маркеров, дабы проще было выбрать соответствующий под¬
ход.
Упражнения, которые проверяют, насколько хорошо вы усвоили материал, помечены
незаполненным треугольником:
> 17.3. Составьте список неизоморфных циклов графа, представленного на рис. 17.1.
Например, если в вашем списке содержится цикл 3-4-5-3, в нем не могут нахо¬
диться циклы 3-5-4-3, 4-5-3-4, 4-3-5-4, 5-3-4-5 или 5-4-3-5.
Чаще всего такие упражнения непосредственно связаны с примерами в тексте.
Они не должны вызывать особых трудностей, но их выполнение может прояснить
факт или понятия, которые, возможно, ускользнули из вашего внимания во время
чтения текста.
Упражнения, которые дополняют текст новой и требующей размышления информаци¬
ей, помечены незаполненной окружностью:
о 18.6. Реализуйте DFS, используя свою независимую от представления АТД-функ-
цию для обработки списков ребер из упражнения 17.60.
Такие упражнения заставляют сосредоточиться на важных понятиях, связанных с
материалом, наложенным в тексте, или искать ответа на вопрос, который может воз¬
никнуть во время прочтения. Возможно, читатели сочтут полезным прочесть эти уп¬
ражнения дбже при отсутствии времени для их выполнения.
16 Фундаментальные алгоритмы на С. Части 1-5
Упражнения, которые имеют цель поставить перед читателями задачу, помечены
черной точкой:
• 19.2. Назовите пример крупного графа DAG, описывающего какую-нибудь дея¬
тельность, выполняемую в интерактивном режиме, возможно, графа, определяемо¬
го зависимостями, связывающими определения функций в крупной системе про¬
граммного обеспечения, или связями каталогов в крупной файловой системе.
Для выполнения таких упражнений требуется потратить значительное время, в за¬
висимости от опыта читателя. В общем случае, лучше всего выполнять их в несколько
приемов.
Несколько упражнений, которые особенно трудны (по сравнению с большинством
других) помечены двумя черными точками:
•• 20.77. Разработайте алгоритм, который при заданном множестве N точек на плос¬
кости находит множество ребер, мощность которого пропорциональна N, и в ко¬
тором наверняка содержится дерево MST. Этот алгоритм должен содержать доста¬
точно легкие вычисления, чтобы можно было разработать компактную и
эффективную реализацию.
Эти упражнения аналогичны вопросам, которые могут ставиться в научной литера¬
туре, однако материал книги может так подготовить читателей, что им доставит удо¬
вольствие попытаться ответить на них (а, возможно, и преуспеть в этом).
Мы старались, чтобы все пометки были безотносительны к программной и матема¬
тической подготовке читателей. Те упражнения, которые требуют наличия опыта по
программированию или математическому анализу, очевидны. Мы настоятельно реко¬
мендуем читателям проверить свое понимание алгоритмов, реализовав их. Тем не ме¬
нее, упражнения, подобные приведенному ниже, просты для профессиональных про¬
граммистов или студентов, изучающих программирование, но могут потребовать
значительных усилий от тех, кто в последнее время по ряду причин программировани¬
ем не занимался:
• 17.73. Напишите программу, которая генерирует V случайных точек на плоскости,
после чего строит граф, состоящий из ребер, соединяющих все пары точек, уда¬
ленных друг от друга на расстояние, не превышающее d (см. рис. 17.13 и програм¬
му 3.20). Определите, какое значение d следует выбрать, чтобы ожидаемое число
ребер было равно Е. Проведите тестирование полученной программы в соответствии с
изложенным в упражнении 17.64 (для низких уровней насыщенности) и в соответствии
с изложенным в упражнении 17.65 (для высоких уровней насыщенности).
Мы настоятельно рекомендуем всем читателям стремиться учитывать приводимые
нами аналитические обоснования свойств всех алгоритмов. С другой стороны, упраж¬
нения, подобные нижеследующему, не составляют сложности для профессионального
математика или студента, изучающего дискретную математику, однако наверняка потребу¬
ют значительных усилий от тех, кто давно не занимался математическим анализом:
• 18.3. Сколько существует путей обхода лабиринта, показанного на рис. 18.2 и 18.3,
при проведении исследования Тремо?
Книга снабжена большим количеством упражнений, чтобы всех их можно было
прочесть и усвоить; тем не менее, я надеюсь, что среди них достаточно таких, кото¬
рые могут послужить мощным стимулом к углубленному пониманию интересующих их
вопросов, нежели простое чтение текста.
Анализ
1
2
Ввеление
Принципы анализа алгоритмов
Введение
Цель этой книги - изучение широкого множества важ¬
ных и полезных алгоритмов, то есть, методов реше¬
ния задач, которые подходят для компьютерной реализа¬
ции. Мы будем иметь дело с различными областями
применения, всегда уделяя основное внимание фундамен¬
тальным алгоритмам, которые важно знать и интересно
изучать. Мы затратим достаточное время на изучение каж¬
дого алгоритма, чтобы понять его основные характеристи¬
ки и разобраться во всех его тонкостях. Наша цель - до¬
статочно подробно изучить как можно больше самых
важных алгоритмов, используемых в компьютерах в насто¬
ящее время, чтобы уметь ими пользоваться и дать оценку
их сильным и слабым сторонам.
Стратегия, используемая для изучения программ, пред¬
ставленных в этой книге, заключается в их реализации и
тестировании, экспериментировании с различными их вер¬
сиями, в анализе их работы на небольших примерах и в
попытках их выполнения применительно к более сложным
практическим задачам, с какими мы можем столкнуться
на практике. Для описания алгоритмов будет использован
язык программирования С, что также позволит получить
полезные программные реализации. Программы написаны
в единообразном стиле, который допускает также их пе¬
ревод на другие современные языки программирования.
Значительное внимание также уделяется рабочим ха¬
рактеристикам алгоритмов, чтобы легче было разрабаты¬
вать более совершенствованные версий алгоритмов, срав¬
нивать различные алгоритмы выполнения одной и той же
задачи и предсказывать или гарантировать их производи¬
тельность при решении сложных задач. Чтобы понять, как
работает тот или иной алгоритм, возможно, потребуется
выполнить ряд экспериментов с ними или провести их ма-
Глава 1. Введение 19
тематический анализ, либо и то, и другое. Мы рассмотрим подробную информацию,
касающуюся многих наиболее важных алгоритмов, причем, когда это целесообразно,
аналитические выкладки приводятся непосредственно в тексте; в других случаях, необ¬
ходимые результаты берутся из научных публикаций.
Чтобы продемонстрировать общий подход к разработке алгоритмических решений,
в этой главе мы рассмотрим подробный пример, по условиям которого для решения
конкретной задачи используются несколько алгоритмов. Рассматриваемая задача — это
не просто модельная задача; это фундаментальная вычислительная задача, и решение,
которое мы стремимся получить, должно быть пригодным для использования в раз¬
личных приложениях. Мы начнем с простого решения, затем постараемся выяснить
его рабочие характеристики, что поможет нам найти способы усовершенствовать ал¬
горитм. Выполнив определенное число итераций этого процесса, получим эффектив¬
ный и полезный алгоритм решения задачи. Этот пример служит своего рода прототи¬
пом использования одной и той же общей методологии на протяжении всей книги.
Глава завершается кратким обсуждением содержания книги, включая описание ос¬
новных ее частей и их взаимосвязь между собой.
1.1 Алгоритмы
Для написания компьютерной программы мы обычно используем метод, который
уже был когда-то разработан для решения какой-либо задачи. Часто этот метод не за¬
висит от конкретного используемого компьютера - вполне вероятно, что он будет
одинаково пригодным для многих компьютеров и многих компьютерных языков.
Именно метод, а не сама программа должен быть исследован с тем, чтобы выяснить, как
подойти к решению задачи. Термин алгоритм используется в компьютерных науках для
описания метода решения задачи, пригодного для реализации в виде компьютерной про¬
граммы. Алгоритмы составляют основу теории вычислительных машин и систем: они явля¬
ются основными объектами изучения во многих, если не большинства ее областей.
Большая часть представляющих интерес алгоритмов использует методы организа¬
ции данных, применяемых в вычислениях. Созданные таким образом объекты называ¬
ются структурами данных (data structures), и они также являются центральными объекта¬
ми изучения компьютерных наук. Следовательно, алгоритмы и структуры данных идут
рука об руку. В этой книге мы будем придерживаться точки зрения, согласно которой
структуры данных существуют как промежуточные или конечные результаты выполне¬
ния алгоритмов и, следовательно, обязаны мы их изучить, чтобы получить полное
представление об алгоритме. Простые алгоритмы могут порождать сложные структуры
данных и наоборот, сложные алгоритмы могут использовать простые структуры дан¬
ных. В этой книге будут изучены свойства многих структур данных; фактически книга
вполне могла бы называться "Алгоритмы и структуры данных в языке С".
Когда компьютер используется для решения той или иной задачи, мы, как прави¬
ло, сталкиваемся с рядом различных возможных подходов. При решении простых за¬
дач выбор того или иного подхода вряд ли имеет особое значение, если только выб¬
ранный подход приводит к правильному решению. Однако, при решении сложных
задач (или в приложениях, в которых приходится решать очень большое количество
простых задач) мы немедленно сталкиваемся с необходимостью разработки методов, в
20 Часть 1. Анализ
условиях которых время или память используются с максимально возможной эффек¬
тивностью.
Основная побудительная причина изучения алгоритмов состоит в том, что это зна¬
ние этой предметной области позволяет обеспечить огромную экономию ресурсов,
вплоть до получения решений задач, которые в противном случае были бы невозмож¬
ны. В приложениях, в которых обрабатываются миллионы объектов, часто оказывается
возможным ускорить работу программы в миллионы раз, используя хорошо разрабо¬
танный алгоритм. Подобный пример приводится в разделе 1.2 и многих других разде¬
лах книги. Для сравнения, дополнительные затраты денег или времени для приобрете¬
ния и установки нового компьютера потенциально позволяет ускорить работу программы
всего лишь в 10-100 раз. Тщательная разработка алгоритма - исключительно эффектив¬
ная часть процесса решения сложной задачи в любой области применения.
При разработке очень большой или очень сложной компьютерной программы зна¬
чительные усилия должны быть направлены на понимание и постановку задачи, под¬
лежащей решению, оценку ее сложности и разбиение ее на менее сложные подзадачи,
решения которых можно легко реализовать. Часто реализация многих из алгоритмов
решения задач, полученных в результате разбиения, тривиальна. Однако в большинстве
случаев существует несколько алгоритмов, выбор которых особенно важен, поскольку
на их выполнения затрачивается существенная часть системных ресурсов. Именно
этим типам алгоритмов уделяется основное внимание в данной книге. Мы изучим ряд
основополагающих алгоритмов, которые полезны при решении сложных задач во
многих областях применения.
Совместное использование одних и тех же программ в различных компьютерных
системах становится все более распространенным, поэтому, рассчитывая на использо¬
вание многих из рассмотренных в книге алгоритмов, мы в то же время должны созна¬
вать, что реализовывать нам удастся лишь немногие из них. Тем не менее, реализация
простых версий базовых алгоритмов позволяет лучше их понять и, следовательно, эф¬
фективнее использовать и точнее настраивать более развитые их версии. И что еще
важнее, повод для повторной реализации базовых алгоритмов возникает очень часто.
Основная причина состоит в том, что мы сталкиваемся, и очень часто, с совершенно
новыми вычислительными средами (аппаратными и программными) и с новыми свой¬
ствами, которые не могут наилучшим образом использовать старые реализации этих
алгоритмов. Другими словами, чтобы наши решения были более переносимыми и
дольше сохраняли актуальность, мы часто пользуемся базовыми алгоритмами, ориен¬
тированными на конкретное приложение, а не полагаемся на системные подпрограм¬
мы. Другая часто возникающая причина повторной реализации базовых алгоритмов
заключается в том, что механизмы совместного использования программ во многих
компьютерных системах не всегда обладают достаточной мощностью, чтобы позволить
нам адаптировать стандартные программы для эффективного решения специальных
задач (либо вообще могут не подходить для их выполнения), поэтому иногда гораздо
легче разработать новую реализацию.
Компьютерные программы часто чрезмерно оптимизированы. В некоторых случаях
достижения максимальной эффективности реализации конкретного алгоритма не стоит
затрачиваемых на это усилий, например, если алгоритм не предназначен для решения
очень сложной задачи или не используется многократно. В отдельных случаях вполне
Глава 1. Введение 2 1
достаточно аккуратной, сравнительно простой реализации: достаточно быть уверенным
в ее работоспособности и в том, что, скорее всего, в худшем случае она будет рабо¬
тать в 5—10 раз медленнее наиболее эффективной версии, что может означать увеличе¬
ние времени выполнения на несколько дополнительных секунд. И напротив, правиль¬
ный выбор алгоритма может ускорить работу в 100-1000 и более раз, что может
обеспечить экономию времени прогона алгоритма в минутах, часах и даже более того.
В этой книге основное внимание уделяется простейшим приемлемым реализациям
наилучших алгоритмов.
Выбор наилучшего алгоритма решения конкретной задачи может оказаться слож¬
ным процессом, подчас требующим сложного математического анализа. Направление
компьютерных наук, занимающееся изучением подобных вопросов, называется анали¬
зом алгоритмов (analysis of algorithm). Анализ многих изучаемых нами алгоритмов пока¬
зывает, что для них характерна прекрасная производительность; о хорошей работе
других известно просто из опыта их применения. Наша основная цель - изучение ал¬
горитмов, пригодных для решения важных задач, хотя большое внимание будет уделе¬
но также сравнительной производительности различных методов. Не следует использо¬
вать алгоритм, не имея представления о ресурсах, которые могут потребоваться для
его выполнения, поэтому мы стремимся заранее знать, какую производительность
можно ожидать от того или иного алгоритма.
1.2 Пример задачи связности
Предположим, что имеется последовательность пар це¬
лых чисел, в которой каждое целое число представляет
объект некоторого типа, а пара p-q интерпретируется как
"р связано с q". Мы полагаем, что отношение ’’связано с"
является транзитивным: если р связано с q, a q связано с
г, то р связано с г. Задача состоит в написании програм¬
мы, исключающей лишние пары из этого множества: ког¬
да программа вводит пару p-q, она должна выводить эту
пару только в том случае, если из просмотренные на те¬
кущий момент множества пар не следует, что р связано с
q. Если просмотренных ранее пар следует, что р связано
с q, то программа должна игнорировать пару p-q и пере¬
ходить к вводу следующей пары. Пример такого процесса
показан на рис. 1.1.
Задача состоит в разработке программы, которая мо¬
жет запомнить достаточный объем информации о просмот¬
ренных парах, чтобы решить, связана ли новая пара
объектов. Достаточно неформально задачу разработки та¬
кого метода мы называем задачей связности (connectivity
problem). Такая задача возникает в ряде важных приложе¬
ний. Мы коротко рассмотрим три примера, подтверждаю¬
щие фундаментальный характер этой задачи.
Например, целые числа могли бы представлять компь¬
ютеры в большой сети, а пары чисел могли бы представ-
3-4
4-9
8-0
2-3
5-6
2-9
5-9
7-3
4-8
5-6
0-2
6-1
3-4
4-9
8-0
2-3
5-6
5-9
7-3
4-8
6-1
2-3-4-9
5-6
0-8-4-3-2
РИСУНОК 1.1.
ПРИМЕР ЗАДАЧИ СВЯЗНОСТИ
При заданной последователь¬
ности пар целых чисел,
представляющих связь между
объектами (столбец слева),
в алгоритме решения задачи
связности передайте на
вывод те пары, которые
устанавливают новые связи
(столбец в центре). Напри¬
мер, пара 2-9 не должна
выводиться, поскольку связь
2-3-4-9 определяется ранее
указанными связями (доказа¬
тельство этого утверждения
показано справа).
22 Часть /. Анализ
лять соединения в сети. Тогда такой программой можно воспользоваться для опреде¬
ления того, нужно ли устанавливать новое прямое соединение между р и q, чтобы они
имели возможность обмениваться информацией, или же можно использовать суще¬
ствующие соединения, чтобы установить коммутируемый канал связи между ними. В
подобных приложениях может потребоваться обработка миллионов точек и миллиар¬
дов или большего числа соединений. Как мы увидим далее, решить подобную задачу
для такого приложения невозможно, не имея эффективного алгоритма.
Аналогично, целые числа могут представлять токоприемники электрической сети, а
пары этих чисел могут представлять связывающие их провода. В этом случае програм¬
му можно было бы использовать для определения способа соединения всех токопри¬
емников без каких-либо избыточных соединений, если это возможно. Не существует
никакой гарантии того, что ребер списка окажется достаточно для соединения всех
точек - действительно, вскоре мы увидим, что определение факта, так ли это, может
стать основным применением нашей программы.
Рисунок 1.2 служит более сложным примером использования этих двух видов при¬
ложений. Изучение этого рисунка дает представление о сложности задачи связности:
как можно быстро выяснить, являются ли любые две заданные точки в такой сети свя¬
занными?
РИСУНОК 1.2. БОЛЕЕ СЛОЖНЫЙ ПРИМЕР ЗАДАЧИ СВЯЗНОСТИ
Объекты задачи связности могут быть точками соединений, а пары чисел могут быть соединениями
между ними, как показано в этом идеализированном примере. Они могут представлять провода,
соединяющие здания в городе или компоненты компьютерной микросхемы. Это графическое пред¬
ставление позволяет человеку выявить узлы, не связанные друг с другом, однако алгоритм должен
работать только с переданными ему парами целых чисел. Связаны ли два узла, помеченные черными
кружками ?
Глава 1. Введение 23
Еще один пример встречается в некоторых средах программирования, где имена
каких-либо двух переменных можно объявлять эквивалентными. Задача заключается в
том, чтобы после считывания некоторой последовательности таких объявлений опреде¬
лить, являются ли два заданных имени эквивалентными. Это приложение — одно из
первых, давших начало разработке нескольких алгоритмов, которые мы будем рас¬
сматривать. Как будет показано далее, оно устанавливает непосредственную связь
между рассматриваемой задачей и простой абстракцией, которая позволяет нам ис¬
пользовать эти алгоритмы для широкого круга приложений.
Такие приложения; как задача об эквивалентности имен переменных, описанная в
предыдущем абзаце, требует, чтобы целое число с каждым отдельным именем пере¬
менной было сопоставлено некоторое целое число. Такое сопоставление подразумева¬
ется также в описанных выше приложениях, устанавливающих соединения в сети и в
электрической цепи. В главах 10-16 мы рассмотрим ряд алгоритмов, которые могут
эффективно построить такое сопоставление. Таким образом, в этой главе без ущерба
для общности изложения можно предположить, что имеется N объектов с целочислен¬
ными именами от 0 до N -1.
Нам требуется программа, которая выполняет конкретную, четко поставленную за¬
дачу. Существует множество других задач, связанных с этой задачей, которые нам,
возможно, придется решать. Одна из первых проблем, с которой приходится сталки¬
ваться при разработке того или иного алгоритма, связана с необходимостью убедиться
в том, что задана поставлена правильно. Как правило, чем больше требуется от алго¬
ритма, тем больше времени и объема памяти может потребоваться для решения задачи.
Это соотношение невозможно заранее точно выразить в числах, и часто постановку
задачи приходится менять, когда выясняется, что ее трудно решить, либо ее решение
требует слишком больших затрат, либо когда, при удачном стечении обстоятельств,
выясняется, что алгоритм может предоставить более полезную информацию, чем от
него требовалось в первоначальной постановке.
Например, приведенная выше постановка задачи связности требует только, чтобы
программа каким-либо образом могла узнать, является ли данная пара p-q связанной,
но не требует показать какой-либо один или все способы соединения этой пары. До¬
бавление в постановку конкретного требования усложняет задачу и приводит к друго¬
му семейству алгоритмов, которое мы кратко будет рассматривать в главе 5 и подроб¬
но - в части 7.
Описанная в предыдущем абзаце постановка задачи требуют больше информации,
чем первоначальная постановка; можно также потребовать от нее меньше информации.
Например, можно просто потребовать ответа на вопрос: "Достаточно ли М связей для
соединения всех N объектов?”. Эта задача служит иллюстрацией того факта, что для
разработки эффективных алгоритмов часто требуется обдумать вопросы, касающиеся
обрабатываемых объектов, на высоких уровнях абстракции. В данном случае из фун¬
даментальных положений теории графов следует, что все N объектов связаны тогда и
только тогда, когда количество пар, выданных алгоритмом решения задачи связности,
в точности равно N -1 (см. раздел 5.4). Иначе говоря, алгоритм решения задачи связ¬
ности никогда не выдаст более N -1 пар, поскольку как только он выдаст более
N - 1 пары, любая встретившаяся после этого пара уже будет связанной. Соответ¬
ственно, можно написать программу, отвечающую "да/нет" на только что поставлен¬
24 Часть 1. Анализ
ный вопрос, изменив программу, которая решает задачу связности таким образом,
чтобы она увеличивала значение специального счетчика, а не выдавала на выходе ра¬
нее несвязанную пару, и отвечала "да", когда значение счетчика достигнет значения
N- 1, и "нет”, если это не происходит. Этот вопрос - всего лишь один из множества
вопросов, на которые мы хотели бы получить ответ, исследуя свойства связности гра¬
фов. Входное множество пар чисел называется графом (graph), а выходное множество
пар — остовным деревом (spanning tree) этого графа, связывающим все объекты. Свой¬
ства графов, остовных деревьев и всевозможные связанные с ними алгоритмы будут
рассматриваться в части 7.
Имеет смысл попытаться выявить базовые операции, использованные в алгоритме
решения задачи связности и тем самым сделать любой алгоритм решения этой задачи
полезным для решения ряда аналогичных задач. В частности, при получении каждой
новой пары вначале необходимо определить, представляет ли она новое соединение,
затем следует увязать информацию о том, что это соединение было просмотрено, в
общую картину связности объектов таким образом, чтобы эта пара учитывалась при
проверке последующих соединений в будущем. Мы инкапсулируем эти две задачи в
виде абстрактных операций (abstract operation), полагая, что вводимые целочисленные
значения представляют элементы в абстрактных множествах, а затем разработаем такие
алгоритмы и структуры данных, которые могут:
■ находить множество, содержащее заданный элемент,
■ замещать множества, содержащие два данных элемента, их объединением.
Организация алгоритмов в виде последовательности абстрактных операций, по-ви¬
димому, не препятствует никаким вариантам решения задачи связности, а сами эти
операции могут оказаться полезными при решении других задач. Разработка все более
высоких уровней абстракции, обеспечивающими возрастающие возможности, - ос¬
новной процесс в компьютерных науках в целом и в разработке алгоритмов в частно¬
сти, и на протяжении этой книги мы будем обращаться к нему неоднократно. В этой
главе мы неформально воспользуемся абстрактным мышлением в качестве руководя¬
щих принципов при разработке программ решения задачи связности; как внедряются
абстракции в программы на языке С, будет показано в главе 4.
Задача связности легко решается посредством абстрактных операций find (поиск) и
union (объединение). После считывания новой пары p-q из ввода мы выполняем опера¬
цию find для каждого элемента пары. Если элементы пары находятся в одном наборе,
мы переходим к следующей паре; если нет, то выполняем операцию union и записыва¬
ем Ъту пару. Множества представляют связные компоненты (connected component): это
подмножества объектов, характеризующиеся тем, что любые два объекта в данной
компоненте связаны. Этот подход сводит разработку алгоритмического решения зада¬
чи связности к задачам определения структуры данных, представляющей эти множе¬
ства, и к разработке алгоритмов операций union и find, которые эффективно использу¬
ют эту структуру данных.
Существует много возможных способов представления и обработки абстрактных
множеств. В этой главе основное внимание уделяется поиску представления, которое
может эффективно поддерживать операции union и find, требуемые для решения задачи
связности.
Глава L Введение 25
Упражнения
1.1. Приведите выходные результаты, которые должен вычислить алгоритм реше¬
ния задачи связности при заданном вводе 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3.
1.2. Перечислите все возможные способы связывания двух различных объектов,
показанных в примере на рис. 1.1.
1.3. Опишите простой метод подсчета числа множеств, остающихся после выполне¬
ния операций union и find при решении задачи связности, как описано в тексте.
1.3 Алгоритмы объединения-поиска
Первый шаг в процессе разработки эффективного алгоритма решения заданной за¬
дачи - реализация упрощенного алгоритма ее решения. Если нужно решить несколько ва¬
риантов конкретной задачи, которые оказываются простыми, это может быть выпол¬
нено посредством упрощенной реализации. Если требуется более сложный алгоритм,
то упрощенная реализация предоставляет возможность проверить правильность работы
алгоритма для простых случаев и может служить отправной точкой для оценки харак¬
теристик производительности. Эффективность всегда остается предметом наших забот,
однако наш основной интерес при разработке первой программы решения задачи со¬
стоит в том, чтобы убедиться, что эта программа является правильным решением.
Первая мысль, которая при этом возникает - надо как-то сохранить все вводимые
пары, а затем создать функцию для их просмотра, чтобы попытаться выяснить, связа¬
на ли следующая пара объектов. Однако нам придется воспользоваться другим подхо¬
дом. Во-первых, количество пар может быть настолько велико, что в условиях прак¬
тического приложения все они не поместятся в памяти. Во-вторых, что гораздо
важнее, не существует никакого простого метода, который позволил бы определить,
связаны ли два объекта на множестве всех соединений, даже если бы нам удалось
всех их разместить в памяти! Базовый метод, использующий этот подход, рассматрива¬
ется в главе 5, методы, которые исследуются в этой главе, проще, поскольку они ре¬
шают менее сложную задачу, и эффективнее, поскольку не требуют сохранения всех
пар. Все они используют массив целых чисел, каждое из которых соответствует от¬
дельному объекту, для хранения информации, необходимой для реализации операций
union и find.
Массивы суть элементарные структуры данных, которые подробно изучаются в
разделе 3.2. Здесь же они используются в простейшей форме: мы объявляем, что соби¬
раемся использовать, скажем, 1000 целых чисел, записывая а [1000]; затем мы обра¬
щаемся к /-ому целому числу в массиве, записывая a[i] для 0 < / < 1000.
Программа 1.1 представляет собой реализацию простого алгоритма, называемого
алгоритмом быстрого поиска (quick find algorith), решающего задачу связности. В основе
этого алгоритма лежит использование массива целых чисел, обладающих тем свой¬
ством, что р и q связаны тогда и только тогда, когда р-тая и #-тая записи массива рав¬
ны. Мы инициализируем /-тую запись массива значением / при 0 < / < N. Чтобы реа¬
лизовать операцию union для р и q, мы просматриваем массив, изменяя все записи с
именем р на записи с именем q. Этот выбор произволен - можно было бы все записи
с именем q изменить на записи с именем р.
26 Часть 1. Анализ
Программа 1.1. Решение задачи связности методом быстрого поиска
Эта программа считывает последовательность пар неотрицательных целых чисел,
меньших N, из стандартного ввода (интерпретируя пару р q, как "связать объект р с
объектом q") и выводит пары, представляющие объекты, которые еще не связаны.
Она поддерживает массив id, содержащий запись для каждого объекта и обладаю¬
щий тем свойством, что элементы id[p] и id[q] равны тогда и только тогда, когда
объекты р и q связаны. Для простоты N определена во время компиляции как кон¬
станта. Иначе можно было бы считывать ее из ввода и распределять массив id дина¬
мически (см. раздел 3.2).
#include <stdio.h>
#define N 10000
main ()
{ int i, p, q, t, id[N] ;
for (i = 0; i < N; i++) id[i] = i;
while (scanf("%d %d\n", &p, &q) == 2)
{
if (id[p] == id[q]) continue;
for (t = id[p] , i = 0; i < N; i++)
if (id[i] == t) id[i] = id[q] ;
printf(" %d %d\n", p, q);
}
}
Изменения массива при выполнении операций union
в примере на рис. 1.1 показаны на рис. 1.3. Для реали¬
зации операции find достаточно проверить указанные
записи массива на предмет равенства - отсюда следует
название быстрый поиск (quick-find). С другой стороны,
операция union требует просмотра всего массива для
каждой вводимой пары.
Свойство 1.1 Алгоритм быстрого поиска выполняет не
менее MN инструкций для решения задачи связности
при наличии N объектов, для которых требуется вы¬
полнение М операций объединения.
Для каждой из М операций union цикл for выполня¬
ется N раз. Для каждой итерации требуется выпол¬
нение, по меньшей мере, одной инструкции (если ог¬
раничиваться только проверкой завершения цикла). ■
На современных компьютерах можно выполнять де¬
сятки или сотни миллионов инструкций в секунду, по¬
этому эти затраты не заметны, если значения М и N
малы, но в современных приложениях может потребо¬
ваться обработка миллиардов объектов и миллионов
вводимых пар. Поэтому мы неизбежно приходим к
заключению, что для подобных задач нельзя найти при¬
емлемого решения, если пользоваться алгоритмом быс¬
трого поиска (см. упражнение 1.10). Процесс точного
количественного обоснования этого заключения будет
рассматриваться в главе 2.
р q
0123456789
2 4 4
2 9 9
2 9 9
9
9
9
9
9
1 1
7 8
7 8
7 0
7 0
9 7
9 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
11111
РИСУНОК 1.3
ПРИМЕР БЫСТРОГО ПОИСКА
(МЕДЛЕННОГО ОБЪЕДИНЕНИЯ)
В этой таблице приводится
содержимое массива id после
того, как каждая пара,
представленная слева, обраба¬
тывается алгоритмом быстрого
поиска (программа 1.1).
Затененные элементы — это
те, которые изменяются для
выполнения операции union.
При обработке пары р q все
элементы, имеющие значение
id[p], получают значение
id[q].
Глава 7. Введение 27
®®@®®®®®®
® ® ©
® ® ® ®
Графическое представление массива, показанного на
рис. 1.3, приведено на рис. 1.4. Можно считать, что не¬
которые объекты представляют множество, к которому
они принадлежат, а остальные указывают на представите¬
ля их множества. Причина обращения к такому графи¬
ческому представлению массива вскоре станет понятна.
Обратите внимание на тот факт, что связи между объек¬
тами в этом представлении не обязательно совпадают со
связями во вводимых парах — они представляют собой
информацию, запоминаемую алгоритмом, чтобы иметь
возможность определить, соединены ли пары, которые
будут вводиться в будущем.
Следующий алгоритм, который мы рассмотрим, пред¬
ставляет собой метод, дополнительный к предшествующе¬
му и названный алгоритмом быстрого объединения (quick-
union algorithm). В его основе лежит та же структура
данных - массив, индексированный по именам объектов,
но в нем используется иная интерпретация значений, что
приводит к более сложным абстрактным структурам. В
структуре, которая не содержит циклов, каждый объект
указывает на другой объект того же множества. Чтобы
определить, находятся ли два объекта в одном множе¬
стве, мы следуем указателям на каждый из них до тех
пор, пока не будет достигнут объект, который указывает
на самого себя. Объекты находятся одном и том же мно¬
жестве тогда и только тогда, когда этот процесс приво¬
дит из каждого из них к одному и тому же объекту. Если
они не содержатся в одном множестве, процесс завер¬
шится на разных объектах (которые указывают сами на
себя). Тогда для образования объединения достаточно
связать оба эти объекта друг с другом, чтобы выполнить
операцию union; отсюда и название быстрое объединение
(quick-union).
На рис. 1.5 показано графическое представление, ко¬
торое соответствует рис. 1.4 при выполнении алгоритма
быстрого объединения на массиве, изображенном на рис.
1.1, а на рис. 1.6 показаны соответствующие изменения в
массиве id. Графическое представление структуры дан¬
ных позволяет сравнительно легко понять, как работает
алгоритм - вводимые пары, о которых известно, что они
связаны во входных данных, остаются связанными и в
структуре данных. Как упоминалось ранее, важно иметь в виду с самого начала, что
связи в структуре данных не обязательно совпадают со связями в приложении, отобра¬
жаемыми вводимыми парами; скорее, алгоритм строит их таким образом, чтобы обес¬
печить эффективное выполнение операций union и find.
РИСУНОК 1.4
ПРЕДСТАВЛЕНИЕ БЫСТРОГО
ПОИСКА В ВИДЕ ДЕРЕВА.
На этом рисунке показано
графическое представление
примера, приведенного на рис.
1.3. Связи на этом рисунке не
обязательно представляют
связи во входном массиве.
Например, структура,
показанная на нижней
диаграмме, содержит связь
1-7, которая отсутствует во
вводе, но образуется в резуль¬
тате обработки строки
связей 7-3-4-9-5-6-1.
28 Часть 1. Анализ
Связанные компоненты, изображенные на рис. 1.5,
называются деревьями (tree); это основополагающие
комбинаторные структуры, с которыми мы много¬
кратно будем сталкиваться на протяжении этой книги.
Свойства деревьев будут подробно рассмотрены в гла¬
ве 5. Деревья, изображенные на рис. 1.5, полезны для
выполнения операций union и find, поскольку их мож¬
но быстро построить, и они характеризуются тем, что
два объекта связаны в дереве тогда и только тогда,
когда объекты связаны во входном массиве. Переме¬
щаясь вверх по дереву, можно легко отыскать корень
дерева, содержащего каждый объект, и, следователь¬
но, существует способ определить, связаны ли они
друг с другом или нет. Каждое дерево содержит толь¬
ко один объект, указывающий сам на себя, называе¬
мый корнем (root) дерева. Указатель на себя на диаг¬
раммах не показан. Начав с любого объекта дерева и
перемещаясь к объекту, на который он указывает, за¬
тем к следующему указанному объекту и так далее, мы
в конечном итоге всегда попадаем в корень. Справед¬
ливость этого свойства можно доказать методом ин¬
дукции: это свойство выполняется сразу после иници¬
ализации массива, так как каждый объект в этот
момент указывает сам на себя, и если это справедливо
перед выполнением данной операции union, это безус¬
ловно справедливо и после ее выполнения.
Диаграммы алгоритма быстрого поиска, показан¬
ные на рис. 1.4, обладают теми же свойствами, что и
описанные в предыдущем абзаце. Различие состоит в
том, что в деревьях быстрого поиска мы достигаем
корня из всех узлов, следуя лишь вдоль одной связи, в
то время как в дереве быстрого объединения для дос¬
тижения корня может потребоваться пройти по не¬
скольким связям.
Программа 1.2 представляет собой реализацию опе¬
раций union n findy вместе образующих алгоритм быст-
®Ф®@®®®®®
(D
® ® ® ® ® ® ® ®
0
®
РИСУНОК. 1.5
ПРЕДСТАВЛЕНИЕ БЫСТРОГО
ОБЪЕДИНЕНИЯ В ВИДЕ ДЕРЕВА
На этом рисунке дано графическое
представление примера, приведен¬
ного на рис. 1.3. Мы проводим
линию от объекта i к объекту
id[i].
рого объединения для решения задачи связности. На
первый взгляд кажется, что алгоритм быстрого объединения работает быстрее алгорит¬
ма быстрого поиска, поскольку для каждой вводимой пары ему не нужно просматривать
весь массив, но насколько он быстрее? На этот вопрос здесь труднее ответить, чем в слу¬
чае быстрого поиска, поскольку время выполнения этого алгоритма в большей степени
зависит от характера ввода. Выполнив эмпирические исследования или математический
анализ (см. главу 2), можно убедиться, что программа 1.2 значительно эффективнее про¬
граммы 1.1 и ее можно использовать для решения крупных практических задач. Одно из
таких эмпирических исследований будет рассмотрено в конце этого раздела.
Глава 1. Введение 29
А пока быстрое объединение будем считать усо¬
вершенствованием, поскольку оно устраняет основ¬
ной недостаток быстрого поиска (состоящий в том,
что для выполнения М операций union на N объектах
программе нужно выполнить, по меньшей мере, NM
инструкций).
Программа 1.2 Решение задачи связности методом
быстрого объединения
Если тело цикла while в программе 1.1 заменить
этим кодом, мы получим программу, которая соот¬
ветствует тем же спецификациям, что и программа
1.1, но выполняет меньше вычислений для операции
union за счет выполнения большего количества вы¬
числений для операции find. Циклы for и последую¬
щий оператор if в этом коде определяют необходи¬
мые и достаточные условия для того, чтобы массив
id для р и q был связанным. Оператор присваива¬
ния id[i] = j реализует операцию union.
for (i = р;
for (j = q;
if (i == j)
id[i] = j;
printf(" %d %d\n",
i != id[i];
j !« id[j];
continue;
= id[i])
= id[j])
q) ;
Это различие между быстрым объединением и
быстрым поиском действительно является усовер¬
шенствованием, но быстрое объединение все же об¬
ладает тем недостатком, что нельзя гарантировать,
что оно будет выполняться существенно быстрее бы¬
строго поиска в каждом случае, ибо может возник¬
нуть такое сочетание вводимых данных, что опера¬
ция find замедлится.
Свойство 1.2. Пусть даны М пар на множестве N
объектов и М > N; для решения задачи связности
алгоритму быстрого объединения может потребо¬
ваться выполнение более MN/2 инструкций.
р
q
0
1
2
3
4
5 6
7
8
9
3
4
0
1
2
щ.
4
5 6
7
8
9
4
9
0
1
2
4
9
5 6
7
8
9
8
0
0
1
2
4
9
5 6
7
0
9
2
3
0
1 !1(
4
9
5 6
7
0
9
5
6
0
1
9
4
9
И б
7
0
9
2
9
0
1
9
4
9
6 6
7
0
9
5
9
0
1
9
4
9
6 ш
7
0
9
7
3
0
1
9
4
9
6 9
ш
0
9
4
8
0
1
9
4
9
6 9
9
0
■
5
6
0
1
9
4
9
б 9
9
0
0
0
2
0
1
9
4
9
б 9
9
0
0
6
1
н
1
9
4
9
6 9
9
0
0
5
8
1
1
9
4
9
6 9
9
0
0
РИСУНОК 1.6.
ПРИМЕР БЫСТРОГО ОБЪЕДИНЕНИЯ
(НЕ ОЧЕНЬ БЫСТРОГО ПОИСКА)
В этой таблице отображается
содержимое массива id после
обработки каждой из показанных
слева пар чисел алгоритмом
быстрого поиска (программа 1.1).
Затененные элементы — это те,
значения которых изменяются для
последующего выполнения операции
объединения (по одному на каждую
операцию). При обработке пары
р q мы следуем по указателям из р,
чтобы выйти в элемент i, для
которого id [ i ] = i; затем мы
следуем по указателям из i, чтобы
попасть в элемент j, для которого
id[ j] = j; затем, если i и j
различны, устанавливаем id [ i ] =
id [ j ]. Для выполнения операции
find для пары 5-8 (последняя
строка) i принимает значения 5 6
9 0 1, a j ~ значения 8 0 1.
Предположим, что пары вводятся в следующем
порядке: 1-2, 2-3, 3-4 и так далее. После ввода
N - 1 таких пар мы имеем N объектов, принадле¬
жащих к одному множеству, и сформированное алгоритмом быстрого объединения
дерево представляет собой прямую линию, в котором объект N указывает на
объект N- \ , тот, в свою очередь, — на объект N -2, тот — на N - 3 и так далее.
Чтобы выполнить операцию find для объекта N, программа должна отследить N -1
указателей. Таким образом, среднее количество указателей, отслеживаемых для
первых N пар, равно
(О + 1 + ... + (N— I)) / N = (N- 1) / 2
30 Часть 1. Анализ
Теперь предположим, что все остальные пары связывают объект N с каким-либо
другим объектом. Чтобы выполнить операцию find для каждой из этих пар, требует¬
ся отследить, по меньшей мере, (N— 1) указателей. Общее число инструкций для
М операций find для такой последовательности вводимых пар определенно больше
MN/ 2. ■
К счастью, можно легко внести такие изменения в этот алгоритм, которые гаран¬
тируют, что худшие случаи, подобные этому, не возникнут. Вместо того чтобы произ¬
вольным образом соединять второе дерево с первым для выполнения операции union,
можно отслеживать количество узлов в каждом дереве и всегда соединять меньшее де¬
рево с большим. Это изменение требует несколько большего объема кодов и наличия
еще одного массива для хранения счетчиков узлов, как показано в программе 1.3, но
оно приводит к существенному повышению эффективности алгоритма. Мы будем на¬
зывать этот алгоритм алгоритмом взвешенного быстрого объединения (weighted quick-union
algorithm).
Программа 1.3 Взвешенная версия быстрого бъединения
Эта программа является модификацией алгоритма быстрого объединения (см. про¬
грамму 1.2), которая в служебных целях поддерживает для каждого объекта, у которо¬
го id[i] = i, дополнительный массив sz, представляющий собой массив количе¬
ства узлов в соответствующем ему дереве, чтобы операция union могла связывать
меньшее из двух заданных деревьев с большим, тем самым предотвращая разраста¬
ние длинных путей в деревьях.
#include <std±o.h>
#define N 10000
main()
{ int i, j, p, q, id[N], sz [N] ;
for (i = 0; i < N; i++)
{ id[i] = i; sz[i] = 1; }
while (scanf ("%d %d\n", 4p, &q) == 2)
{
for (i = p; i != id[i] ; i * id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
if (sz [i] < sz [ j ])
{ id[i] = j; sz[j] += s z[i]; }
else { id[j] = i; sz[i] += sz[j]; }
printf(" %d %d\n", p, q) ;
}
}
На рис. 1.7 показан лес деревьев, построенных алгоритмом взвешенного поиска
для примера ввода, приведенного на рис. 1.1. Даже в этом небольшом примере пути в
деревьях существенно короче, чем в случае невзвешенной версии, представленной на
рис. 1.5. Рисунок 1.8 служит иллюстрацией того, что происходит в худшем случае, ког¬
да размеры объединяемых операцией union множеств всегда равны (и являются степе¬
нью 2). Эти структуры деревьев выглядят сложными, но они обладают простым свой¬
ством, состоящим в том, что максимальное число указателей, которые необходимо
отследить, чтобы достичь корня в дереве из 2п узлов, равно п. Более того, при слия¬
нии двух деревьев, состоящих из Т узлов, мы получаем дерево,, состоящее из 2Л+1 уз¬
лов, а максимальное расстояние до корня увеличивается до п + 1. Это наблюдение
Глава 1. Введение 3 1
можно обобщить до доказательства того, что взвешен¬
ный алгоритм значительно эффективнее невзвешенного.
Свойство 1.3. Для определения того, связаны ли два
из N объектов, алгоритму взвешенного быстрого
объединения требуется отследить максимум 21 g N
указателей.
Можно доказать, что операции union сохраняет
свойство, согласно которому количество указателей,
отслеживаемых из любого узла на пути до корня на
множестве из к объектов, не превышает lg к. При
объединении множества, состоящего из / узлов, с
множеством, состоящим из j узлов, при / < j число
указателей, которые должны отслеживаться в мень¬
шем множестве, увеличивается на 1, но теперь узлы
находятся в множестве размера / + у, и, следователь¬
но, свойство не нарушается, ибо 1 + lg / =
= lg(/ + /) < lg(/ +j). ш
Практическое следствие свойства 1.3 заключается в
том, что количество инструкций, которые алгоритм
взвешенного быстрого объединения использует для об¬
работки М ребер между N объектами, не превышает
значения М lg N, умноженного на некоторую константу
(см. упражнение 1.9). Этот вывод резко отличается от
полученной нами выше оценки, согласно которой алго¬
ритм быстрого поиска всегда (а алгоритм быстрого
объединения иногда) использует не менее М N/2 инст¬
рукций. Мы приходим к заключению, что при исполь¬
зовании взвешенного быстрого объединения мы можем
гарантировать, что крупные задачи, с которыми дово¬
дится сталкиваться на практике, можно решать за при¬
емлемое время (см. упражнение 1.11). Добавив всего
лишь несколько строк дополнительного кода, мы полу¬
чим программу, которая при решении крупных задач,
могущих встретиться в практических приложениях, ра¬
ботает буквально в миллионы раз быстрее, чем более
простые алгоритмы.
Из приведенных схем видно, что лишь сравнительно
небольшое количество узлов располагаются далеко от
корня; действительно, эмпирические исследования
очень сложных задач показывает, что, как правило, для
©Ф@(з)®®®®®
© © © ® © © ® ®
® ® © ® © © ®
® © ©
© © ®
РИСУНОК 1.7. ПРЕДСТАВЛЕНИЕ
ВЗВЕШЕННОГО БЫСТРОГО
ОБЪЕДИНЕНИЯ В ВИДЕ ДЕРЕВА
На этой последовательности
рисунков демонстрируется
результат внесения изменений
алгоритма быстрого объедине¬
ния, обеспечивающих связыва¬
ние корня меньшего из двух
деревьев с корнем большего из
деревьев. Расстояние от
каждого узла до корня его дерева
невелико, поэтому операция find
выполняется эффективно.
решения практических задач посредством использова¬
ния алгоритма взвешенного быстрого объединения, реализованного в программе 1.3,
требуется линейное время. То есть, затраты времени на выполнение алгоритма связаны
с затратами времени на считывание ввода постоянным коэффициентом. Вряд ли мож¬
но было бы рассчитывать найти более эффективный алгоритм.
32 Часть L Анализ
Сразу же возникает вопрос, можно ли найти алго¬
ритм, обеспечивающий гарантированную линейную про¬
изводительность. Этот исключительно трудный вопрос
уже много лет не дает покоя исследователям (см. раздел
2.7). Существует множество способов дальнейшего со¬
вершенствования алгоритма взвешенного быстрого
объединения. В идеальном случае было бы желательно,
чтобы каждый узел указывал непосредственно на ко¬
рень своего дерева, но за это не хотелось бы расплачи¬
ваться изменением большого числа указателей, как это
делалось в случае алгоритма быстрого объединения. К
идеалу можно приблизиться, просто делая все проверя¬
емые узлы указателями на корень. На первый взгляд
этот шаг кажется радикальным, но его легко реализо¬
вать, а в структуре этих деревьев нет ничего неприкос¬
новенного: если их можно изменить, чтобы сделать ал¬
горитм более эффективным, это следует сделать. Этот
метод, названный сжатием путей (path compression),
можно легко реализовать, добавив еще один проход по
каждому пути во время выполнения операции union и
снабдив элемент id, соответствующий каждой встречен¬
ной вершине, указателем на корень. В результате дере¬
вья становятся почти полностью плоскими, приближаясь
к идеалу, обеспечиваемому алгоритмом быстрого поис¬
ка, как показано на рис. 1.9. Анализ, устанавливающий
этот факт, исключительно сложен, но сам метод прост
и эффективен. Результат сжатия пути для большого
примера показан на рис. 1.11.
Существует множество других способов реализации
алгоритма сжатия пути. Например, программа 1.4 пред¬
ставляет собой реализацию, которая сжимает пути, зас¬
тавляя каждую связь перескакивать к следующему узлу
на пути вверх по дереву (см. рис. 1.10). Этот метод не¬
сколько проще реализовать, чем полное сжатие путей
(см. упражнение 1.16), но он дает тот же конечный ре¬
зультат. Мы называем этот вариант взвешенным быстрым
объединением посредством сжатия путей делением пополам
(weighted quick-union with path compression by halving). Ka-
®®@®®®®®®
w
© ® ® ® ® ®
®®®®
I®®
РИСУНОК 1.8. ВЗВЕШЕННОЕ БЫСТРОЕ
ОБЪЕДИНЕНИЕ (ХУДШИЙ СЛУЧАЙ)
Наихудший сценарий для
алгоритма взвешенного быстрого
объединения заключается в том,
что каждая операция объедине¬
ния связывает деревья одинако¬
вого размера. Если число
объектов меньше 2п, то рассто¬
яние от любого узла до корня его
дерева меньше п.
кой из этих методов эффективнее? Оправдывает ли дос
тигаемая экономия затраты времени, требующегося для реализации сжатия путей? Су¬
ществует ли какая-либо иная технология, применение которой следовало бы
рассмотреть? Чтобы ответить на эти вопросы, следует внимательнее присмотреться к
алгоритмам и реализациям. Мы вернемся к этой теме в главе 2 в контексте рассмот¬
рения основных подходов к анализу алгоритмов.
Глава 1. Введение 33
Программа 1.4 Сжатие путей делением пополам
Если циклы for в программе 1.3 заменить этим ко¬
дом, то длина любого проходимого пути будет делить¬
ся пополам. Конечный результат этого изменения зак¬
лючается в том, что превращение деревьев в почти
полностью плоские после выполнения длинной после¬
довательности операций.
for (i = р; i != id[i] ; i = id[i])
id[i] = id[id[i]];
for (j = q; j ! = id[j] ; j = id[j])
id[j] = id [id [ j ] ] ;
Конечный результат применения последовательно¬
сти рассмотренных выше алгоритмов для решения
задачи связности близок к наилучшему из тех, на ка¬
кой можно было бы рассчитывать в любом практи¬
ческом смысле. Мы имеем алгоритмы, которые лег¬
ко реализовать и время выполнения которых
гарантированно связано с затратами времени на сбор
данных постоянным коэффициентом. Более того, ал¬
горитмы являются оперативными, они рассматривают
каждое ребро только один раз и используют объем
памяти, пропорциональный количеству объектов; по¬
этому какие-либо ограничения на количество обраба¬
тываемых ими ребер отсутствуют. Результаты экспе¬
риментального исследования, приведенные в табл.
1.1, подтверждают вывод о том, что программа 1.3 и
ее варианты с использованием сжатия путей целесо¬
образно применять даже в крупных практических
приложениях. Выбор лучшего из этих алгоритмов
требует тщательного и сложного анализа (см. главу 2).
Таблица 1.1. Результаты эмпирических исследований
алгоритмов объединения-поиска
Представленные в таблице в относительных единицах
значения времени, затрачиваемого на решение слу¬
чайных задач связности с использованием алгоритмов
объединения-поиска, служат доказательством эффек¬
тивности взвешенной версии алгоритма быстрого
объединения. Дополнительный выигрыш, достигаемый
благодаря использованию сжатия путей менее очеви¬
ден. Здесь М - количество случайных соединений, по¬
строение которых продолжается до тех пор, пока все
N объектов не будут связаны. Этот процесс требует
значительно больше операций find, чем операций
union, поэтому быстрое объединение выполняется на¬
много медленнее быстрого поиска. Ни быстрый поиск,
ни быстрое объединение не годятся для случая, когда
РИСУНОК 1.9. СЖАТИЕ ПУТЕЙ
Пути в деревьях можно сделать
еще короче, просто снабдив все
просматриваемые объекты
указателями на корень нового
дерева, полученного в результате
выполнения операции объединения,
как показано в этих двух приме¬
рах. На диаграмме вверху показан
результат, соответствующий рис.
1.7. В случае коротких путей
алгоритм сжатия путей не
оказывает никакого влияния, но
при обработке пары 16, мы
снабжаем узлы 1, 5 и 6 указате¬
лями на узел 3, в результате чего
дерево становится более плоским,
чем на рис. 1.7. На диаграмме
внизу показан результат, соот¬
ветствующий рис. 1.8. В деревьях
могут появляться пути, которые
содержат больше одной-двух
связей, но при каждом их прохож¬
дении мы делаем их более плоски¬
ми. В данном случае при обработке
пары 6 8 мы делаем дерево более
плоским, снабжая узлы 4, 6 и 8
указателями на узел 0.
34 Часть 1. Анализ
значение N очень велико. Время выполнения взвешенных
методов явно пропорционально значению Л/, поскольку оно
уменьшается вдвое при уменьшении вдвое значения N.
N
М
U
W
Н
1000
6206
14
25
6
5
3
2500
20236
82
210
13
15
12
5000
41913
304
1172
46
26
25
10000
83857
1216
4577
91
73
50
25000
309802
219
208
216
50000
708701
469
387
497
100000
1545119
1071
1106
1096
Обозначения:
F - быстрый поиск (программа 1.1).
U - быстрое объединение (программа 1.2).
W - взвешенное быстрое объединение (программа 1.3).
Р - взвешенное быстрое объединение с сжатием путей
(упражнение 1.16).
Н - взвешенное быстрое объединение с делением попо¬
лам (программа 1.4).
Упражнения
РИСУНОК 1.10. СЖАТИЕ ПУТИ
ДЕЛЕНИЕМ ПОПОЛАМ
Можно уменьшить длину
путей вверх по дереву почти
вдвое, прослеживая две связи
одновременно и устанавливая
нижнюю из них указывающей
на тот же узел, что и
верхняя, как демонстрируется
в этом примере. Конечный
результат выполнения такой
операции для каждого
проходимого пути приближа¬
ется к результату, получае¬
мому в результате полного
сжатия пути.
>1.4. Приведите содержимое массива id после выпол¬
нения каждой операции union при использовании алго¬
ритма быстрого поиска (программа 1.1) для решение
задачи связности для последовательности 0-2, 1-4,
2-5, 3-6, 0-4 и 1-3. Укажите также количество об¬
ращений программы к массиву id для каждой вводи¬
мой пары.
>1.5. Выполните упражнение 1.4, но воспользуйтесь для
этой цели алгоритмом быстрого объединения (программа 1.2).
> 1.6. Приведите содержимое массива id после выполнения каждой операции union
для случаев использования алгоритма взвешенного быстрого объединения примени¬
тельно к примерам, соответствующим рис. 1.7 и 1.8.
>1.7. Выполните упражнение 1.4, но при этом воспользуйтесь алгоритмом взвешен¬
ного быстрого объединения (программа 1.3).
РИСУНОК 1.11. БОЛЬШОЙ ПРИМЕР РЕЗУЛЬТАТА ПРИМЕНЕНИЯ АЛГОРИТМА СЖАТИЯ ПУТЕЙ
Эта диаграмма отображает результат обработки случайных пар 100 объектов алгоритмом взвешен¬
ного быстрого объединения со сжатием путей. Все узлы этого дерева, за исключением двух, находятся
на расстоянии одного-двух шагов от корня.
Глава 1. Введение 35
>1.8. Выполните упражнение 1.4, но при этом воспользуйтесь алгоритмом взвешен¬
ного быстрого объединения со сжатием путей делением пополам (программа 1.4).
1.9. Дайте оценку верхней границы числа машинных инструкций, требуемых для
обработки М соединений УУ объектов при использовании программы 1.3. Напри¬
мер, можно предположить, что для выполнения любого оператора присваивания
языка С всегда требуется выполнение менее с инструкций, где с - некоторая фик¬
сированная константа.
1.10. Определите минимальное время (в днях), которое потребовалось бы для вы¬
полнения быстрого поиска (программа 1.1) с целью решить задачу с 109 объектов и
106 вводимых пар на компьютере, который может выполнять 109 инструкций в се¬
кунду, в предположении, что при каждой итерации внутреннего цикла while дол¬
жно выполняться не менее 10 инструкций.
1.11. Определите максимальное время (в секундах), которое потребовалось бы для
выполнения взвешенного быстрого объединения (программа 1.3) для решения зада¬
чи с 109 объектов и 106 вводимых пар на компьютере, который может выполнять
109 инструкций в секунду. Примите, что при каждой итерации внешнего цикла
while должно выполняться не более 100 инструкций.
1.12. Вычислите среднее расстояние от узла до корня для наихудшего из возмож¬
ных деревьев, то есть, для дерева из 2" узлов, построенного алгоритмом взвешен¬
ного быстрого объединения.
>1.13 Нарисуйте схему, подобную представленной на рис. 1.10, но содержащую во¬
семь, а не девять узлов.
о 1.14. Приведите последовательность вводимых пар, для которой алгоритм взвешен¬
ного быстрого объединения (программа 1.3) создает путь длиной 4.
• 1.15. Приведите последовательность вводимых пар, для которой алгоритм взвешен¬
ного быстрого объединения со сжатием пути длиной 4.
1.16. Покажите, как необходимо изменить программу 1.3, чтобы реализовать полное
сжатие путей, при котором каждая операция union завершается тем, что каждый
обрабатываемый узел указывает на корень нового дерева.
>1.17. Выполните упражнение 1.4, но при этом воспользуйтесь алгоритмом взвешен¬
ного быстрого объединения с полным сжатием путей (упражнение 1.16).
•• 1.18. Приведите последовательность вводимых пар, для которой алгоритм взвешен¬
ного быстрого объединения с полным сжатием путей (см. упражнение 1.16) создает
путь длиной 4.
о 1.19. Приведите пример, показывающий, что модификации быстрого объединения
(программа 1.2) для реализации полного сжатия путей (см. упражнение 1.16) не до¬
статочно, чтобы гарантировать отсутствие длинных путей в деревьях.
• 1.20. Измените программу 1.3 таким образом, чтобы в ней для принятия решения,
что нужно устанавливать, id[i] = j или id[j] = i, вместо веса использова¬
лась высота деревьев (самый длинный путь от любого узла до корня). Выполните
эмпирические исследования с тем, чтобы сравнить этот вариант с программой 1.3.
•• 1.21. Покажите, что свойство 1.3 справедливо для алгоритма, описанного в упраж¬
нении 1.20.
36 Часть 1. Анализ
• 1.22. Измените программу 1.4 таким образом, чтобы она генерировала случайные
пары целых чисел в диапазоне от 0 до N -\ вместо того, чтобы считывать их из
стандартного ввода, и выполняла цикл до тех пор, пока не будет выполнена N -1
операция union. Выполните программу для значений N = 103, 104, 105 и 106 и выве¬
дите суммарное число ребер, построенных для каждого значения N.
• 1.23. Внесите в программу из упражнения 1.22 такие изменения, чтобы она выводи¬
ла в виде графика количество ребер* требуемых для соединения N элементов, при
100 <N< 1000.
•• 1.24. Приведите приближенную формулу для вычисления числа случайных ребер,
необходимых для соединения N объектов, как функции от N.
1.4 Перспективы
Каждый из алгоритмов, рассмотренных в разделе 1.3, по-видимому, является в оп¬
ределенном смысле усовершенствованием предыдущего, но, вероятно, этот процесс
был искусственно упрощен, поскольку мы обладаем преимуществом использования
ретроспективы, связанной с разработкой исследователями самих этих алгоритмов на
протяжении многих лет (см. раздел ссылок). Реализации просты, а задача четко постав¬
лена, поэтому мы можем оценить различные алгоритмы непосредственно, путем эмпи¬
рических исследований. Более того, мы можем подкрепить эти исследования, количе¬
ственно сравнив производительность алгоритмов (см. главу 2). Не все предметные
области, рассмотренные в этой книге, столь же хорошо проработаны, как эта, и мы
обязательно встретимся с алгоритмами, которые трудно с чем-либо сравнить, и с ма¬
тематическими задачами, которые трудно решить. Мы стремимся дать используемым
алгоритмам объективную научно обоснованную оценку, а также обогатить свои зна¬
ния, изучая при этом их свойства путем прогона программных реализаций на факти¬
ческих данных, полученных из приложений, или на случайных тестовых наборах дан¬
ных.
Этот процесс можно рассматривать как прототип изучения различных алгоритмов
решения фундаментальных задач, которые рассматриваются в данной книге. Когда это
возможно, мы проходим через те же базовые этапы, что и при изучении алгоритмов
объединения-поиска, описанных в разделе 1.2. Часть этих этапов сведена в следующий
список:
■ Полная или частичная постановка задачи, включая определение основных абст¬
рактных операций, используемых для решения этой задачи.
■ Тщательная разработка компактной реализации простейшей версии алгоритма.
■ Разработка более совершенных версий реализаций путем пошагового уточне¬
ния, подтверждения эффективности тех или иных идей совершенствования алго¬
ритма посредством эмпирического или математического анализа либо обоих
вместе.
■ Поиск высокоуровневых абстрактных представлений структур данных или гото¬
вых работающих алгоритмов, которые позволяют эффективно проектировать на
высоком уровне абстракции более совершенные версии.
Глава 1. Введение 37
■ Стремление к получению гарантированной производительности в худшем слу¬
чае, когда это возможно, не упуская возможностей получения хорошей произ¬
водительности при работе с реальными данными.
Возможность получить кардинальное повышение производительности алгоритмов
решения реальных задач, подобных рассмотренным в разделе 1.2, превращают разра¬
ботку алгоритмов в увлекательную область исследований. Лишь очень немногие другие
области разработки таят в себе потенциальные возможности обеспечить экономию ре¬
сурсов в миллионы, миллиарды и более раз.
Что еще важнее, так это то, что по мере повышения вычислительной мощности
компьютеров и приложений, разрыв между быстрыми и медленными алгоритмами уве¬
личивается. Новый компьютер может работать в 10 раз быстрее и может обрабатывать
в 10 раз больше данных, чем старый, но при использовании квадратичного алгоритма,
наподобие быстрого поиска, новому компьютеру потребуется в 10 раз больше времени
для выполнения нового задания, чем требовалось старому компьютеру для выполнения
прежнего задания! Вначале это утверждение кажется противоречивым, но его легко
подтвердить простым тождеством (107V)V10 = 10Nn, как будет показано в главе 2. По
мере того как вычислительные мощности увеличиваются, позволяя решать все более
сложные задачи, важность использования эффективных алгоритмов также возрастает.
Разработка эффективного алгоритма приносит моральное удовлетворение и может
обеспечить существенную практическую выгоду. Как следует из примера решения за¬
дачи связности, четко сформулированная задача может послужить стимулом изучения
многочисленных алгоритмов, которые не только полезны и интересны, но и представ¬
ляют собой увлекательную и трудную для понимания задачу. Мы встретимся со многи¬
ми оригинальными алгоритмами, которые были разработаны задолго до возникнове¬
ния множества практических проблем. По мере расширения области применения
компьютерных решений для научных и экономических задач возрастает важность ис¬
пользования эффективных алгоритмов для решения известных задач и разработки эф¬
фективных решений для новых задач.
Упражнения
1.25. Предположим, что взвешенное быстрое объединение используется для обра¬
ботки в 10 раз большего количества соединений на новом компьютере, который
работает в 10 раз быстрее старого. Насколько больше времени потребуется для вы¬
полнения новой задачи на новом компьютере по сравнению с выполнением старой
задачи на старом компьютере?
1.26. Выполните упражнение 1.25 для случая использования алгоритма, для которо¬
го требуется выполнение N инструкций.
3 8 Часть 1. Анализ
1.5 Обзор тем
В этом разделе приведено краткое описание основных частей книги, дается пере¬
чень раскрытых в них конкретных тем и сформулирован общий подход к изучению
материала. Выбор тем диктовался стремлением рассмотреть как можно большее число
базовых алгоритмов. Некоторые из освещенных тем относятся к фундаментальным об¬
ластям компьютерных наук, которые мы подробно рассматриваем с целью изучения
основных алгоритмов широкого применения. Другие обсуждаемые в этой книге алго¬
ритмы относятся к областям компьютерных наук, в которых в настоящее время про¬
водятся наиболее интенсивные исследования, и к связанным с ними областям, таким
как численный анализ и исследование операций - в этих случаях приведенный мате¬
риал служит введением в эти области через исследование базовых методов.
В первых четырех частях, включенных в этот том, освещен наиболее широко ис¬
пользуемое множество алгоритмов и структур данных, представляющее собой первый
уровень абстракции для коллекций объектов с ключами, которые могут поддерживать
широкое множество важных фундаментальных алгоритмов. Алгоритмы, которые мы
будем изучать, являются результатом исследований и разработок, проводившихся на
протяжении десятков лет, они, как и прежде, продолжают играть важную роль во все
расширяющемся применении вычислительных процессов.
Основные принципы (Часть 1) в контексте данной книги представляют собой базо¬
вые принципы и методологию, используемые для реализации, анализа и сравнения ал¬
горитмов. Материал, приведенный в главе 1, служит обоснованием изучения разработ¬
ки и анализа алгоритмов; в главе 2 рассмотрены основные методы получения
информации о количественной оценке производительности алгоритмов.
Структуры данных (Часть 2) тесно связаны с алгоритмами: необходимо получить
ясное представление о методах представления данных, которые используются во всех
остальных частях книги. Изложение материала начинается с введения в базовые струк¬
туры данных в главе 3, включая анализ, связанные списки и строки; затем в главе 5
будут рассмотрены рекурсивные программы и структуры данных, в частности, деревья
и алгоритмы, манипулирующие ими. В главе 4 рассмотрены основные абстрактные
типы данных (abstract data types — ADT), такие как стеки и очереди, а также реализа¬
ции, в которых используются элементарные структуры данных.
Алгоритмы сортировки (Часть 3), предназначенные для упорядочения файлов, име¬
ют особую важность. Мы достаточно глубоко рассмотрим ряд базовых алгоритмов, в
том числе быструю сортировку, сортировку слиянием, пирамидальную сортировку и
поразрядную сортировку. В ходе изучения этих алгоритмов мы встретимся с несколь¬
кими связанными с ними задачами, в том числе с очередями по приоритету, задачи
выбора и слияния. Многие из этих алгоритмов служат основой для других алгоритмов,
рассматриваемых в последующих частях книги.
Алгоритмы поиска (Часть 4), предназначенные для поиска конкретных элементов в
больших коллекциях элементов, также играют важную роль. Мы рассмотрим основ¬
ные и расширенные методы поиска с использованием деревьев и преобразований
численных ключей, в том числе деревья цифрового поиска, сбалансированные дере¬
вья, хеширование и trie-деревья, а также методы, которые подходят для работы с
очень крупными файлами. Мы отметим взаимосвязь между этими методами, приведем
Глава 1. Введение 39
статистические данные об их сравнительной производительности и установим их соот¬
ветствие методам сортировки.
В частях с 5 по 8, которые вынесены в отдельный том, освещены современные
применения описанных здесь алгоритмов для другого множества приложений - для
второго уровня абстракций, характерных для ряда важнейших областей применения.
Кроме того, в этих частях более глубоко рассматриваются технологии разработки и
анализа алгоритмов. Многие из затрагиваемых задач являются объектом исследований,
проводимых в настоящее время.
Алгоритмы на графах (Часть 5) полезны при решении ряда сложных и важных за¬
дач. Общая стратегия поиска на графах разрабатывается и применяется к фундамен¬
тальным задачам связности, в том числе к задаче отыскания кратчайшего пути, пост¬
роения минимального остовного дерева, к задаче о потоках в сети и к задаче о
паросоченаниях. Унифицированный подход к этим алгоритмам показывает, что в их
основе лежит одна и та же процедура, и что эта процедура базируется на основном
абстрактном типе данных очереди по приоритету.
Алгоритмы обработки строк (Часть 6) включают в себя ряд методов обработки (длин¬
ных) последовательностей символов. Поиск в строке приводит к сопоставлению с этало¬
ном, что, в свою очередь, ведет к синтаксическому анализу. В этой части также рассмат¬
риваются и технологии сжатия файлов. Опять-таки, введение в актуальные темы
выполняется через анализ некоторых простых задач, которые важны и сами по себе.
Геометрические алгоритмы (Часть 7) - это методы решения задач с использовани¬
ем точек и линий (и других простых геометрических объектов), которые вошли в
употребление совсем недавно. Мы рассмотрим алгоритмы поиска выпуклых оболочек,
заданных набором точек, определения пересечений геометрических объектов, решения
задач отыскания ближайших точек и алгоритма многомерного поиска. Многие из этих
методов прекрасно дополняют более простые методы сортировки и поиска.
Усложненные темы (Часть 8) устанавливают соответствие между изложенным в
книге материалом и несколькими связанными областями. Изложение материала начи¬
нается с рассмотрения базовых подходов к разработке и анализу алгоритмов, в том
числе алгоритмов типа "разделяй и властвуй", динамического программирования, ран¬
домизации и амортизации. Мы дадим обзор линейного программирования, быстрого
преобразования Фурье, NP-полноты и других актуальных тем для получения общего
представления о ряде областей изучения, интерес к которым поровдается элементар¬
ными проблемами, с которыми мы сталкиваемся в этой книге.
Изучение алгоритмов представляет большой интерес, поскольку это сравнительно
новая предметная область (почти все изученные в этой книге алгоритмы не старше 50
лет, а некоторые были открыты совсем недавно) с богатыми традициями (некоторые
алгоритмы известны уже в течение тысяч лет). Постоянно появляются все новые от¬
крытия, но лишь немногие алгоритмы исследованы полностью. В этой книге мы рас¬
смотрим замысловатые, сложные и трудные алгоритмы, наряду с изящными, просты¬
ми и легко реализуемыми алгоритмами. Наша задача - понять первые и оценить
вторые в контексте множества различных потенциально возможных применений. В
процессе всего этого нам предстоит исследовать ряд полезных инструментальных
средств и выработать стиль алгоритмического мышления, который пригодится при ре¬
шении предстоящих трудных вычислительных задач.
Принципы
анализа
алгоритмов
Анализ - это ключ к пониманию алгоритмов в степени,
достаточной для их эффективного применения при ре¬
шении практических задач. Хотя у нас нет возможности
проводить исчерпывающие эксперименты и глубокий ма¬
тематический анализ каждой программы, мы будем рабо¬
тать в рамках базового подхода, предусматривающего как
эмпирическое тестирование, так и приближенный анализ,
которые помогут нам в изучении базовых рабочих харак¬
теристик разрабатываемых алгоритмов, чтобы мы имели
возможность сравнивать различные алгоритмы и приме¬
нять их для решения практических задач.
Сама идея точного описания рабочих характеристик
сложного алгоритма с помощью математического анализа
кажется на первый взгляд устрашающей перспективой,
поэтому мы часто обращаемся к исследовательской лите¬
ратуре за результатами подробных математических иссле¬
дований. Хотя целью данной книги не является обзор ме¬
тодов анализа или обобщение их результатов, нам важно
знать, что мы стоим на твердой теоретической почве при
сравнении различных методов. Более того, посредством
аккуратного использования небольшого числа относитель¬
но простых методов можно получить большое количество
подробной информации о многих важных алгоритмах. На
протяжении всей этой книги основное внимание мы уде¬
ляем фундаментальным аналитическим результатам и мето¬
дам анализа, особенно, когда это облегчает понимание
внутренней работы фундаментальных алгоритмов. В этой
главе наша основная цель заключается в описании среды
и инструментальных средств, необходимых для работы с
алгоритмами.
Глава 2. Принципы анализа алгоритмов
41
В главе 1 представлен контекст, который служит иллюстрацией многих базовых по¬
нятий анализа алгоритмов, поэтому мы будем часто ссылаться на рабочие характерис¬
тики алгоритмов объединения-поиска, прежде всего, на их производительность, для
конкретизации определенных моментов. В разделе 2.6 мы подробно рассмотрим также
несколько новых примеров.
Анализ играет важную роль на всех стадиях процесса проектирования и реализа¬
ции алгоритмов. Прежде всего, как мы уже могли убедиться, можно сократить время
выполнения программы в тысячи и даже миллионы раз за счет правильного выбора
алгоритма. Чем больше эффективных алгоритмов мы изучаем, тем труднее становится
задача выбора одного из них, поэтому необходимо подробно изучать свойства алго¬
ритмов. В своем стремлении получить наилучший (в некотором точном техническом
смысле) алгоритм, мы будем находить алгоритмы, полезные для решения сложных
вопросов, как в практическом, так и в теоретическом плане.
Полное описание методов анализа алгоритмов сам по себе является темой, достой¬
ной отдельной книги (см. раздел ссылок), однако здесь рассматриваются основы, кото¬
рые позволяют:
■ Проиллюстрировать процесс.
■ Описать в одном месте используемые математические соглашения.
■ Обеспечить основу для обсуждения проблем высокого уровня.
■ Дать оценку научного обоснования выводов, полученных при сравнении конк¬
ретных алгоритмов.
Следует отметить, что сами алгоритмы и их анализ зачастую переплетаются. В этой
книге мы не станем глубоко пускаться в сложные математические рассуждения, но в
то же время проведем достаточное количество математических выкладок, чтобы по¬
нять, что представляют собой наши алгоритмы и что нужно, чтобы использовать их с
максимальной эффективностью.
2.1. Реализация и эмпирический анализ
Мы разрабатываем и реализуем алгоритмы, создавая иерархию абстрактных опера¬
ций, которые помогают понять природу вычислительных задач, которые мы хотим ре¬
шить. При теоретическом изучении данный процесс, хотя он достаточно важен, может
увести очень далеко от практических задач, которые мы призваны решать. Поэтому в
данной книге мы стоим на твердой почве, формулируя все рассматриваемые нами ал¬
горитмы в реальным языке программирования, а именно, в языке С. При таком под¬
ходе различие между алгоритмом и его реализацией иногда становится довольно рас¬
плывчатым, но это лишь небольшая плата за возможность работать с конкретной
реализацией и на ней же учиться.
В самом деле, правильно разработанные программы на конкретном языке про¬
граммирования представляют собой эффективные методы формулирования алгорит¬
мов. В этой книге мы изучаем множество важных и эффективных алгоритмов, пред¬
ставленных в виде компактных и точных реализаций на языке С. Описания
алгоритмов на обычном языке или их представление с использованием абстракций вы¬
сокого уровня зачастую утрачивают конкретность и полноту; а практические реализа¬
42 Часть 1. Анализ
ции заставляют нас находить экономные представления, не позволяющие утонуть в де¬
талях.
Мы выражаем алгоритмы на языке программирования С, но в этой книге речь
идет об алгоритмах, то есть это не учебник по программированию на С. Разумеется,
мы рассматриваем реализации на С многих важных задач, и когда существует удоб¬
ный и эффективный способ решить задачу именно средствами С, мы непременно вос¬
пользуемся этой возможностью. Тем не менее, подавляющее большинство решений,
принимаемых относительно реализации алгоритмов, можно применять в любой совре¬
менной среде программирования. Перевод программ, рассмотренных в главе 1, или
любых других программ из этой книги на другой современный язык программирова¬
ния не представляет особых трудностей. В тех случаях, когда какой-либо другой язык
обеспечивает более эффективный механизм решения тех или иных задач, мы будем
указывать на это. Наша цель - использовать язык С как средство для выражения рас¬
сматриваемых нами алгоритмов, а не тратить время на изучение особенностей этого
языка программирования.
Если алгоритм реализуется как часть крупной системы, мы используем абстракт¬
ные типы данных или похожий механизм, чтобы иметь возможность изменить алгорит¬
мы или детали реализации после того, как станет ясно, какая часть системы заслужи¬
вает наиболее пристального внимания. Однако с самого начала мы должны иметь
правильное представление о рабочих характеристик каждого алгоритма, так как тре¬
бования системы к проектированию могут в значительной степени повлиять на произ¬
водительность алгоритма. Подобные проектные решения, имеющие далеко идущие по¬
следствия, необходимо принимать с осторожностью, поскольку в конечном итоге часто
оказывается, что производительность всей системы зависит от производительности не¬
которых базовых алгоритмов, подобных тем, что обсуждаются в этой книге.
Реализации алгоритмов, изучаемых в этой книге, нашли эффективное применение
в разнообразных крупных программах, операционных системах и прикладных прило¬
жениях. Мы намерены дать описания этих алгоритмов и провести исследования их ди¬
намических свойств, экспериментируя с доступными реализациями. Для одних прило¬
жений в реализации не нужно вносить никаких изменений, для других может
потребоваться определенная доработка. Например, при реализации некоторых практи¬
ческих приложений оправдано применение стиля безопасного программирования, от¬
личного от того, что используется в данной книге. Необходимо отслеживать возникно¬
вение ошибок и сообщать о них, а, кроме того, программы должны быть разработаны
таким образом, чтобы их изменение было несложным делом, чтобы их могли быстро
читать и понимать другие программисты, чтобы они хорошо состыковывались с раз¬
личными частями системы и чтобы сохранялась возможность их переноса в другие
среды.
Не отвергая все эти соображения, мы, тем не менее, применяем подход, согласно
которому при анализе каждого алгоритма основное внимание будет уделяться самым
важным рабочим характеристикам алгоритма, при этом производительность является
одной из них. Основной наш интерес вызывают алгоритмы с наилучшими показателя¬
ми производительности, особенно если они к тому же просты в реализации.
Для эффективного использования алгоритмов, когда нашей целью является реше¬
ние крупной задачи, которую нельзя решить другим способом, или когда цель заклю¬
Глава 2. Принципы анализа алгоритмов
43
чается в эффективной реализации критически важной части системы, нам требуется
понимание рабочих характеристик алгоритмов. Формирование такого понимания и яв¬
ляется целью анализа алгоритмов.
Один из первых шагов при продвижении вперед в понимании рабочих характерис¬
тик алгоритмов является проведение эмпирического анализа (empirical analysis). Если два
алгоритма могут решать одну и ту же задачу, то в этом методе нет ничего сверхъесте¬
ственного: мы выполняем прогон обоих алгоритмов и определяем, какой из них вы¬
полняется дольше! Это метод может показаться очевидным, не стоящим нашего вни¬
мания, но, тем не менее, им довольно часто пренебрегают при сравнительном анализе
алгоритмов. Тот факт, что один алгоритм в 10 раз быстрее другого, вряд ли ускольз¬
нет от внимания тех, кто ждет 3 секунды при выполнении одного и 30 секунд - при
выполнении другого, однако при проведении математического анализа его легко упус¬
тить как небольшой постоянный фактор, учитывающий непроизводительные затраты
ресурсов. Когда мы отслеживаем производительность точных реализаций алгоритмов
при типовом вводе, мы получаем результаты, которые не только являются непосред¬
ственным показателем их эффективности, но и содержат информацию, необходимую
для сравнения алгоритмов и подтверждения результатов, полученных путем примене¬
ния методов математического анализа (см., например, табл. 1.1). Когда эмпирическое
изучение поглощает много времени, на помощь приходит математический анализ.
Ожидание завершения программы в течение часа или целого дня едва ли может рас¬
сматриваться как продуктивный способ для понимания того, что программа работает
медленно, особенно в тех случаях, когда простой анализ приводит к тому же
результату.
Первая проблема, возникающая перед нами при эмпирическом анализе — это раз¬
работка правильной и полной реализации. Для некоторых сложных алгоритмов эта
проблема может оказаться труднопреодолимым препятствием. Соответственно, с помо¬
щью анализа или на основании опыта, полученного при работе с похожими програм¬
мами, мы обычно хотим в том или ином виде получить некоторых критерий, насколь¬
ко эффективной может оказаться программа, прежде чем тратить какие-либо усилия
на ее реализацию.
Вторая проблема, с которой мы сталкиваемся при эмпирическом анализе, — это
определение природы входных данных и других факторов, оказывающих прямое влия¬
ние на проводимые эксперименты. Обычно существуют три основных возможности:
реальные данные, случайные данные и искаженные данные. Реальные данные позволяют
точно измерить параметры используемой программы; случайные данные гарантируют,
что наши эксперименты тестируют алгоритм, а не данные; искаженные (то есть, заве¬
домо ошибочные) данные гарантируют, что наши программы способны воспринимать
любой направляемый им ввод. Например, при тестировании алгоритмов сортировки
мы прогоняем их на данных, в качестве которых берем слова из книги "Моби Дик",
на сгенерированных случайным образом целых числах и на числовых файлах, все числа
которых принимают одно и то же значение. Задача определения, какие данные необходи¬
мо использовать для сравнения алгоритмов, возникает также и при анализе алгоритмов.
При сравнении различных реализаций легко допустить ошибки, особенно, если ал¬
горитмы выполняются на разных машинах, если используются различные компиляторы
или системы, или если сравниваются крупные программы с нечетко заданным вводом.
44 Часть 1. Анализ
Опасность получения неверной оценки при эмпирическом сравнении программ таится
в том, что программный код одной реализации может быть разработан более каче¬
ственно, чем код другой. Изобретателю предлагаемого нового алгоритма, по-видимо¬
му, придется принять во внимание все аспекты его реализации, чтобы не тратить
слишком много усилий на создание классического конкурирующего алгоритма. Чтобы
быть уверенным в точности эмпирического сравнения алгоритмов, мы должны быть
уверены, что всем его реализациям было уделено одинаковое внимание.
Один из подходов, который часто применяется в этой книге, как это видно из гла¬
вы 1, заключается в построении алгоритмов за счет внесения небольших изменений в
другие алгоритмы решения той же задачи, поэтому сравнительное исследование про¬
сто необходимо. В более общем смысле, мы стараемся определить основные абстракт¬
ные операции и проводим сравнение алгоритмов на базе того, как они используют
эти операции. Например, эмпирические результаты, приведенные в табл. 1.1, эмпири¬
чески устойчивы при сравнении языков и сред программирования, поскольку в них
используются похожие программы, оперирующие одним и тем же набором базовых
операций. Для реальной среды программирования эти числа можно поставить в соот¬
ветствие с реальными значениями времени выполнения. Чаще всего просто требуется
узнать, какая из двух программ будет быстрее или до какой степени определенное изме¬
нение может улучшить временные либо пространственные характеристики программы.
Выбор среди алгоритмов, решающих данную задачу, наиболее подходящего, являет¬
ся нелегким делом. Возможно, наиболее распространенной ошибкой при выборе алго¬
ритма является пренебрежение его рабочими характеристиками. Быстродействующие
алгоритмы, как правило, сложнее, чем решения "в лоб", а разработчики часто предпо¬
читают более медленные алгоритмы, дабы избежать дополнительных сложностей. Одна¬
ко, как мы убедились на примере алгоритмов объединения-поиска, можно добиться су¬
щественной экономии ресурсов с помощью всего лишь нескольких строк
программного кода. Как ни странно, но пользователи многочисленных компьютерных
систем теряют много времени, применяя для решения задачи простые квадратичные
алгоритмы, в то время как доступные N\ogN или линейные алгоритмы ненамного
сложнее и могут решить ту же задачу значительно быстрее. Когда мы имеем дело с
крупными задачами, у нас нет другого выбора, как искать наилучший алгоритм, что и
будет показано далее.
Возможно, вторую очень распространенную ошибку при выборе алгоритма мы со¬
вершаем, когда уделяем слишком много внимания его рабочим характеристикам. Сни¬
жение времени выполнения программы в 10 раз несущественно, если ее выполнение
занимает несколько микросекунд. Даже если выполнение программы длится несколь¬
ких минут, время и усилия, необходимые, чтобы она стала выполняться в 10 раз быст¬
рее, могут не стоить того, особенно, если программа должна применяться всего лишь
несколько раз. Суммарное время, требуемое для реализации и отладки улучшенного
алгоритма, может быть значительно выше, чем время, необходимое для выполнения
несколько более медленного варианта программы, — в конце концов, часть этой ра¬
боты вполне можно возложить на компьютер. Еще хуже, можно потратить значитель¬
ное количество времени и усилий, реализуя идеи, которые должны были бы улучшить
программу, но, фактически, не делают этого.
Глава 2. Принципы анализа алгоритмов
45
Мы не можем провести эмпирическое тестирование программы, которая еще не
написана, но можем проанализировать свойства будущей программы и оценить потен¬
циальную эффективность предлагаемого улучшения. Не все предполагаемые усовер¬
шенствования дают реальный выигрыш в производительности, поэтому нужно оцени¬
вать степень улучшений на каждом шаге. Более того, в реализации алгоритма мы
можем включить те или иные параметры в наши реализации, а анализ поможет нам
правильно установить их значения. Важнее всего то, что, достигнув понимания фунда¬
ментальных свойств созданных нами программ и базовой природы того, как эти про¬
граммы используют ресурсы, мы получаем потенциальную возможность рассчитать их
эффективность на компьютерах, которые еще не созданы, или сравнить их с новыми
алгоритмами, которые еще не представлены в виде компьютерных программ. В разде¬
ле 2.2 в общих чертах описана методология достижения базового понимания того, как
работают алгоритмы.
Упражнения
2.1. Переведите программы из главы 1 на другой язык программирования и от¬
ветьте на вопросы упражнения 1.22 применительно к полученным реализациям.
2.2. Сколько времени займет посчитать до 1 миллиарда (не учитывая переполне¬
ние)? Определить количество времени, необходимое для выполнения программе
int i, j, k, count = 0;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 0; k < N; k++)
count++;
в выбранной вами среде для N = 10, 100 и 1000. Если в используемом вами компи¬
ляторе заложены свойства оптимизации, предназначенные для повышения эффек¬
тивности программ, проверьте, позволяют ли они повысить эффективность вашей
программы.
2.2 Анализ алгоритмов
В этом разделе мы наметим, в каких пределах математический анализ может играть
важную роль в процессе сравнения производительности алгоритмов, преследуя при
этом цель заложить фундамент, необходимый для понимания основных результатов
математического анализа, примененного к фундаментальным алгоритмам, которые мы
будем изучать на протяжении всей этой книги. Мы рассмотрим основные математи¬
ческие инструментальные средства, используемые для анализа алгоритмов, которые
позволят изучать классические примеры анализа фундаментальных алгоритмов с тем,
чтобы воспользоваться результатами исследовательской литературы, которые помогут
правильно оценить рабочие характеристики полученных нами алгоритмов.
Среди причин, которые побуждают нас выполнять математический анализ алгорит¬
мов, отметим следующие:
■ Для сравнения разных алгоритмов, предназначенных для решения одной задачи.
■ С целью прогнозирования оценки производительности алгоритма в новой среде.
■ Для выбора значений различных параметров алгоритма.
46 Часть J. Анализ
На протяжении этой книги можно будет найти немало примеров проявления каж¬
дой из этих причин. Для некоторых таких задач эмпирического анализа будет вполне
достаточно, однако математический анализ, как будет показано ниже, может оказаться
более информативным (к тому же менее дорогим!).
Анализ алгоритмов может оказаться достаточно трудоемким делом. Некоторые из
алгоритмов, приведенных в этой книге, понятны до такой степени, что даже известны
точные математические формулы для расчета времени выполнения в реальных ситуа¬
циях. Эти формулы разрабатываются путем тщательного изучения программы с целью
вычисления времени выполнения в терминах фундаментальных математических вели¬
чин и последующего математического анализа соответствующих числовых значений. С
другой стороны, рабочие характеристики других алгоритмов, изучаемых в этой книге,
не поняты до конца, возможно, потому, что их анализ приводит к нерешенным мате¬
матическим вопросам или же известные реализации слишком сложны, чтобы их под¬
робный анализ имел смысл, или (скорее всего) типы входных данных не поддаются
точному описанию.
Несколько важных факторов, обеспечивающих точность анализа, обычно находятся
за пределами заданной области влияния программиста. Во-первых, программы на язы¬
ке С переводятся в машинные коды компьютера конкретного типа, и задача опреде¬
лить, сколько времени займет выполнение даже одного оператора С (особенно в сре¬
де, где возможен совместный доступ к ресурсам так, что одна и та же программа
может иметь различные рабочие характеристики в разные моменты времени), может
оказаться достаточно сложной. Во-вторых, многие программы чрезвычайно чувстви¬
тельны к входным данным, поэтому их производительность может меняться в широ¬
ких пределах в зависимости от ввода. В-третьих, многие интересующие нас програм¬
мы еще не получили должной оценки, поэтому для них пока не существует
конкретных математических результатов. И, в заключение, две программы могут ока-
; заться вообще несравнимыми: в частности, когда одна работает эффективно с каким-
то одним типом входных данных, в то время как другая эффективно выполняется в
других обстоятельствах.
Несмотря на все эти факторы, часто можно с достаточной точностью предсказать,
"сколько времени займет выполнение конкретной программы, или понять, что в опре¬
деленных ситуациях одна программа будет выполняться эффективнее другой. Более
того, часто эти сведения можно получить, пользуясь ограниченным набором математи¬
ческих средств. Задача аналитика алгоритмов - получить как можно больше информа¬
ции о рабочих характеристиках алгоритмов; задача программиста заключается в том,
чтобы использовать эту информацию при выборе алгоритмов для конкретных прило¬
жений. В этом и в нескольких следующих разделах основное внимание мы будем уде¬
лять идеализированной среде аналитика. Чтобы эффективно применять лучшие алго¬
ритмы, нам иногда придется погружаться в эту среду.
Первый шаг при анализе алгоритма состоит в определении абстрактных операций,
которые положены в его основу, с целью отделить анализ от реализации. Так, напри¬
мер, мы отделяем вычисление, сколько раз одна из реализаций алгоритма объединения-
поиска выполняет фрагмент i = a[i] программного кода, от подсчета, сколько
наносекунд может потребоваться для выполнения этого фрагмента на конкретном
компьютере. Для определения фактического времени выполнения программы на ком¬
Глава 2. Принципы анализа алгоритмов
пьютере заданного типа нужны оба эти элемента. Первый из них определяется свой¬
ствами алгоритма, второй — свойствами компьютера. Такое разделение зачастую по¬
зволяет сравнивать алгоритмы способом, который не зависит от конкретной реализа¬
ции или от конкретного типа компьютера.
Хотя количество используемых абстрактных операций может оказаться очень боль¬
шим, в принципе, производительность алгоритма обычно зависит от нескольких вели¬
чин, причем наиболее важные для анализа величины, как правило, определить не¬
сложно. Один из способов их определения заключается в использовании механизма
профилирования (механизма, доступного во многих реализациях языка С, который
включает в себя счетчик частоты выполнения каждой инструкции) для нахождения
наиболее часто исполняемых фрагментов программы по результатам нескольких проб¬
ных запусков. Или же, подобно алгоритму объединения-поиска, описанному в разделе
1.3, наша реализация может быть построена всего лишь на нескольких абстрактных
операциях. В любом случае, анализ сводится к определению частоты исполнения не¬
скольких фундаментальных операций. Наш образ действия заключается в том, чтобы
найти приблизительные оценки этих величин, будучи уверенными, что для важных
программ при необходимости можно будет выполнить более полный анализ. Более
того, как будет показано далее, часто можно пользоваться приближенными аналити¬
ческими результатами в сочетании с эмпирическими исследованиями, чтобы прогнози¬
ровать производительность многих алгоритмов достаточно точно.
Кроме того, необходимо проводить исследования самих данных и моделировать их
ввод, с которым алгоритму придется иметь дело. Чаще всего мы будем рассматривать
один из двух подходов к анализу: мы либо будем предполагать, что ввод является слу¬
чайным, и изучать производительность программы для среднего случая (average-case),
либо будем рассматривать вырожденный ввод и изучать производительность програм¬
мы в худшем случае (worst case). Процесс описания случайного ввода для многих алго¬
ритмов сложен, но для многих других алгоритмов он может оказаться достаточно про¬
стым и приводить к аналитическим результатам, содержащим полезную информацию.
Средний случай может оказаться математической фикцией, не имеющей представле¬
ния в виде данных, для обработки которых используется данная программа, а худший
случай может быть представлен причудливой конструкцией, которая никогда не встре¬
чается на практике. Тем не менее, в большинстве случаев такие виды анализа предос¬
тавляют полезную информацию о производительности алгоритма. Например, мы мо¬
жем сравнивать аналитические и эмпирические результаты (см. раздел 2.1). Если они
совпадут, то возрастает наше доверие к обоим этим видам исследований; если они не
совпадут, мы сможем узнать больше об алгоритме и модели, изучив несоответствия.
В следующих трех разделах мы кратко рассмотрим математический инструмента¬
рий, которым будем пользоваться на протяжении всей этой книги. Этот материал вы¬
ходит за пределы избранной нами основной темы, поэтому читатели.с хорошей мате¬
матической подготовкой, либо те из них, кто не намерен подробно проверять наши
математические выкладки, касающиеся производительности алгоритмов, могут сразу
перейти к разделу 2.6, чтобы вернуться к этому материалу позже, когда в этом воз¬
никнет необходимость. Математические выкладки, в общем случае не сложны для по¬
нимания и очень близки к сути разрабатываемого алгоритма, поэтому те, кто стремит¬
ся эффективно использовать компьютер, не должны их игнорировать.
48 Часть 1. Анализ
Прежде всего, в разделе 2.3 рассматриваются математические функции, которые
нам нужны для описания рабочих характеристик алгоритмов. Затем, в разделе 2.4 рас¬
сматривается О-нотация (O-notation) и понятие пропорционально (is proportional to), кото¬
рое позволит нам опускать детали при математическом анализе. Далее, в разделе 2.5
изучается понятие рекуррентных соотношений (recurrence relations), основного аналити¬
ческого инструмента, используемого для представления рабочих характеристик алго¬
ритма в математических выражениях. Следуя этому обзору, в разделе 2.6 приводятся
примеры, в которых все эти инструментальные средства применяются для анализа
конкретных алгоритмов.
Упражнения
• 2.3. Найдите выражение вида со + ctN + c^N2 + C3N1, которое точно описывает
время выполнения программы из упражнения 2.2. Сравните время, прогнозируемое
этим выражением, с реальным при N = 10, 100 и 1000.
• 2.4. Найдите выражение, которое точно описывает время выполнения программы
1.1 в величинах М и N.
2.3 Рост функций
Для большинства алгоритмов главным параметром (primary parameter) является TV, ко¬
торый оказывает существенное влияние на время их выполнения. Параметр N может
быть степенью полинома, размером файла при сортировке или поиске, количеством
символов в строке или некоторой другой абстрактной мерой размера рассматривае¬
мой задачи: чаще всего, он прямо пропорционален величине обрабатываемого набора
данных. Когда таких параметров существует более одного (например, М и N в алго¬
ритмах объединения-поиска, которые обсуждались в разделе 1.3), мы часто сводим ана¬
лиз к одному параметру, задавая его как функцию от других параметров или рассмат¬
ривая одновременно только один параметр (считая остальные постоянными). Таким
образом, мы ограничиваем себя рассмотрением только одного параметра N без потери
общности. Нашей целью является выражение требований к ресурсам, предъявляемых
разрабатываемыми нами программами (как правило, это время выполнения) в зависи¬
мости от N с использованием максимально простых математических формул, которые
обеспечивают точность расчетов для больших значений параметров. Алгоритмы, изуча¬
емые в этой книге, обычно имеют время выполнения, пропорциональное одной из
следующих функций:
1 Большинство инструкций большинства программ выполняется один или мак¬
симум несколько раз. Если все инструкции программы обладают этим свой¬
ством, мы говорим, что время выполнения программы постоянно (constant).
log N Когда время выполнения программы описывается логарифмической
(logarithmic) зависимостью, программа немного утрачивает быстродействие с
ростом N. Такое время выполнения обычно характерно для программ, кото¬
рые сводят крупную задачу к некоторой последовательности задач меньше¬
го размера, уменьшая на каждом шаге размер задачи на некоторую неболь¬
шую часть. В интересующем нас диапазоне мы будем рассматривать время
выполнения как величину, не превосходящую некоторое большое постоян¬
Глава 2. Принципы анализа алгоритмов
49
ное значение. Основание логарифма изменяет это значение, но ненамного:
когда N - тысяча, logTV равно 3, если основание равно 10, либо примерно
10, если основание равно 2; когда N равно миллиону, значения logyV всего
лишь удвоится. При удвоении N значение logjV возрастет на постоянную ве¬
личину, а удваивается лишь, когда N увеличится до N2.
N Когда время выполнения программы линейно (linear), это обычно означает,
что каждый элемент ввода подвергается небольшой обработке. Когда N рав¬
но миллиону, такого же порядка и время выполнения алгоритма. Когда N
удваивается, то же происходит и со временем выполнения. Эта ситуация оп¬
тимальна для алгоритма, который должен обработать N вводов (или произве¬
сти N выводов).
TVIog N Время выполнения, пропорциональное N \ogN имеет место, когда алгоритм
решает задачу, разбивая ее на подзадачи меньших размеров, решая их неза¬
висимо и затем объединяя решения. Из-за отсутствия подходящего прилага¬
тельного ("линерифмический" - Tinerithmic"?) мы просто говорим, что время
выполнения такого алгоритма равно N log N. Когда N равно 1 миллион,
N log N возрастает примерно до 20 миллионов. Когда N удваивается, то вре¬
мя выполнения возрастает более чем вдвое (но не намного более).
N2 Когда время выполнения алгоритма является квадратичным (quadratic), он
полезен для практического использования применительно к небольшим зада¬
чам. Квадратичное время выполнения обычно характерно для алгоритмов,
которые обрабатывают все элементы данных парами (возможно, в цикле
двойного уровня вложения). Когда N равно одной тысяче, время выполне¬
ния равно одному миллиону. Когда N удваивается, время выполнения увели¬
чивается в четыре раза.
N3 Аналогичный алгоритм, обрабатывающий элементы данных тройками (воз¬
можно, в цикле тройного уровня вложения), имеет кубическое (cubic) время
выполнения и практически применим лишь для решения малых задач. Когда
N равно 100, время выполнения равно 1 миллиону. Когда N удваивается,
время выполнения увеличивается в восемь раз.
2n Лишь немногие алгоритмы с экспоненциальным (exponential) временем выпол¬
нения имеют практическое применение, хотя такие алгоритмы возникают ес¬
тественным образом при попытках решения задачи "в лоб". Когда N равно
20, время выполнения равно 1 миллиону. Когда N удваивается, время выпол¬
нения увеличивается в четыре раза!
Время выполнения конкретной программы, скорее всего, будет некоторой кон¬
стантой, умноженной на одно из перечисленных выше выражений (главный член —
leading term) плюс некоторые слагаемые меньшего порядка. Значения постоянного ко¬
эффициента и остальных слагаемых зависят от результатов анализа и деталей реализа¬
ции. В грубом приближении коэффициент при главном члене связан с количеством
инструкций во внутреннем цикле: на любом уровне разработки алгоритма разумно со¬
кратить количество таких инструкций. Для больших jV доминирует главный член, для
малых N или в случае тщательно разработанных алгоритмов свой вклад вносят и дру-
50 Часть L Анализ
гие слагаемые, поэтому сравнение алгоритмов стано¬
вится более сложным. В большинстве случаев мы бу¬
дем называть время выполнения программ просто "ли¬
нейным", "yVlogjV", "кубическим" и т.д. Обоснование
такого предложения подробно рассматривается в раз¬
деле 2.4.
В итоге, чтобы уменьшить общее время выполне¬
ния программы, мы минимизируем количество инст¬
рукций во внутреннем цикле. Каждую инструкцию не¬
обходимо подвергнуть исследованию: нужна ли она
вообще? Существует ли более эффективный способ
выполнить ту же задачу? Некоторые программисты
считают, что автоматические инструменты, содержа¬
щиеся в современных компиляторах, могут создавать
наилучший машинный код; другие утверждают, что
наилучшим способом является написание внутренних
циклов вручную на машинном языке, или ассемблере.
Как правило, мы будем воздерживаться от рассмотре¬
ния вопросов оптимизации на таком уровне, хотя вре¬
мя от времени будем указывать, сколько машинных
инструкций требуется для выполнения определенных
операций, чтобы показать, почему на практике одни
алгоритмы могут оказаться быстрее других.
Для малых задач то, каким методом мы воспользу¬
емся, практически не имеет значения — быстрый со¬
временный компьютер все равно выполнит такую за¬
дачу мгновенно. Но по мере роста размера задачи,
числа, с которыми мы имеем дело, становятся огром-
секунды
102
1.7 минуты
ю4
2.8 часа
ю5
1.1 дня
10®
1.6 недели
107
3.8 месяца
108
3.1 года
109
3.1 десятилетия
10'°
3.1 столетия
ю11
никогда
РИСУНОК 2.1 ПЕРЕВОД СЕКУНД
Огромная разница между такими
числами, как 10* и l(f, становит¬
ся более очевидной, когда мы
применяем их для измерения
промежутков времени, а затем
переводим в привычные единицы
измерения времени. Мы можем
позволить программе выполняться
2.8 часа, но вряд ли мы захотим
иметь дело с программой, выполне¬
ние которой займет 3.1 года.
Поскольку 2ю примерно равно 103,
этой таблицей можно воспользо¬
ваться и для перевода степеней 2
в привычные единицы времени.
Например, 232 секунд составляют
примерно 124 года.
ными, как показано в табл. 2.1. Когда количество ис¬
полняемых инструкций медленным алгоритмом становится по-настоящему огромным,
время, необходимое для их выполнения, становится неприемлемым, даже если будут
использованы самые быстрые компьютеры. На рис. 2.1 приведен перевод большого
количества секунд в дни, месяцы, годы и т.д.; в табл. 2.1 показаны примеры того, что
выбор быстрого алгоритма имеет больше возможностей решить задачу за приемлемое
время, чем даже самые быстродействующие компьютеры.
Таблица 2.1 Время для решения крупных задач
Для многих приложений нашим единственным шансом решить крупную задачу остает¬
ся использование эффективного алгоритма. В этой таблице показано минимальное ко¬
личество времени, необходимое для решения задач размером 1 миллион и 1 милли¬
ард с использованием линейных алгоритмов, алгоритмов с зависимостью N log N и
квадратичных алгоритмов на компьютерах с быстродействием 1 миллион, 1 миллиард
и 1 триллион операций в секунду. Быстрый алгоритм помогает существенно ускорить
решение задачи на медленной машине, однако быстрая машина не сможет выручить,
когда используется медленный алгоритм.
Глава 2. Принципы анализа алгоритмов
51
Операций
Размер задачи 1 миллион
Размер задачи 1 миллиард
в секунду
N
NlgN
N2
N
NlgN
N2
106
секунд
секунд
недель
часов
часов
никогда
10»
мгновенно
мгновенно
часов
секунд
секунд
десятилетий
1012
мгновенно
мгновенно
секунд
мгновенно мгновенно
недель
Таблица 2.2 Значения часто встречающихся функций
В этой таблице сравниваются значения, принимаемые рядом функций, с которыми
нам придется часто сталкиваться при анализе алгоритмов. Очевидно, доминирующей
является квадратичная функция, особенно на больших значениях Л/, а на малых значе¬
ниях N различие между функциями оказываются не такими, как можно было бы ожи¬
дать. Например, Л/3/2 больше, чем N 1д2Л/, на очень больших значениях Л/, однако на
небольших N наблюдается обратная картина. Точное время выполнения алгоритма
может быть выражено в виде линейной комбинации этих функций. Мы можем легко
отделить быстрые алгоритмы от медленных из-за огромной разницы, например, между,
lg N и N или N и Л/2, тем не менее, различия между двумя быстрыми алгоритмами
может потребовать более тщательных исследований.
gN
л/дг
N
NlgN
N(lgN)2
N212
N2
3
3
10
33
110
32
100
7
10
100
664
4414
1000
10000
10
32
1000
9966
99317
31623
1000000
13
100
10000
132877
1765633
1000000
100000000
17
316
100000
1660964
27588016
31622777
10000000000
20
1000
1000000
19931569
397267426
1000000000
1000000000000
При анализе алгоритмов можно воспользоваться еще несколькими функциями. На¬
пример, алгоритм с N2 входными данными, имеющий время выполнения Аг3, лучше
рассматривать как алгоритм с зависимостью N3/2. Кроме того, алгоритмы, допускаю¬
щие разбиение на две подзадачи, имеют время выполнения, пропорциональное
N log2N. Из табл. 2.2 очевидно, что обе эти функции ближе к N logN, нежели к N2.
Логарифмическая функция играет особую роль при разработке и анализе алгорит¬
мов, поэтому ее стоит рассмотреть подробнее. Поскольку нам часто приходится да¬
вать оценку аналитическим результатам, в которых опущен постоянный множитель,
мы будем пользоваться записью "logTV", опуская основание. Изменение основания ло¬
гарифма с одной константы на другую меняет значение логарифма лишь на постоян¬
ный множитель, однако в определенных контекстах мы используем конкретные значе¬
ния оснований логарифмов. В математике настолько важным является понятие
натуральный логарифм (natural logarithm) с основанием е = 2.71828..., что широкое рас¬
пространение получило следующее сокращение: \oggN s InTV. В вычислительной техни¬
ке очень важен двоичный логарифм (binary logarithm) (т.е. по основанию 2), поэтому ис¬
пользуется сокращение \ogiN = \gN.
Иногда нам приходится вычислять логарифмы, особенно в отношении больших чи¬
сел. Например, lg lg 2256 = lg 256 = 8. Из этого примера должно быть понятно, что в
52 Часть 1. Анализ
большинстве практических случаев lg lgTV рассматривается как константа, поскольку
значение этого выражения достаточно мало даже для очень больших N.
Наименьшее целое число, большее lgjV, равно количеству бит, необходимых для
представления N в двоичном формате; точно так же наименьшее целое, большее
logio^V, это число цифр, необходимое для представления N в десятичном формате.
Оператор языка С
for (IgN = 0; N > 0; lgN++, N /= 2) ;
дает простой способ подсчета наименьшего целого, большего 1 gN. Похожий метод для
вычисления этой функции
for (IgN = 0, t = 1; t < N; lgN++, t += t) ;
В нем утверждается, что 2п < N < 2n+l, когда п - наименьшее целое, большее lgM
Кроме того, мы часто сталкиваемся с некоторыми специальными функциями и
различными формами математической записи, употребляемыми в из классическом
анализе и позволяющими получить компактные описания свойств программ. В табл.
2.3 сведены самые известные функции; мы кратко обсудим эти функции, а также не¬
которые наиболее важные их свойства в следующих параграфах.
Наши алгоритмы и их анализ часто оперируют дискретными величинами, поэтому
нам часто требуются специальные функции, переводящие действительные числа в це¬
лые, в частности:
LtJ: наибольшее целое, меньшее или равное х;
fYl: наименьшее целое, большее или равное х.
Например, оба значения |_7eJ и [е] равны 3, а Гlg(н-1)1 есть число бит в двоичном
представлении числа N. Другое важное применение этих функций возникает в том
случае, когда необходимо поделить множество, состоящее из N объектов пополам.
Этого нельзя сделать точно, если N есть нечетное число, поэтому, чтобы сохранить
точность, мы строим одно подмножество из lN/2] объектов, а второе, - из ГЛ/21
объектов. Если N четно, то размеры обоих подмножеств равны (VN/2\ = ГN/2]); если
же N нечетно, то их размеры отличаются на единицу ([.N/2\ + 1 = Гду2"|). В языке С
можно непосредственно подсчитать значения этих функций, если мы оперируем целы¬
ми числами (например, если N > 0, то N/2 равно [_Ay2j, а N-(N/2) равно Г N/l\), а
при операциях над числами с плавающей точкой можно воспользоваться функциями
floor и ceil из заголовочного файла math.h.
При анализе алгоритмов часто приходится сталкиваться с дискретизированной вер¬
сией функции натурального логарифма, получившей название гармонических чисел
(harmonic numbers). TV-тое гармоническое число определяется выражением
Натуральный логарифм lnTV есть значение площади под кривой \/х на отрезке
между 1 и N; гармоническое число HN есть площадь под ступенчатой функцией, ко¬
торую можно определить, вычисляя значения функции 1/х для целых чисел в диапазо¬
не от 1 до N. Зависимость показана на рис. 2.2. Формула
HN ~ In jV + у+ 1/(12N)
Глава 2. Принципы анализа алгоритмов
53
где у = 0.57721... (эта константа называется постоян¬
ной Эйлера (Euler's constant)), дает отличное приближе¬
ние для HN . В отличие от ГlgA^l и LlgA/J, для вычисле¬
ния HN лучше воспользоваться библиотечной
функцией log, а не подсчитывать его непосредствен¬
но из определения.
Таблица 2.3 Специальные функции и постоянные
В этой таблице показаны виды математической записи
функций и постоянных, которые часто появляются в
формулах, описывающих рабочие характеристики алго¬
ритмов. Формулы для приближенных значений можно
при необходимости расширить с целью достижения
большей точности (см. раздел ссылок).
РИСУНОК 2.2 ГАРМОНИЧЕСКИЕ ЧИСЛА
Гармонические числа представля¬
ют собой приближенные значения
элементов площади под кривой
у=1/х. Постоянная у показывает
разность между HN и
N
N = jdxlx.
1
Функция Название
Типовое значение
Приближение
ы
Гх1
lg N
fn
HN
N!
Ig(W)
функция округления снизу
функция округления сверху
двоичный логарифм
числа Фибоначчи
гармонические числа
факториал
L3.14J = 3
Гз.н! = 4
lg 1024 = 10
Fi о = 55
Я,о - 2.9
10! = 3628800
lg (100!) = 520
X
X
1.44 In N
In N + у
(■N/е)"
N lg N - 1.447V
e = 2.71828...
у = 0.57721...
Ф = О + л/5 ) / 2 = 1.61803...
In 2 = 0.693147...
lg* = 1 / In 2 = 1.44269.,
Последовательность чисел
О 1 1 2 3 5 8 13 21 34 55 89 144 233 377...,
определенная формулой
Fn = Fn-i + Fn-2 , где N > 2, a F0 = 0 и F{ = 1
известна как числа Фибоначчи (Fibonacci numbers). Эти числа обладают многими интерес¬
ными свойствами. Например, отношение двух следующих подряд элементов этой пос¬
ледовательности приближенно равно золотому сечению (golden ratio) ф = (1 + V5 ) / 2 ~
~ 1.61803... . Более подробный анализ показывает, что Fn равно значению выражения
Ф N / л/5 , округленному до ближайшего целого числа.
При анализе алгоритмов часто встречается также функция факториала (factorial) N\.
Как и экспоненциальная функция, факториал возникает при решении задач "в лоб" и
растет слишком быстро, чтобы такие решения представляли практический интерес.
Она также используется при анализе алгоритмов, поскольку представляет собой коли¬
чество способов перестановки N объектов. Для аппроксимации N\ используется фор¬
мула Стирлинга (Stirling's formula):
]gN! = jV IgN - AMg e + lg y[2nN
54 Часть 1. Анализ
Например, формула Стирлинга показывает, что число бит в двоичном представле¬
нии числа N1 равно примерно N\gN.
Большинство рассматриваемых в этой книге формул выражается посредством не¬
скольких функций, которые мы рассмотрели в этой главе. Однако при анализе алго¬
ритмов может встретиться множество других специальных функций. Например, клас¬
сическое биномиальное распределение (binomial distribution) и аппроксимация Пуассона
(Poisson approximation) играют важную роль при разработке и анализе некоторых фун¬
даментальных алгоритмов поиска, которые будут рассматриваться в главах 14 и 15. Функ¬
ции, не попавшие в приведенный выше список, обсуждаются по мере их появления.
Упражнения
!> 2.5. Для каких значений N выполняется неравенство 10 NIgA' > IN2!
>2.6. Для каких значений N выражение N3/2 имеет значение в пределах от
N(\gN)2/2 до 2A41gA02?
> 2.7. Для каких значений N выполняется неравенство 2 N HN - N < N IgN + 10А?
о 2.8. Для какого наименьшего значения N выполняется неравенство logiologioiV > 8?
о 2.9. Докажите, что LlgTVj + 1 — это число двоичных разрядов, необходимое для
представления числа N в двоичной форме.
2.10. Добавьте в табл. 2.1 колонки для N(\gN)2 и JV3/2.
2.11. Добавьте в табл. 2.1 строки для 107 и 108 инструкций в секунду.
2.12. Напишите на языке С функцию, которая подсчитывает Ядг, используя функ¬
цию log из стандартной библиотеки math.
2.13. Напишите эффективную функцию на языке С, подсчитывающую Гlg lg N\ Не
используйте библиотечную функцию.
2.14. Сколько цифр в десятичном представлении числа 1 миллион факториал?
2.15. Сколько бит в двоичном представлении числа lg(jV!) ?
2.16. Сколько бит в двоичном представлении
2.17. Приведите простое выражение для Llg/^J ?
о 2.18. Приведите наименьшие значения N, для которых Vhn\ = /, где 1 < / < 10.
2.19. Приведите наибольшее значение N, для которого можно решить задачу, тре¬
бующую выполнения f(N) инструкций, на машине с быстродействием 109 операций
в секунду для следующих функций f(N): N3/2, jV5/4, 2 N HN, N 1 gN lg lgjV и N2 \gN.
2.4 О-нотация
Математическая запись, позволяющая отбрасывать подробности при анализе алго¬
ритмов, называется О-нотацией (O-notation). Она определяется следующим образом.
Определение 2.1 Говорят, что функция g(N) является 0(f (N)), если существуют та¬
кие постоянные со и Nq, что g(N) < со f(N) для всех N >Nq.
О-нотация используется по трем основным причинам:
■ Чтобы ограничить ошибку, возникающую при отбрасывании малых слагаемых в
математических формулах.
Глава 2. Принципы анализа алгоритмов
55
■ Чтобы ограничить ошибку, возникающую, когда не учитываются те части про¬
граммы, которые дают малый вклад в анализируемую сумму.
■ Чтобы классифицировать алгоритмы по верхней границе их суммарного време¬
ни выполнения.
Третье назначение О-нотации рассматривается в разделе 2.7, а два других кратко
обсуждаются ниже.
Постоянные с0 и Nq, используемые в О-нотации, часто скрывают практически важ¬
ные подробности реализации. Очевидно, что выражение "алгоритм имеет время вы¬
полнения есть 0(f(N))" ничего не говорит о времени выполнения при N, меньшем Nq,
а за со, возможно, скрываются большие непроизводительные затраты ресурсов, необ¬
ходимые, чтобы избежать худшего случая с пагубными последствиями. Мы отдаем
предпочтение алгоритму, время выполнения которого составляет N2 наносекунд, а не
log# столетий, но мы не можем сделать такой выбор на основании О-нотации.
Часто результаты математического анализа не отличаются точностью, их скорее
можно считать приближенными в строгом техническом смысле: такой результат пред¬
ставляет собой выражение, содержащее последовательность убывающих слагаемых.
Подобно тому, как мы интересуемся, в основном, внутренним циклом программы, в
данном случае наше внимание больше всего привлекают главные члены (наибольшие по
величине слагаемые) математического выражения. О-нотация позволяет нам отслежи¬
вать главные члены и игнорировать меньшие слагаемые при манипуляции с прибли¬
женными математическими выражениями, а также получать компактные выражения,
дающие точные приближения для анализируемых количественных величин.
Некоторые из основных манипуляций, которыми мы пользуемся при работе с вы¬
ражениями, содержащими О-нотацию, являются предметом упражнений 2.20-2.25.
Многие из этих манипуляций интуитивно понятны, а склонные к математике читатели
могут с интересом выполнить упражнение 2.21, в котором требуется доказать обосно¬
ванность базовых операций из определения. По существу, из этих упражнений следу¬
ет, что можно раскрывать скобки в алгебраических выражениях с О-нотацией так,
как, если бы ее там не было, а затем отбрасывать все слагаемые, оставляя наиболь¬
ший. Например, если требуется раскрыть скобки в выражении
(N + 0(1))(ЛГ+ 0(log N) + 0(1)),
то мы получим шесть слагаемых
N2 + 0(N) + 0(N log N) + 0(log N) + CX.N) + 0(1).
Однако мы можем отбросить все слагаемые и оставить только
N2 + 0(Nlog N).
То есть, N2 является хорошей аппроксимацией этого выражения, когда N доста-
точно велико.
Эти действия интуитивно ясны, но О-нотация позволяет выразить их с математи¬
ческой точностью. Формула с одним О-слагаемым называется асимптотическим выра¬
жением (asymptotic expression).
В качестве более подходящего примера предположим (применив тот или иной ме¬
тод математического анализа), что некоторый конкретный алгоритм имеет внутренний
56 Часть 1. Анализ
цикл, который в среднем выполняется 2N HN раз, внешнюю процедуру, которая вы¬
полняется TV раз, и программу инициализации, которая выполняется один раз. Далее
предположим, что мы определили (после тщательного исследования реализации), что
каждая итерация внутреннего цикла выполняется за ао наносекунд, внешняя процеду¬
ра - за а\ наносекунд, а программа инициализации - за а2 наносекунд. Тогда среднее
время выполнения программы (в наносекундах) равно
2ао N HN + a\N + а2.
Поэтому для времени выполнения справедлива следующая формула:
2 aoNHN+ 0(N).
Более простая формула имеет важное значение, поскольку из нее следует, что при
больших TV нет необходимости искать значения величин а{ и а2 для аппроксимации
времени выполнения. В общем случае, точное математическое выражении для вычис¬
ления времени выполнения может содержать много других слагаемых, при этом не
все из них легко поддаются анализу. О-нотация предлагает нам способ получения при¬
ближенного ответа для больших TV без учета слагаемых такого рода.
Продолжая данный пример, можно воспользоваться О-нотацией, чтобы выразить
время выполнения с помощью известной функции, а именно, InTV. Посредством О-но-
тации приближенное выражение из табл. 2.5 можно записать как HN= InTV + 0(1). Та¬
ким образом, 2 a0N\nN + O(TV) - это асимптотическое выражение для общего време¬
ни выполнения рассматриваемого нами алгоритма. По нашей оценке, при больших ТУ
оно будет близко к легко вычисляемому выражению 2aoN\nN. Постоянный множи¬
тель зависит от времени, которое требуется для выполнения инструкций внутреннего
цикла.
Более того, нам не нужно знать значения ао, чтобы предсказать, что время выпол¬
нения для ввода размером 2TV будет вдвое больше, чем для ввода размером TV при
больших 7V, поскольку
Таким образом, асимптотическая формула позволяет нам делать точные прогнозы,
не вдаваясь в подробности реализации или анализа. Отметьте, что такой прогноз не
был бы возможным, если бы выполнялась О-аппроксимация только главного члена.
Предложенная схема рассуждений позволяет ограничиться только главным членом
при сравнении времен выполнения различных алгоритмов или при попытке дать им
оценку. Довольно часто мы имеем возможность подсчитать, сколько раз выполняются
те или иные операции фиксированной стоимости, и хотим для оценки результата ис¬
пользовать только главный член, полагая, что, при необходимости, всегда можно про¬
вести точный анализ, подобный выполненному выше.
Когда функция f(N) является асимптотически большой по сравнению с другой фун¬
кцией g(n) (т.е. g(N) //(TV) —> 0, когда TV -» оо), в этой книге мы иногда используем
термин (бесспорно, нетехнический) приблизительно равен f(N)f что означает
f(N) + 0(g(N)). То, что мы, возможно, теряем в математической точности, компенси¬
руется более глубоким пониманием проблемы, так как нас больше интересует произ¬
2а0 (2 TV) 1п(2ТУ) + 0(2 ТУ) = 21п(2ТУ) + 0(1) =.
Глава 2. Принципы анализа алгоритмов
57
водительность алгоритма, а не математические детали. В таких случаях мы можем быть
уверены в том, что при больших значениях N (если даже не при всех значениях) ис¬
следуемая количественная величина будет близка по величине к f(N). Например, даже
если мы знаем, что числовое значение равно N(N — \)/2, мы можем считать его рав¬
ным N2/2. При таком способе выражения результат воспринимается быстрее, чем в
более подробном и точном представлении, хотя он, возможно, отличается от точного
значения, скажем, всего лишь на 0.1 процента для N = 1000. Потеря точности в данном
случае намного меньше, чем при более привычном использовании 0(f(N)). Наша цель
состоит в том, чтобы быть одновременно и точными, и краткими при описании про¬
изводительности алгоритмов.
Мы иногда рассуждаем в подобном ключе и говорим, что время выполнения алго¬
ритма пропорционально f(N), когда можно дока¬
зать, что оно равно cf(N) + g(N), где функция
g(N) асимптотически мала по сравнению с функ¬
цией f(N). Когда такая зависимость имеет место,
то мы можем прогнозировать время выполнения,
скажем, для 2N, если оно известно для N, как в
примере, который обсуждался выше. На рис. 2.3
приводятся значения коэффициентов, которыми
мы можем воспользоваться для подобных прогно¬
зов поведения функций, с которыми мы часто
сталкиваемся во время анализа алгоритмов.
В сочетании с эмпирическим исследованием (см.
раздел 2.1) такой подход делает излишним опре¬
деление постоянных величин, зависящих от реа¬
лизации. Или наоборот, мы часто можем выдви¬
гать ту или иную гипотезу о функциональной
зависимости времени выполнения конкретной
программы, изучив, как меняется время ее вы¬
полнения при увеличении N в два раза.
Различия О-границ, которые пропорциональны
(is proportional to) и приблизительно равны (about)
друг другу, показаны на рис. 2.3 и 2.4. О-нотация
используется, прежде всего, для исследования
фундаментального асимптотического поведения
алгоритма; мы используем понятие пропорциональ¬
но, когда хотим дать прогноз производительности
алгоритма методом экстраполяции на основе эм¬
пирических исследований, а приблизительно равна,
когда намерены сравнении производительности
разных алгоритмов или при предсказании абсо¬
лютной производительности.
РИСУНОК 2.3 ОГРАНИЧЕНИЕ ФУНКЦИИ
С ПОМОЩЬЮ О-АППРОКСИМАЦИИ
На этой схематической диаграмме
осциллирующая кривая представляет
собой функцию g(N), которую мы
пытаемся аппроксимировать; гладкая
черная кривая представляет собой
другую функцию, f(N), которую мы
пытаемся использовать для аппрокси¬
мации, а гладкая серая кривая
является функцией cf(N) с некоторой
неопределенной постоянной с.
Вертикальная прямая задает значение
N0, указывающее, что аппроксимация
имеет место для N > Nq. Когда мы
говорим, что g(N) = 0(f(N)), мы всего
лишь ожидаем, что значение функции
g(N) находится ниже некоторой
кривой, имеющей фррму функции f(N),
и правее некоторой вертикальной
прямой. В противном случае поведение
функции f(N) может оказаться
непредсказуемым (например. она не
обязательно должна быть непре¬
рывной).
5 8 Часть 1. Анализ
Упражнения
> 2.20. Докажите, что 0(1) - то же самое, что 0(2).
2.21. Докажите, что в выражениях с О-нотацией
можно производить любое из перечисленных пре¬
образований:
f(N) -> 0(f(N)),
cO(f(N)) -» CKf(N)),
0{cf(N)) -> (КAN)),
f(N)-m = mm ->/w = m + mm,
тюхх&ю) -* mN)g(N)),
0(f(N)) + OWN)) -> OWN))
если f(N) = 0(g(N)).
о 2.22. Покажите, что (N + 1 )(#* + 0(1)) =
N InN+ 0(N).
2.23. Покажите, что N lnjV = 0(N3/2).
• 2.24. Покажите, что NM = 0(aN) для любого M и
любого постоянного а > 1.
• 2.25. Докажите, что
N
N+0(1)
РИСУНОК 2.4
АППРОКСИМАЦИЯ ФУНКЦИЙ
Когда говорят, что функция g(N)
пропорциональна функции f(N)
(верхний график), то подразумева¬
ют, что она растет как f(N), но,
возможно, смещена относительно
последней на неизвестную посто¬
янную. Если задано некоторое
значение g(N), можно вычислить
значение этой функции при
больших значениях N. Когда
говорят, что g(N) приблизительно
равна f(N) (нижний график), то
при этом подразумевают, что
функцию/можно использовать для
вычисления более точной оценки
значений функции g.
2.26. Предположим, что Нк = N. Найдите прибли¬
женную формулу, которая выражает к как функ¬
цию от N.
• 2.27. Предположим, что lg(fc!) = N. Найдите при¬
ближенную формулу, которая выражает к как
функцию N.
о 2.28. Известно, что время выполнения одного ал¬
горитма равно 0(N\ogN), а время выполнения
другого алгоритма равно O(N^). Что можно ска¬
зать об относительной производительности этих алгоритмов?
о 2.29. Известно, что время выполнения одного алгоритма всегда приблизительно
равно TVlogTV, а другого - 0(N3). Что можно сказать об относительной произво¬
дительности этих алгоритмов?
о 2.30. Известно, что время выполнения одного алгоритма всегда приблизительно
равно TVlogTV, а другого - всегда приблизительно равно N3. Что можно сказать об
относительной производительности этих алгоритмов?
о 2.31. Известно, что время выполнения одного алгоритма всегда пропорционально
N logN, а другого - всегда пропорционально N3. Что можно сказать об относи¬
тельной производительности этих алгоритмов?
о 2.32. Выведите значения множителей, приведенных на рис. 2.5: для каждой функ¬
ции f(N), показанной слева, найдите асимптотическую формулу для f(2N)/(N).
Глава 2. Принципы анализа алгоритмов
59
2.5 Простейшие рекурсии
Как будет показано далее в этой книге, мно¬
гие алгоритмы основаны на принципе рекурсив¬
ного разбиения большой задачи на меньшие,
когда решения подзадач используются для реше¬
ния исходной задачи. Эта тема подробно обсуж¬
дается в главе 5, главным образом, с практичес¬
кой точки зрения, где основное внимание
уделяется различным реализациям и приложени¬
ям. Кроме того, в разделе 2.6 будет рассмотрен
подробный пример. В этом разделе мы ознако¬
мимся с базовыми методами анализа таких алго¬
ритмов и получим решения нескольких стандар¬
тных формул, с которыми нам приходится
сталкиваться при анализе многих алгоритмов,
которые предстоит изучить. Понимание матема¬
тических свойств формул, приводимых в этом
разделе, дает возможность получить представле¬
ние о рабочих характеристиках алгоритмов, изу¬
чаемых в этой книге.
Формула 2.1 В рекурсивной программе, в
которой при каждой итерации цикла количе¬
ство вводов уменьшается на единицу, возни¬
кает следующее рекуррентное соотношение:
Cn = CN-1 + N, где N > 2 и Q = 1.
1
Коэффициент отсутствует
lg N
Небольшой рост
N
Рост в два раза
N\gN
Рост немного больше,
чем в два раза
Nv2
Множитель 2л/2
N2
Множитель 4
Множитель 8
2n
В квадрате
РИСУНОК 2.5 ВЛИЯНИЕ УДВОЕНИЯ РАЗМЕРОВ
ЗАДАЧИ НА ВРЕМЯ ВЫПОЛНЕНИЯ
Прогнозирование влияния удвоения
размеров задачи на время выполнения
является простой задачей, когда время
выполнения пропорционально одной из
простых функций, подобной представ¬
ленным в данной таблице. В теории мы
можем опираться на эти результаты,
только когда N достаточно велико, но
данный метод на удивление эффекти¬
вен. И наоборот, быстрый метод
определения функциональной зависимос¬
ти роста времени выполнения програм¬
мы заключается в запуске программы,
удвоении количество вводов для макси¬
мально возможного N с последующим
выбором соответствующей функции из
этой таблицы.
Решение: CN приблизительно равна N2/2. Для
решения рекурсии ее можно раскрыть, применяя саму к себе следующим образом:
Cn = Cn-i + N
= Cn- 2 + (N- 1) + N
= Cn- з + (N-2) + (N- 1) + N
Продолжая в том же духе, можно получить:
CN= Сх + 2 + ... + (N- 2) + (N- 1) + N
= 1 + 2 + ... + (N-2) + (N- 1) + N
N(N+1)
2
Подсчет суммы 1 + 2 + ... + (N - 2) + (N — 1) + 7V выполняется элементарно:
прибавим к сумме ее же, но взятую в обратном порядке. Полученная сумма есть
удвоенный искомый результат, содержит N слагаемых, каждое из которых равно
N+ 1.
60 Часть 1. Анализ
Этот простой пример иллюстрирует базовую схему, которую мы используем в этом
разделе, когда мы рассматриваем ряд формул, основанных на принципе рекурсивной
декомпозиции в алгоритме, которая непосредственно отражается на его анализе. На¬
пример, время выполнения таких алгоритмов определяется размерами и числом подза¬
дач, а также временем, необходимым для разбиения исходной задачи на подзадачи.
Математически зависимость времени выполнения алгоритма при вводе объема N от
времени его выполнения при меньших объемах вводов легко задается формулами,
именуемыми рекуррентными соотношениями (recurrence relations). Такие формулы точно
описывают производительность соответствующих алгоритмов: для вычисления времени
выполнения достаточно решить эти рекурсии. Более строгие рассуждения, касающие¬
ся конкретных алгоритмов, мы будем приводить, когда перейдем к изучению этих ал¬
горитмов; здесь же мы рассмотрим сами формулы.
Формула 2.2 В рекурсивной программе на каждом шаге количество вводов умень¬
шается вдвое, отсюда возникает следующее рекуррентное соотношение:
Cn = CNj2 + 1, где N > 2 и Q = 1.
Решение: Cn приблизительно равна 1 gN. В том виде, в
каком оно записано, это уравнение не имеет смысла,
исключение представляют собой случай, когда N четно
или же когда под N/2 предполагается целочисленное де¬
ление. Теперь предположим, что N = 2п, в этом случае
рекурсия всегда определена правильно. (Заметьте, что
п = lgN.) Тогда рекурсию раскрыть еще проще, чем в
предыдущем случае:
= С^я-1 +1
= С~>п-2 +1 + 1
— с2-з + 3
N
(N) 2
LlgAd +
1
1
1
2
10
2
3
11
2
4
100
3
5
101
3
6
110
3
7
111
3
8
1000
4
9
1001
4
10
1010
4
11
1011
4
12
1100
4
13
1101
4
14
1110
4
15
1111
4
= С2о + п
= п + \.
Точное решение для любого N зависит от интерпретации
N/2. Если N/2 представляет собой LАУ2J, тогда существу¬
ет очень простое решение: CN — это количество бит в
двоичном представлении числа N, т.е. по определению
LlgNj + 1. Этот вывод немедленно следует из того фак¬
та, что операция отбрасывания крайнего правого бита в
двоичном представлении любого числа N > 0 превраща¬
ет его в LjV/2J (см. рис. 2.6).
Формула 2.3 В рекурсивной программе, которая умень¬
шает ввод вдвое, но которая, возможно, должна прове¬
рить каждый элемент, возникает следующее рекуррент¬
ное соотношение:
C.V = С n/2 + N, где N > 2 и С\ = 0.
РИСУНОК 2.6 ЦЕЛОЧИСЛЕННЫЕ
ФУНКЦИИ И ДВОИЧНЫЕ
ПРЕДСТАВЛЕНИЯ.
Рассматривая двоичное
представление числа N
(в центре), получим \_N/2\
путем отбрасывания
крайнего правого бита. То
есть, число бит в двоичном
представлении числа N на
единицу больше, чем в
представлении числа 1_ЛУ2_|.
Поэтому LlgWj + 1, т. е.
число бит в двоичном
представлении числа N
есть решение формулы 2.2 в
случае, когда N/2 интерпре¬
тируется как VN/2\.
Глава 2. Принципы анализа алгоритмов
61
Решение: CN приблизительно равна 2N. Рекурсия раскрывается в сумму N + N/2 +
+ N/4 + N/S + ... (Как и формуле 2.2, рекуррентное соотношение определено точ¬
но только в том случае, когда N является степенью числа 2). Если данная последо¬
вательность бесконечна, то сумма простой геометрической прогрессии равна 2N.
Поскольку мы используем целочисленное деление и останавливаемся на 1, данное:
значение является приближением точного ответа. Точное решение зависит от
свойств двоичного представления числа N.
Формула 2.4 В рекурсивной программе, которая должна выполнить линейный
проход по вводу до, в течение или после разбиения его на две половины, возника¬
ет следующее рекуррентное соотношение:
Сдг = 2Ст + N, где N> 2 и С\ = 0.
Решение: CN приблизительно равна NlgN. На это решение ссылаются намного
чаще, чем на остальные из приводимых здесь рекурсий, поскольку данная рекур¬
сия используется на всем семействе алгоритмов "разделяй и властвуй".
Сгп = 2С2п-\ + 2"
Со Л С”) л— 1 Л
—2- = -Ц- + 1
2« 2
^2п~2 1 1
= =- + 1 + 1
2*
= п.
Мы находим решение практически тем же способом, что и для формулы 2.2, но
при этом на втором шаге выполняем дополнительную операцию — деление обеих
частей равенства на 2я, что позволяет раскрыть рекурсию.
Формула 2.5 В рекурсивной программе, которая разбивает ввод пополам, а затем
производит одно и то же число других операций (см. главу 5) возникает следую¬
щая рекурсия.
CN = 2Ст + 1, где N > 2 и С\ = 1.
Решение: Сн приблизительно равна 2N. Это решение можно получить так же, как и
решение для формулы 2.4.
С помощью приведенных методов можно получить решение для различных вариан¬
тов подобных формул, с другими начальными условиями или с небольшими отличиями
в добавочном члене, но при этом необходимо помнить, что некоторые рекурсии, ка¬
жущиеся похожими, могут иметь гораздо более сложные решения. Существует различ¬
ные современные общие методы математически строгого решения таких уравнений
(см. раздел ссылок). С несколькими сложными рекуррентными соотношениями мы бу¬
дем иметь дело в последующих главах, где и будем искать их решения по мере воз¬
никновения таких соотношений.
62 Часть 1. Анализ
Упражнения
> 2.33. Составьте таблицу значений CN, заданных формулой 2.2, для 1 < N < 32, счи¬
тая, что TV/2 означает [.N/21
> 2.34. Выполните упражнение 2.33, интерпретируя N/2 как ГN/21.
> 2.35. Выполните упражнение 2.34 для формулы 2.3.
о 2.36. Предположим, что fN пропорциональна постоянной величине и
Сдг = Сду2 + /м где TV > t и 0 < CN < с при TV < /,
где с и t — постоянные. Покажите, что CN пропорционально lgTV.
• 2.37. Сформулируйте и докажите обобщенные версии формул 2.3—2.5, аналогичные
обобщенной версии формулы 2.2 в упражнении 2.36.
2.38. Составьте таблицу значений CN в формуле 2.4 при 1 < TV < 32 для трех следу¬
ющих случаев: (1) TV/2 интерпретируется как LTV/2J, (2) N/2 интерпретируется как
ГА/21 (3) 2Ст интерпретируется как С[л/2] + C\n/i\
2.39. Решите формулу 2.4 для случая, когда TV/2 интерпретируется как LTV/2J, ис¬
пользуя соответствие двоичному представлению числа TV, как это было сделано в
доказательстве формулы 2.2. Указание: Рассмотрите все числа, меньшие TV.
2.40. Решите рекурсию
Cn = Cn/2 + N2 при TV > 2 и Ci = 0,
когда TV является степенью числа 2.
2.41. Решите рекурсию
Cn = Сдуа + 1 при TV > 2 и С\ = 0,
когда TV является степенью числа а.
о 2.42. Решите рекурсию
CN = аСдг/2 при TV > 2 и Ci = 1,
когда TV является степенью числа 2.
о 2.43. Решите рекурсию
Сдг = (Сл//2)2 при TV > 2 и Ci = 1,
когда TV является степенью числа 2.
• 2.44 Решите рекурсию
CN =
2 + - 1
Cn/2 при TV > 2 и Ci = 1,
igTV
когда TV является степенью числа 2.
• 2.45. Рассмотрите семейство рекурсий, подобных представленным формулой 2.1,
где TV/2 может означать либо LTV/2J, либо ГTV/21, при этом единственное требование
заключается в том, чтобы рекурсия имеет место при TV > с0 и CN = 0(1) при
TV < с0. Докажите, что решением всех таких рекурсий является формула
lgtf+ 0(1).
•• 2.46. Сформулируйте обобщенные рекуррентные соотношения для формул 2.2-2.5
и найдите их решения, аналогичные полученным в упражнении 2.45.
Глава 2, Принципы анализа алгоритмов
63
2.6 Примеры анализа алгоритмов
Вооружившись инструментами, о которых шла речь в трех предыдущих разделах,
мы проведем анализ последовательного поиска (sequential search) и бинарного поиска
(binary search) - двух основных алгоритмов с целью определить, входит ли та или иная
последовательность объектов во множество ранее сохраненных объектов. Мы ставим
перед собой цель показать методы сравнения алгоритмов, а не подробное описание
самих алгоритмов. Для простоты предположим, что все рассматриваемые объекты яв¬
ляются целыми числами. Приложения более общего характера рассматриваются в гла¬
вах 12-16. Простые версии алгоритмов, которые мы здесь изучаем, не только демон¬
стрируют многие аспекты задачи разработки и анализа алгоритмов, но и имеют
непосредственное применение.
Например, представим себе компанию, обрабатывающую кредитные карточки и
имеющую N кредитных рисков, иначе говоря, украденных кредитных карточек, кото¬
рая намерена проверить, не участвует ли в какой-либо из М транзакций хотя бы один
из этих N "плохих" номеров. Чтобы не быть голословными, будем считать значение N
достаточно большим (скажем, порядка 103-106), а значение М - очень большим (по¬
рядка 106— 109). Цель анализа заключается в том, чтобы дать приблизительную оценку
времени выполнения алгоритмов, когда параметры принимают значения из указанных
выше диапазонов.
Программа 2.1 реализует простое решение проблемы поиска. Она оформлена в
виде функции на языке С, обрабатывающей массив (см. главу 3), с целью обеспечения
лучшей совместимости с другими программами решения этой задачи, которые мы бу¬
дем изучать в части 4. Однако не обязательно вдаваться в детали представления про¬
граммы для понимания того, как работает алгоритм: мы сохраняем все объекты в мас¬
сиве, затем при совершении каждой транзакции мы последовательно просматриваем
массив от начала до конца, проверяя, содержится ли в нем число, которое мы ищем.
Приступая к анализу алгоритма, прежде всего, отметим, что его время выполнения
зависит от того, находится ли требуемый объект в массиве. То, что поиск закончился
неудачно, мы узнаем, когда проверим N объектов, в то же время, успешный поиск
может завершиться на первом, втором или любом другом объекте.
Программа 2.1 Последовательный поиск
Данная функция проверяет, находится ли число v среди элементов массива
а [1], а [1+1], а [г] путем последовательного сравнения с каждым элементом,
начиная с начала. Если по достижении последнего элемента нужное значение не най¬
дено, то функция возвращает значение -1. В противном случае она возвращает индекс
элемента массива, содержащего искомое число.
int search (int а[], int v, int 1, int r)
{ int i ;
for (i = 1; i <= r; i++)
if (v *= a[i]) return i;
return -1;
}
Поэтому время выполнения зависит от данных. Если бы каждый раз поиск оста¬
навливался на числах, оказавшихся в первой позиции, то алгоритм был бы быстрым;
если бы он продолжался до чисел, находящихся в последней позиции, то алгоритм ра¬
64 Часть 1. Анализ
ботал бы медленно. В разделе 2.7 мы обсудим различие между возможностью гаранти¬
ровать производительность и прогнозировать производительность. В данном случае,
лучшее из того, что мы можем гарантировать, - это то, что будет исследовано не бо¬
лее N чисел.
Однако чтобы сделать какой-либо прогноз, необходимо выдвинуть то или иное
предположение относительно данных. В рассматриваемом случае предположим, что
все числа выбраны случайным образом. Из этого предположения следует, например,
что каждое число в таблице может с одинаковой вероятностью оказаться объектом по¬
иска. После некоторых размышлений мы приходим к выводу, что именно это свой¬
ство поиска является наиболее важным, поэтому маловероятно, что поиск на множе¬
стве случайно выбранных будет успешным (см. упражнение 2.48). В некоторых
приложениях количество транзакций с успешным поиском может быть высоким, в
других приложениях — низким. Чтобы не отягощать модель свойствами приложения,
мы разделим задачу на два случая (успешный и неуспешный поиск) и проанализируем
их независимо друг от друга. Рассматриваемый пример показывает, что важнейшим
моментом эффективного анализа является разработка обоснованной модели приложения.
Наши аналитические результаты будут зависеть от доли успешно закончившихся поисков,
более того, они обеспечат нас информацией, которая может нам понадобиться при вы¬
боре различных алгоритмов для разных приложений на основании этого параметра.
Свойство 2.1 Последовательный поиск исследует N чисел при каждом неудачном поиске
и в среднем примерно N/2 чисел при каждом успешном поиске.
Если каждое число в таблице с равной вероятностью может оказаться объектом
поиска, то (1+ 2 + ... + N) / N = (N + 1) / 2 есть средняя цена поиска. ■
Из свойства 2.1 следует, что время выполнения программы 2.1 пропорционально N
при условии, что средняя стоимость операции сравнения двух чисел постоянна. Отсю¬
да, например, следует ожидать, что если удвоить количество объектов, то и время, не¬
обходимое для поиска, также удвоится.
Последовательный поиск с неудачным исходом можно ускорить, если упорядочить
числа в таблице. Сортировка чисел в таблице является предметом рассмотрения глав
6-11. Несколько алгоритмов, которые мы рассмотрим ниже, выполняют эту задачу за
время, пропорциональное N logTV, которое незначительно по сравнению со стоимос¬
тью поиска при очень больших М. В упорядоченной таблице можно прервать поиск
сразу по достижении числа, большего, чем искомое. Такое изменение уменьшает сто¬
имость последовательного поиска примерно до N/2 чисел, которые необходимо в среднем
проверить с неудачным исходом, то есть, она равна стоимости успешного поиска.
Свойство 2.2 Алгоритм последовательного поиска в упорядоченной таблице проверяет
N чисел для каждого поиска в худшем случае и примерно N/2 чисел в среднем.
В этом случае опять-таки необходимо определить модель поиска с неудачным ис¬
ходом. Этот результат следует из предположения, что поиск может с равной веро¬
ятностью закончится на любом из N + 1 интервалов, задаваемых N числами в таб¬
лице, а это непосредственно приводит к выражению
(1 + 2 + ... + N + N) / N = (N + 3) / 2.
Стоимость поиска с неудачным исходом, который заканчивается до или после
N-ой записи в таблице, та же: а именно, N. ■
Глава 2. Принципы анализа алгоритмов
65
Другой способ выразить результат свойства 2.2 - сказать, что время выполнения
последовательного поиска пропорционально М N для М транзакций в среднем и худ¬
шем случае. Если мы удвоим количество транзакций или количество объектов в табли¬
це, то время выполнения удвоится; если же мы удвоим обе величины одновременно,
то время выполнения вырастет в 4 раза. Этот результат свидетельствует о том, что
данный метод не подходит для очень больших таблиц. Если для проверки одного числа
требуется с микросекунд, а М = 109 и N = 106, тогда время выполнения поиска для
всех транзакций будет, по крайней мере, (с / 2) 109 секунд, или, согласно данным рис.
2.1, около 16с лет, что совершенно неприемлемо.
Программа 2.2 Бинарный поиск
В данной программе используются те же функциональные средства, что и программе
2.1, однако гораздо ее эффективность гораздо выше.
int search (in t a[], int v, int 1, int r)
{
while (r >= 1)
{ int m = (1+r)/2;
if (v == a[m]) return m;
if (v < a[m]) r = m-1; else 1 = m+1;
}
return -1;
>
Программа 2.2 представляет собой классическое решение проблемы поиска мето¬
дом гораздо более эффективным, чем последовательный поиск. Он основан на идее,
что если числа в таблице упорядочены, то мы можем отбросить половину из них пос¬
ле сравнения искомого значения с числом из середины таблицы. Если они равны, зна¬
чит, поиск закончился успешно, если искомое число меньше, то мы применим тот же
метод к левой части таблицы, если больше - то к правой части. На рис. 2.7 представ¬
лен пример применения этого метода к демонстрационному множеству чисел.
Свойство 2.3 Бинарный поиск никогда не проверяет более нем LlgjVj + 1 чисел.
Доказательство данного свойства служит иллюстрацией применение рекуррентных
соотношений при анализе алгоритмов. Пусть TN есть количество сравнений, необ¬
ходимое для проведения бинарного поиска в худшем случае, тогда из того, что ал¬
горитм сводит поиск в таблице размера N к поиску в два раза меньшей таблице,
непосредственно следует, что
Tn ^ Tin/2\ + 1, при N > 2 и Т\ = 1.
При поиске в таблице размером N мы проверяем число в средине исходной табли¬
цы, затем производим поиск в таблице размером не более IN/2_|. Фактическая сто¬
имость может быть меньше этого значения, так как первое же сравнение может
закончиться успешно, либо таблица имеет размер [.N/2] - 1 (если N четно). Так
же, как при решении формулы 2.2, легко доказать, что TN < п + 1 при TV = 2я, а
затем получить общий результат методом индукции. ■
Свойство 2.3 позволяет решать крупные задачи поиска на множестве, содержащем
до 1 миллиона чисел, за счет всего лишь 20 сравнений на транзакцию, а это обычно
требует меньшее времени, чем нужно большинству современных компьютеров для чте-
66 Часть 1. Анализ
ния или записи одного числа. Проблема поиска на¬
столько важна, что было разработано несколько ме¬
тодов, обладающих еще более высоким быстродей¬
ствием, чем описанный выше, как будет показано в
главах 12-16.
Обратите, что свойства 2.1 и 2.2 выражены через
операции, которые чаще других выполняются над
данными. Как отмечено в комментарии к свойству
2.1, ожидается, что каждая операция должна выпол¬
няться за постоянное время, в этом случае можно
утверждать, что время выполнения бинарного поис¬
ка пропорционально lg TV, в отличие от А^для после¬
довательного поиска. При удвоении N время
бинарного поиска изменяется, но не в два раза, как
это имеет место для последовательного поиска. С
ростом N различие между двумя методами становит¬
ся все более очевидным.
Можно проверить аналитическое доказательство
свойств 2.1 и 2.2, для чего придется написать соот¬
ветствующую программу и выполнить тестирование
алгоритма. Например, в таблице 2.4 показаны значе¬
ния времени выполнения бинарного и последова¬
тельного методов поиска для М поисков в таблице
размером N (включая в случае бинарного поиска
стоимость сортировки таблицы) при различных зна¬
чениях М и N. Здесь мы не будем подробно рас¬
сматривать реализацию программы с целью прове¬
дения экспериментов, поскольку подробный анализ
аналогичных задач мы проведем в главах 6 и 11, а
также еще и потому, что использование библиотеч¬
ных и внешних функций и другие детали создания
программ из компонент, включая и функцию sort,
изучаются в главе 3. Здесь мы просто отметим, что
проведение эмпирического тестирования - это
неотъемлемая часть оценки эффективности
алгоритма.
Таблица 2.4 подтверждает наш вывод о том, что
1488
1488
1578
1578
1973
1973
3665
3665
4426
4426
4548
4548
5435
5435
5435
5435 5435
5446
5446
5446
5446
6333
6333
6333
6385
6385
6385
6455
6455
6455
6504
6937
6965
7104
7230
8340
8958
9208
9364
9550
9645
9686
РИСУНОК 2.7 БИНАРНЫЙ ПОИСК
Чтобы проверить, содержится ли
число 5025 в таблице чисел,
приведенной в левом столбце, мы
сначала сравниваем его с 6504, из
чего следует, что дальше необхо¬
димо рассматривать первую
половину массива. Затем произво¬
дится сравнение с числом 4548
(середина первой половины), после
чего исследуется вторая половина
первой половины. Мы продолжаем
этот процесс, работая с подмас-
сивом, в котором может содер¬
жаться искомое число, если оно
содержится в таблице. В конеч¬
ном итоге мы получаем подмассив
с одним элементом, не равным
5025, из чего следует, что 5025
в таблице не содержится.
функциональный рост времени выполнения позво¬
ляет прогнозировать производительность алгоритмов решения крупных задач на осно¬
ве эмпирических исследований работы алгоритма на малых задачах. Сочетание мате¬
матического анализа и эмпирических исследований убедительно показывает, что
предпочтительным алгоритмом, безусловно, является бинарный поиск, по крайней
мере, на данный момент.
Глава 2. Принципы анализа алгоритмов
67
Таблица 2.4 Эмпирическое изучение последовательного и бинарного поиска
Приведенные ниже значения времени выполнения алгоритмов поиска подтверждают
полученные нами аналитические результаты для М поисков в таблице из N объектов,
согласно которым время последовательного поиска пропорционально MN, а время
бинарного поиска - М lg N. При удвоении N время последовательного поиска также
удваивается, а время бинарного поиска почти не изменяется. Последовательный по¬
иск все больше теряет привлекательность для очень больших М по мере возрастания
N, а бинарный поиск является достаточно быстрым даже в случае огромных таблиц.
N
М =
S
1000
В
м =
S
10000
В
М =
S
ЮОООС
В
125
1
1
13
2
130
20
250
3
0
25
2
251
22
500
5
о
49
3
492
23
1250
13
0
128
3
1276
25
2500
26
1
267
3
28
5000
53
0
533
3
30
12500
134
1
1337
3
33
25000
268
1
3
35
50000
537
0
4
39
100000
1269
1
5
47
Сокращения:
S - последовательный поиск (программа 2.1)
В - бинарный поиск (программа 2.2)
Данный пример является прототипом общего подхода к сравнению алгоритмов.
Мы используем математический анализ для оценки частоты, с какой алгоритм выпол¬
няет критические абстрактные операции, затем на основании полученных результатов
мы выводим функциональную форму времени выполнения, которая позволяет прове¬
рить и расширить эмпирические данные. По мере нахождения алгоритмических реше¬
ний вычислительных задач, детализация которых все больше возрастает, и по мере
применения все более сложных методов математического анализа с целью изучения их
рабочих характеристик, мы все чаще будем обращаться за результатами математичес¬
ких исследований к специальной литературе, чтобы в данной книге основное внима¬
ние уделять алгоритмам. Здесь мы не можем себе позволить проводить тщательное ма¬
тематическое и эмпирическое исследование всех алгоритмов, с которыми нам
Приходится иметь дело, главной нашей задачей является определение наиболее важных
рабочих характеристик алгоритмов. Учитывая это, мы, в принципе, всегда можем раз¬
работать научную основу, необходимую для неформального выбора алгоритмов для
важных приложений.
68 Часть 1. Анализ
Упражнения
>2.47. Найдите среднее число сравнений, используемых программой 2.1, если ос N
поисков прошли успешно, a 0 < а < 1.
•• 2.48. Оцените вероятность того, что хотя бы одно из М случайных десятизначных
чисел будет содержаться в наборе из N чисел, при М = 10, 100, 1000 и N = 103,
104, 105, 106.
2.49. Напишите программу-драйвер, которая генерирует М случайных целых чисел
и помещает их в массив, затем подсчитывает количество TV случайных целых чисел,
которые совпадают с одним из чисел массива, используя последовательный поиск.
Выполните прогон программы при М = 10, 100, 1000 и N = 10, 100, 1000.
• 2.50. Сформулируйте и докажите свойство, аналогичное свойству 2.3, для бинарно¬
го поиска.
2.7 Гарантии, предсказания и ограничения
Время выполнения большинства алгоритмов зависит от входных данных. Обычно
нашей целью при анализе алгоритмов является устранение тем или иным способом
этой зависимости: мы хотим иметь возможность сказать о производительности наших
программ нечто такое, что как можно меньше зависит от входных данных, так как в
общем случае неизвестно, какими будут входные данные при каждом новом запуске
программы. Примеры, приводимые в разделе 2.6, служат иллюстрацией двух основных
подходов, которые применяются в таких случаях: анализ производительности в худшем
случае и анализ производительности в среднем случае.
Изучение производительности алгоритмов в худшем случае (worst-case) достаточно
привлекательно, поскольку оно позволяет давать гарантию конкретного времени вы¬
полнения программ. Мы говорим, что частота исполнения конкретных абстрактных
операций меньше, чем значения некоторой функция от числа вводов, независимо от
того, какими являются входные значения. Свойство 2.3 представляет собой пример та¬
кой гарантии для бинарного поиска, так же как и свойство 1.3 - для взвешенного
быстрого объединения. Ес^и выбраны низкие гарантии, как в случае бинарного поис¬
ка, то это благоприятная ситуация, ибо нам удалось устранить те моменты, когда про¬
грамма может работать медленно. Поэтому программы с хорошими рабочими характе¬
ристиками в худшем случае и являются основной целью разработки алгоритмов.
Однако при анализе производительности в худшем случае возникают и некоторые
трудности. Для того или иного алгоритма различие между временем, необходимым для
решения задачи для худших входных данных, и временем для его прогона на данных,
которые обычно встречаются на практике, может оказаться весьма существенным. На¬
пример, для выполнения алгоритма быстрого объединения в худшем случае требуется
время, пропорциональное N, и пропорциональное лишь log# для обычных данных.
Что еще важнее, часто не удается доказать, что существуют входные данные, для ко¬
торых время выполнения алгоритма достигает той или иной границы; можно лишь до¬
казать, что время выполнения будет гарантировано ниже этого предела. Более того,
для некоторых задач алгоритмы с хорошими характеристиками для худшего случая,
оказываются сложнее, чем другие алгоритмы решения этих задач. Иногда мы по соб¬
ственной воле попадаем в ситуацию, когда алгоритм с хорошими характеристиками
Глава 2. Принципы анализа алгоритмов
69
для худшего случая при работе с данными, которые встречаются на практике, оказы¬
вается медленнее, чем более простые алгоритмы, или усилия, затрачиваемые на повы¬
шение производительности в худшем случае, не обеспечивают такого повышения быс¬
тродействия, которое оправдывало бы эти усилия. Для многих приложений другие
свойства алгоритма, в частности, переносимость или надежность, являются более важ¬
ными, чем гарантии, предоставляемые для худшего случая. Например, как было пока¬
зано в главе 1, взвешенное быстрое объединение со сжатием пути обеспечивает дока¬
зуемо лучшие гарантии производительности, чем взвешенное быстрое объединение, но
на типовых данных, встречающихся на практике, оба эти алгоритма имеют практичес¬
ки одинаковое время выполнения.
Изучение производительности алгоритмов в среднем случае (average-case) обладает
тем достоинством, что оно позволяет нам строить прогнозы времени выполнения про¬
грамм. В простейшем случае можно точно характеризовать входные данные алгорит¬
ма, например, алгоритм сортировки может выполняться над массивом из N случайных
целых чисел или геометрический алгоритм может обрабатывать набор из N случайных
точек на плоскости с координатами между 0 и 1. Затем мы подсчитываем, сколько
раз в среднем выполняется каждая инструкция, и вычисляем среднее время выполне¬
ния программы, умножив частоту выполнения каждой инструкции на время ее выпол¬
нения и суммируя соответствующие произведения.
Однако и в анализе производительности в среднем случае приходится преодолевать
различные трудности. Во-первых, входная модель может неточно характеризовать
входные данные, встречающиеся на практике, либо естественной модели входных дан¬
ных может вообще не быть. Мало кто будет возражать против использования таких
моделей входных данных, как "случайно упорядоченный файл", для алгоритма сорти¬
ровки или "случайное множество точек” для геометрического алгоритма, и для таких
моделей можно получить математические результаты, которые будут точно прогнози¬
ровать производительность программ в реальных приложениях. Но как можно харак¬
теризовать входные данные для программы, которая обрабатывает текст на английс¬
ком языке? Даже для алгоритмов сортировки в определенных приложениях другие
модели, отличные от модели случайно упорядоченных данных, представляют интерес.
Во-вторых, анализ может потребовать глубоких математических доказательств. Напри¬
мер, анализ производительности в среднем случае для алгоритмов объединения и поиска
достаточно сложен. Несмотря на то что вывод таких результатов обычно выходит за
пределы данной книги, мы будем иллюстрировать их природу целым рядом классичес¬
ких примеров, а также, при необходимости, будем ссылаться на соответствующие ре¬
зультаты (к счастью, анализ большинства рассматриваемых нами алгоритмов можно
найти в исследовательской литературе). В третьих, знания среднего значения времени
выполнения может оказаться недостаточно: может понадобиться среднее отклонение
или другие факты о распределении времени выполнения, вывод которых может ока¬
заться еще более трудным. В частности, нас будет интересовать вероятность того, что
алгоритм окажется значительно медленнее, нежели ожидалось.
Во многих случаях на первое возражение из предыдущего абзаца можно ответить
использованием фактора случайности во благо. Например, если мы случайным обра¬
зом "перемешаем" массив до сортировки, тогда допущение о том, что элементы мас¬
сива упорядочены случайным образом, будет выполнено. Для таких алгоритмов, назы¬
70 Часть 1. Анализ
ваемых рандомизированными алгоритмами (randomized algorithm), анализ производитель¬
ности в среднем случае приводит к прогнозу ожидаемого времени выполнения в стро¬
го вероятностном смысле. Более того, часто можно доказать, что вероятность того,
что такой алгоритм будет медленным, пренебрежимо мала. Примерами таких алгорит¬
мов могут служить быстрая сортировка (см. главу 9), рандомизированные BST (Binary
Search Tree - дерево бинарного поиска) (см. главу 13) и хеширование (см. главу 14).
Вычислительная сложность (computational complexity) - это направление анализа алго¬
ритмов, которое позволяет нам понимать фундаментальные ограничения, с которыми
нам, возможно, придется столкнуться при проектировании алгоритмов. Главная цель
заключается в определении времени выполнения в худшем случае лучшего алгоритма
решения данной задачи с точностью до постоянного множителя. Эта функция называ¬
ется сложностью (complexity) задачи.
Анализ производительности алгоритма в худшем случае с использованием О-нота-
ции освобождает аналитика от необходимости рассматривать характеристики конкрет¬
ной машины. Выражение "время выполнения алгоритма равно 0(f(N))" не зависит от
входных данных и облегчает распределение алгоритмов по категориям вне зависимос¬
ти от входных данных и деталей реализации, и таким образом отделяет анализ алго¬
ритма от какой-либо конкретной его реализации. В анализе мы, как правило, игнори¬
руем постоянные множители. В большинстве случаев, когда мы хотим знать,
пропорционально ли время выполнения алгоритма N или logjV, не имеет значения, на
какой машине будет выполняться алгоритм - на небольшом компьютере или на су¬
перкомпьютере. Более того, не имеет значения даже то, хорошо или плохо реализован
внутренний цикл алгоритма, то есть, с минимально необходимым или с избыточным
числом команд.
Когда мы можем доказать, что время выполнения алгоритма в худшем случае рав¬
но 0(f(N))y то говорят, что f(N) является верхней границей (upper bound) сложности за¬
дачи. Другими словами, время выполнения лучшего алгоритма не больше, чем время
любого другого алгоритма для данной задачи.
Мы постоянно стремимся улучшить алгоритмы, но, в конце концов, достигаем
точки, в которой никакое изменение, по всей вероятности, не может снизить время
выполнения. При решении конкретной задачи мы заинтересованы в том, чтобы знать,
где необходимо остановиться в улучшении алгоритма, т.е. мы ищем нижнюю границу
(lower bounds) сложности. Для многих задач можно доказать, что любой алгоритм реше¬
ния этой задачи должен использовать определенное число фундаментальных операций.
Доказательство существования нижней границы является достаточно сложной задачей,
требующей построения точной модели машины и разработки замысловатых теорети¬
ческих конструкций вводов, которая трудно решается для любого алгоритма. Мы бу¬
дем редко затрагивать вопрос определения нижних границ, тем не менее, они пред¬
ставляют собой вычислительные барьеры, которые необходимо учитывать при
проектировании алгоритмов, когда в этом возникает необходимость.
Если изучение сложности задачи показывает, что верхняя граница алгоритма соот¬
ветствуют его нижней границе, то это обстоятельство позволяет сделать вывод о том,
что нет смысла пытаться разработать алгоритм, который был бы существенно быстрее,
чем наилучший из известных алгоритмов. В этом случае можно сконцентрировать все
свои усилия на реализации. Например, бинарный поиск является оптимальным в том
Глава 2. Принципы анализа алгоритмов
71
смысле, что никакой другой алгоритм, использующий только сравнения, не сможет
обойтись меньшим их числом операций сравнения в худшем случае, чем бинарный
поиск.
Соответствие верхней и нижней границ имеет место и для алгоритмов объедине¬
ния-поиска, использующих указатели. В 1975 г. Тарьян (Taijan) показал, что алгоритм
взвешенного быстрого объединения со сжатием пути требует следования по менее чем
0(lg* V) указателям в худшем случае, и что любой алгоритм с указателями должен сле¬
довать по более чем постоянному числу указателей в худшем случае для некоторых
входных данных. Другими словами, нет смысла в дальнейшем совершенствовании ал¬
горитма, которое гарантировало бы решение задачи посредством линейного числа
операций i = a[i]. С практической точки зрения это различие очень незначитель¬
но, поскольку мало знечение lg* V, тем не менее, исследования с целью найти простой
линейный алгоритм решения этой задачи проводились в течение долгого времени, и
найденная Тарьяном нижняя граница заставила исследователей переключить свое вни¬
мание на другие задачи. Более того, эта история показывает, что нельзя обойтись без
таких функций как достаточно сложная функция log*, поскольку они свойственны
этой задаче.
Многие алгоритмы, рассматриваемые в этой книге, были подвергнуты глубокому
математическому анализу, и исследования их производительности слишком сложны,
чтобы обсуждать их здесь. Но именно эти исследования позволяют нам рекомендовать
многие из тех алгоритмов, которые рассматриваются в данной книге.
Не все алгоритмы достойны такого тщательного рассмотрения; в самом деле, во
время разработки алгоритмов предпочтение обычно отдается приближенным показате¬
лям производительности, дабы не загружать процесс разработки посторонними деталя¬
ми. По мере того как разработка алгоритма становится более детальной, таким же
становится и анализ, использующий все более тонкие математические инструменты.
Часто процесс проектирования алгоритма вызывает необходимость подробного изуче¬
ния проблемы сложности, которая, в свою очередь, приводит к таким теоретическим
алгоритмам, которые далеки от каких-либо конкретных практических приложений.
Распространенной ошибкой является мнение, что грубый анализ исследований слож¬
ности сразу же приведет к построению практически эффективного алгоритма. Такие
предположения чреваты неприятными неожиданностями. С другой стороны, вычисли¬
тельная сложность можно рассматривать как мощное инструментальное средство, ко¬
торое сообщает нам, когда мы достигнем пределов в разработке алгоритма и когда
мы должны направить свои усилия на сужение промежутка между верхней и нижней
границами.
В этой книге мы придерживаемся той точки зрения, что проектирование алгорит¬
ма, его тщательная реализация, математический анализ, теоретические исследования и
эмпирический анализ все вместе вносят важный вклад в разработку элегантных и эф¬
фективных программ. Мы стремимся получить информацию о свойствах разрабатыва¬
емых нами программ с привлечением всех доступных средств, затем модифицировать
их или разрабатывать новые программы на основе полученной информации. Мы не
имеем возможности проводить исчерпывающее тестирование и анализ каждого алго¬
ритма, с которыми мы работаем в различных программных средах на любой доступ¬
72 Часть 1. Анализ
ной машине, но мы можем воспользоваться реализациями алгоритмов, о которых мы
знаем, что они эффективны, а затем улучшать и сравнивать их, если требуется высо¬
кая производительность. На протяжении всей книги мы будем при необходимости до¬
статочно подробно рассматриваться наиболее важные методы, чтобы выяснить, что яв¬
ляется причиной их эффективной работы.
Упражнение
о 2.51. Известно, что сложность одной задачи, выраженная в единицах времени,
равна N logN, единиц, сложность другой задачи - N3 единиц. Какая неявная ин¬
формация об относительной производительности конкретных алгоритмов, которые
решают эти задачи, содержится в приведенном утверждении?
Ссылки к части 1
Существует множество вводных учебников по программированию. Однако наилуч¬
шим источником сведений о языке С с примерами программ, написанными в том же
духе, что и программы в этой книге, служит книга Кернигана и Ричи (Kernighan,
Ritchie), посвященная языку С.
Многочисленные варианты алгоритмов решения задачи объединения-поиска из гла¬
вы 1 со знанием дела разбиты по категориям и прокомментированы в статье Ван-JIe-
вена и Тарьяна (van Leeuwen, Tarjan).
В книгах Бентли (Bentley), в том же стиле, что и материал, изложенный в данной
книге, опцсаны подробные исследования нескольких конкретных случаев оценки под¬
ходов к разработке алгоритмов решения многочисленных интересных задач построе¬
нию и их реализаций.
Примером классической публикации по анализу алгоритмов, в основу которых по¬
ложены асимптотические показатели производительности алгоритма в худшем случае,
может служить книга Ахо, Хопкрофта и Ульмана (Aho, Hopcroft, Ullman). Книги Кну¬
та (Knuth) проводят более полный анализ средних случаев и могут рассматриваться
как авторитетные источники сведений о конкретных свойствах многочисленных алго¬
ритмов. Книги Тонне, Баеза-Ятса (Gonnet, Baeza-Yates) и Кормена, Лейзерсона, Ри-
веста (Cormen, Leiserson, Rivest) являются более современными работами. Обе они
включают обширный список ссылок на исследовательскую литературу.
В книге Грэхема, Кнута и Паташника (Graham, Knuth, Patashnik) рассматриваются
области математики, с которыми обычно приходится иметь дело при анализе алгорит¬
мов; этот же материал разбросан и в упомянутых ранее книгах Кнута. Книга Седжви-
ка и Флажоле представляет собой исчерпывающее введение в предмет.
А. V. Aho, J. Е. Hopcroft, and J. D. Ullman, The Design and Analysis of Algorithms, Addison-
Wesley, Reading, MA, 1975.
J. L. Bentley, Programming Pearls, Addison-Wesley, Reading, MA, 1985; More Programming
Pearls, Addison-Wesley, Reading, MA, 1988.
R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second
edition, Addison-Wesley, Reading,MA, 1984.
Глава 2. Принципы анализа алгоритмов
73
Т. Н. Согшеп, С. Е. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press/
McGraw-Hill, Cambridge, MA, 1990.
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley,
Reading, MA, 1988.
B. W. Kemighan and D. M. Ritchie, The С Programming Language, second edition,
Prentice-Hall, Englewood Cliffs, NJ, 1988.
D. E. Knuth, The Art of Computer Programming. Volume 7: Fundamental Algorithms, second
edition, Addison-Wesley, Reading, MA, 1973; Volume 2. Seminumerical Algorithms, second
edition, Addison-Wesley, Reading, MA, 1981; Volume 3: Sorting and Searching, second
printing, Addison-Wesley, Reading, MA, 1975.
R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley,
Reading, MA, 1996.
J. van Leeuwen and R. E. Tarjan, "Worst-case analysis of set-union algorithms,” Journal of
the ACM, 1984.
2
Структуры
данных
&sk&uZ zacwtv/
3
Элементарные структуры ланных
4
Абстрактные типы ланных
5
Рекурсия и леревья
Элементарные
структуры данных
Организация данных для обработки является важным
этапом разработки компьютерных программ. Для
многих приложений выбор структуры данных - един¬
ственно важное решение, которое принимается в процес¬
се реализации: как только этот выбор сделан, дальнейшая
разработка алгоритмов не вызывает затруднений. Для од¬
них и тех же данных различные структуры будут занимать
неодинаковое дисковое пространство. Одни и те же опе¬
рации с различными структурами данных создают алгорит¬
мы неодинаковой эффективности. Выбор алгоритмов и
структур данных тесно взаимосвязан. Программисты по¬
стоянно изыскивают способы повышения быстродействия
или экономии дискового пространства за счет оптималь¬
ного выбора.
Структура данных не является пассивным объектом: не¬
обходимо принимать во внимание выполняемые с ней
операции (равно как и алгоритмы, используемые для этих
операций). Эта концепция формально выражена в поня¬
тии типа данных (data type). В данной главе основное вни¬
мание уделяется конкретным реализациям базовых прин¬
ципов, используемых для организации данных. Будут
рассмотрены основные методы организации данных и уп¬
равления ими, изучен ряд примеров, демонстрирующих
преимущества каждого подхода, и сопутствующие вопро¬
сы, такие как управление областью хранения. В главе 4
обсуждаются абстрактные типы данных (ЛТД), в которых
описание типов данных отделено от их реализации.
Ниже будет представлен обзор массивов, связных спис¬
ков и строк. Эти классические структуры данных имеют
широкое применение: наряду с деревьями (см. главу 5)
они формируют основу почти всех алгоритмов, рассматри¬
ваемых в данной книге. Мы будем изучать различные при-
7 6 Часть 2. Структуры данных
митивные операции манипулирующие этими структурами данных, а также разработаем
базовый набор средств, которые можно использовать для составления сложных алго¬
ритмов, решающих трудные задачи.
Изучение хранения данных в виде объектов переменных размеров, а также в связ¬
ных структурах, требует знания, как система управляет областью хранения, которую
она выделяет программам для данных. Эта тема рассматривается не во всех подробно¬
стях, поскольку много важных моментов зависит от системы и аппаратных средств.
Тем не менее, мы ознакомимся с принципами управления хранением и несколькими
базовыми механизмами решения этой задачи. Кроме того, будут рассмотрены специ¬
альные методы, в рамках которых используются механизмы распределения памяти для
программ на языке С.
В конце главы приводится несколько примеров составных структур (compound
structures), таких как массивы связных списков и массивы массивов. Построение абст¬
рактных механизмов нарастающей сложности, начиная с нижнего уровня, является те¬
мой, к которой мы будем регулярно обращаться на протяжении данной книги. Рас¬
сматривается ряд примеров, которые служат основой для последующего составления
более совершенных алгоритмов.
Изучаемые в этой главе структуры данных служат в качестве строительных блоков,
которые можно использовать естественным образом в С и многих других языках про¬
граммирования. В главе 5 рассматривается еще одна важная структура данных - дере¬
во (tree). Массивы, строки, связные списки и деревья служат базовыми элементами
большинства алгоритмов, о которых идет речь в книге. В главе 4 рассматривается ис¬
пользование конкретных представлений, разработанных в данной книге при построе¬
нии базовых абстрактных типов данных, которые удовлетворяют требованиям многих
приложений. Остальная часть книги посвящена разработке различных вариантов базо¬
вых средств, деревьев и абстрактных типов данных для создания алгоритмов, решаю¬
щих более сложные задачи. Они также могут служить хорошей основой для высоко¬
уровневых абстрактных типов данных в разнообразных приложениях.
3.1 Строительные блоки
В этом разделе рассматриваются базовые низкоуровневые конструкции, используе¬
мые для хранения и обработки информации в языке С. Все обрабатываемые компью¬
тером данные, в конечном счете, разбиваются на отдельные биты. Однако написание
программ, обрабатывающих исключительно биты, слишком нудное и трудоемкое заня¬
тие. Типы позволяют указывать, как будут использоваться определенные наборы битов,
а функции позволяют задавать операции, выполняемые над данными. Структуры С ис¬
пользуются для группирования разнородных порций информации, а указатели (pointers)
служат для непрямой ссылки на информацию. В этом разделе изучаются основные ме¬
ханизмы языка С в контексте представления основного принципа организации про¬
грамм. Главная цель - заложить фундамент разработки структур высшего уровня (ос¬
тавшаяся часть данной главы, а также главы 3, 4 и 5), которые будут служить основой
для большинства алгоритмов, рассматриваемых в данной книге.
Программы обрабатывают информацию, которая происходит из математических
или естественных языковых описаний окружающего мира. Соответственно, вычисли¬
тельная среда обеспечивает встроенную поддержку основных строительных блоков по¬
Глава 3. Элементарные структуры данных
77
добных описаний - чисел и символов. В языке С программы построены всего лишь
на нескольких базовых типах данных:
■ Целые числа (int).
■ Числа с плавающей точкой (float).
■ Символы (char).
В обычной практике принято ссылаться на эти типы по их именам в языке С
(int, float и char), хотя часто используются обобщенные термины - целое (integer),
число с плавающей точкой (floating-point number) и символ (character). Символы чаще всего
используются в абстракциях высшего уровня - например, для создания слов и пред¬
ложений. Поэтому обзор символьных данных будет отложен до раздела 3.6, а пока