С. А. Абрамов

Лекции о сложности алгоритмов

Допущено учебно-методическим советом по прикладной математике

и информатике УМО по классическому университетскому

образованию в качестве учебного пособия для студентов высших

учебных заведений, обучающихся по специальности и направлению

«Прикладная математика и информатика» и по направлению

«Информационные технологии»

Москва

Издательство МЦНМО

2009

УДК 510.52 ББК 22.12 A16

Научный редактор Е.А.Бордаченкова

Абрамов С. А.

A16 Лекции о сложности алгоритмов. — М.: МЦНМО,

2009.—256 с.

ISBN 978-5-94057-433-0

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

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

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

ББК 22.12

© Абрамов С. А., 2009. ISBN 978-5-94057-433-0 © МЦНМО, 2009.

Предисловие

Предлагаемая книга основана на курсе лекций, читаемых автором на факультете вычислительной математики и кибернетики (ВМК) МГУ им. М.В.Ломоносова. Ее цель — обсуждение основных понятий тео­рии сложности и некоторых методов анализа сложности алгорит­мов. Это обсуждение сопровождается подробным рассмотрением со сложностной точки зрения ряда алгоритмов арифметики, сортировки и поиска, вычислительной геометрии, теории графов и др. Матери­ал группируется по главам и параграфам в соответствии с раздела­ми самой теории сложности—сложность в худшем случае, сложность в среднем, нижние границы сложности и т.д., а не по тематической принадлежности рассматриваемых алгоритмов — сортировка, теория графов, арифметика и т. д. Для того, чтобы сосредоточиться именно на понятиях и подходах теории сложности, при этом не затрачивая слишком много времени на объяснение деталей трудных для понима­ния алгоритмов, в примерах исследуются либо алгоритмы достаточно известные (сложностные характеристики которых менее известны), либо алгоритмы, суть которых может быть изложена коротко. Слож­ностные вопросы рассматриваются в книге довольно подробно, но книга значительно уступает по широте охвата алгоритмического ма­териала книгам Д. Кнута [18, 19, 20], А. Ахо, Дж.Хопкрофта и Дж.Уль­мана [5], Т.Кормена, Ч. Лейзерсона, Р. Ривеста [21], С.Баасе и А.ван Гелдера [43], Ж.Брассара и П.Берли [46], в той или иной мере отра­жающих весь спектр вопросов построения алгоритмов, и книгам по специальным алгоритмическим разделам математики—вычислитель­ной геометрии (Ф. Препарата, М. Шеймос [30]), алгоритмической тео­рии чисел (Э.Бах, Дж. Шаллит [44]), комбинаторики (Э.Рейнгольд, Ю. Нивергельт, H.Део [31]) и др. Здесь надо сказать, что названная литература, как и некоторые другие издания, послужила источником ряда примеров и задач, предлагаемых в этой книге.

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

4

Предисловие

дели. Недостающие доказательства могут быть найдены, например, в [4], [10], [13], [23].

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

Библиографические комментарии даются в сносках.

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

Автор благодарен своим коллегам по ВМК МГУ В. Б. Алексееву и В. П. Иванникову, а также Е. В. Зиме (университет Вилфрид Лауэр, Ва­терлоо, Канада) и М. Петковшеку (университет Любляны, Словения), беседы и дискуссии с которыми существенно помогли в отборе ма­териала и выработке общей схемы курса лекций и этой книги, при этом надо особо отметить, что Е. В. Зима принял участие в написании главы 6 и приложения D. Большая благодарность и А. В. Бернштей-ну (ИСА РАН), А.А.Васину (ВМК МГУ), В.А.Серебрякову (ВЦ РАН), сделавшим полезные замечания по ряду разделов книги. Автор при­знателен рецензентам М. H. Вялому (ВЦ РАН) и С. Б. Гашкову (мехмат МГУ) —их пометки на полях рукописи оказали значительную помощь на заключительном этапе работы над книгой. Особая благодарность за советы и многочисленные конструктивные замечания Е. А. Борда-ченковой (ВМК МГУ)—научному редактору книги.

Введение

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

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

Часто размер входа определяют как общее число символов в пред­ставлении входа, но возможны и другие пути. В задачах сортировки и поиска размер входа — это, как правило, количество элементов n входного массива, в задачах на графах —число вершин |V | или чис­ло ребер |E | входного графа G = (V, E), но, с другой стороны, |V | и | E | могут рассматриваться и совместно как два параметра раз­мера входа. В арифметических задачах размером входа может быть, например, максимум абсолютных величин входных целых чисел, или количество цифр в двоичной записи этого максимума, или же, как уже говорилось, суммарное количество двоичных цифр всех входных чисел и т.д.—выбор делается в зависимости от характера задачи.

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

6

Введение

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

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

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

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

См., например, статью «Алгоритма сложность» в [40].

Введение

7

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

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

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

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

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

Сд(х), Сд(х)—временные и пространственные затраты алгоритма А для входа (входных данных) х;

\\х\\— размер входах;

T_A{s), S_A(s)—значения временной и пространственной сложности ал­горитма А для значения s размера входа;

А(п)—количество цифр в двоичной записи неотрицательного цело­го п (битовая длина п);

Я* (п) — количество единиц в двоичной записи неотрицательного це­лого п;

[а] —наибольшее целое, меньшее или равное вещественному а;

\а] —наименьшее целое, большее или равное вещественному а;

N, N⁺—множества неотрицательных и положительных целых чисел;

Z—множество (кольцо) целых чисел;

Z_k — кольцо вычетов по модулю к;

Q, Ж, С — множества (поля) рациональных, вещественных и ком­плексных чисел;

П_п —множество всех перестановок чисел 1, 2,..., п;

□—конец доказательства.

Глава 1

Сложности алгоритмов

как функции числовых аргументов.

Сложность в худшем случае

§ 1. Затраты алгоритма для данного входа, алгебраическая сложность

Пусть по входным данным (входу) х алгоритм А вычисляет результат (выход) у. Такое вычисление связано с затратами времени и памя­ти. Допустим, что достигнуто соглашение о том, как измеряются эти затраты, тогда можно рассмотреть функции затрат

С\{х), C^s_A{x),

где верхний индекс Т указывает на временные затраты^г, S — на пространственные затраты (затраты памяти и пространственные за­траты— это синонимы), соответствующие вычислениям, связанным с применением А к входу х; буквы Т и S возникают из английских слов time — время и space — пространство. Вид этих функций может быть очень непростым; их трудно исследовать методами математи­ческого анализа, потому что аргумент х не является, вообще говоря, числом и не принадлежит какому-либо метрическому пространству. Можно ввести некоторую неотрицательную числовую характеристику ||х|| возможных входов алгоритма и оценивать функции затрат с по­мощью функций, зависящих не от х, а от ||х||:

C^T_A{x)^Lp{\\x\\), C^s_A{x)^^{\\x\\). (1.1)

Если ц> и -ф не слишком быстро растут при возрастании (числового) аргумента, то эти оценки могут обнадеживать автора или потреби­теля алгоритма А.

¹ Здесь и далее имеется в виду временные (связанные с расходованием времени), а не временные (непостоянные, краткосрочные) затраты. Аналогично — временная сложность и т.д.

10 Глава 1. Сложности алгоритмов как функции числовых аргументов

Избираемую нами величину || • || принято называть размером вхо­да. В соответствии с нашим замыслом размер входа должен харак­теризовать «громоздкость» исходных данных; то, что ||x|| является числом, позволяет говорить о росте ip, ip и исследовать этот рост. Выбор размера входа —существенный этап оценивания функций за­трат; нужна, во всяком случае, уверенность, что оценки вида (1.1) будут нести полезную информацию.

В дальнейшем, однако, предметом нашего изучения будут не функ­ции затрат, а некоторые другие функции, о которых мы скажем по­сле ряда примеров. Предварительно условимся о некоторых обычных для литературы по сложности алгоритмов обозначениях. Пусть ael, т.е. a — вещественное число. Значение |_aj есть результат округле­ния a до целого в меньшую сторону: 1.3,14J = 3, |_-3,14| = -4 (эту величину — целую часть a — записывают и как [a]). Соответствен­но, \a] есть результат округления a до целого в большую сторону: [3,141=4, [-3,141 = -3. Если a — целое, то [a\ = \a]=a.

Рассмотрим три простых примера.

Пример 1.1. Исходя из определения произведения матриц, мы по­лучаем алгоритм умножения двух квадратных матриц порядка n, тре­бующий n³ операций умножения. Этот алгоритм далее будет обозна­чаться буквами MM, от английских слов matrix multiplication — мат­ричное умножение.

Пример 1.2. Один из очевидных алгоритмов распознавания про­стоты данного neN⁺, который мы будем называть алгоритмом проб­ных делений, состоит в выяснении того, имеется ли среди чисел 2, 3, ..., LVnJ хотя бы одно, делящее n. Количество проверок дели­мости n на те или иные целые числа (для краткости можно гово­рить о «числе делений») колеблется от 1 до LanJ - 1. Этот алго­ритм далее будет обозначаться буквами TD, от английских слов trial divisions —пробные деления.

Пример 1.3. При сортировке простыми вставками число сравне­ний¹ колеблется от n - 1 до —-—, в зависимости от входного мас­сива x ₁,x₂, ...,x_n. Если интересоваться числом перемещений элемен-

¹ Основные алгоритмы сортировки и поиска приводятся в приложении A. Обсуждая конкретные алгоритмы сортировки, мы для краткости иногда будем опускать само сло­во «алгоритм», говоря, например, не об алгоритме сортировки простыми вставками, а просто о сортировке простыми вставками и т. д. Все сортировки, которые мы рассмат­риваем, являются сортировками с помощью сравнений, т. е. никаких других операций, кроме сравнений и перемещений (присваиваний или обменов), над элементами мас­сива производиться не может, — исключение составляет пример 29.1. Элементы сор-