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

С. А. Абрамов

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

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

Электронное издание

Москва
Издательство МЦНМО


УДК .
ББК .
A

Абрамов С. А.
Лекции о сложности алгоритмов.
Электронное издание
М.: МЦНМО, 
 с.
ISBN ----

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

Подготовлено на основе книги: С. А. Абрамов. Лекции о сложности
алгоритмов. — -е изд., перераб. — М.: МЦНМО, .

Издательство Московского центра
непрерывного математического образования
, Москва, Большой Власьевский пер., . Тел. () --
http://www.mccme.ru

ISBN ----
© Абрамов С. А., .
© МЦНМО, .

Предисловие

Предлагаемая книга основана на курсе лекций, читаемых автором
на факультете вычислительной математики и кибернетики (ВМК)
МГУ им. М. В. Ломоносова. Ее цель — обсуждение основных понятий
теории сложности и некоторых методов анализа сложности алгоритмов. Это обсуждение сопровождается подробным рассмотрением со
сложностной точки зрения ряда алгоритмов арифметики, сортировки
и поиска, вычислительной геометрии, теории графов и др. Материал
группируется по главам и параграфам в соответствии с разделами
самой теории сложности — сложность в худшем случае, сложность
в среднем, нижние границы сложности и т. д. Для того, чтобы сосредоточиться именно на понятиях и подходах теории сложности, при
этом не затрачивая слишком много времени на объяснение деталей
трудных для понимания алгоритмов, в примерах исследуются либо
алгоритмы достаточно известные (сложностные характеристики которых менее известны), либо алгоритмы, суть которых может быть
изложена коротко. Сложностные вопросы рассматриваются в книге
довольно подробно, но книга значительно уступает по широте охвата алгоритмического материала книгам Д. Кнута [, , ], А. Ахо,
Дж. Хопкрофта и Дж. Ульмана [], Т. Кормена, Ч. Лейзерсона, Р. Ривеста [], С. Баасе и А. ван Гелдера [], Ж. Брассара и П. Берли [],
отражающих обширный спектр вопросов построения алгоритмов,
и книгам по специальным алгоритмическим разделам математики — вычислительной геометрии (Ф. Препарата, М. Шеймос []), алгоритмической теории чисел (Э. Бах, Дж. Шаллит []), комбинаторики (Э. Рейнгольд, Ю. Нивергельт, H. Део []) и др. Здесь надо сказать,
что названная литература, как и некоторые другие издания, послужила источником ряда примеров и задач, предлагаемых в этой книге.
В последних трех параграфах, касающихся классов P и NP, понятия NP-полноты и т. д., ряд фактов дается без доказательства. Это
объясняется тем, что в книге используются менее формальные модели вычислений, чем, скажем, машина Тьюринга, а доказательства
упомянутых фактов опираются на полностью формализованные модели. Недостающие доказательства могут быть найдены, например,
в [], [], [], [].


Предисловие

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

∗
∗
∗

Первое издание книги вышло в  г. Во втором издании исправлены замеченные опечатки и ошибки. Изложение местами упрощено,
материал внутри некоторых параграфов перекомпонован, добавлен
ряд задач.

Введение

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


Введение

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

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

Введение


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

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

C

T

A(
x),
C

S

A(
x)— временн´ые и пространственные затраты алгоритма
A
для входа (входных данных)
x;
∥
x∥ — размер входа
x;

T

A(
s),
S

A(
s)—значения временн´ой и пространственной сложности алгоритма
A для значения
s размера входа;
λ(
n) — количество цифр в двоичной записи неотрицательного целого
n (битовая длина
n);
λ∗(
n) — количество единиц в двоичной записи неотрицательного целого
n;
⌊
a⌋ — наибольшее целое, меньшее или равное вещественному
a;
⌈
a⌉ — наименьшее целое, большее или равное вещественному
a;
, + — множества неотрицательных и положительных целых чисел;
— множество (кольцо) целых чисел;
k — кольцо вычетов по модулю
k;
, , — множества (поля) рациональных, вещественных и комплексных чисел;
Π

n — множество всех перестановок чисел 1, 2, ...,
n;
□ — конец доказательства.

Глава 

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

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

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

C

T

A(
x),
C

S

A(
x),

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

C

T

A(
x) ⩽ ϕ(∥
x∥),
C

S

A(
x) ⩽ ψ(∥
x∥).
(.)

Если ϕ и ψ не слишком быстро растут при возрастании (числового)
аргумента, то эти оценки могут обнадеживать автора или потребителя алгоритма
A.

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

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

Избираемую нами величину ∥·∥ принято называть размером входа.
В соответствии с нашим замыслом размер входа должен характеризовать «громоздкость» исходных данных; то, что ∥
x∥ является числом,
позволяет говорить о росте ϕ, ψ и исследовать этот рост. Выбор размера входа— существенный этап оценивания функций затрат; нужна,
во всяком случае, уверенность, что оценки вида (.) будут нести полезную информацию.
В дальнейшем, однако, предметом нашего изучения будут не функции затрат, а некоторые другие функции, о которых мы скажем после ряда примеров. Предварительно условимся о некоторых обычных
для литературы по сложности алгоритмов обозначениях. Пусть
a ∈ ,
т. е.
a — вещественное число. Значение ⌊
a⌋ есть результат округления
a до целого в меньшую сторону: ⌊3,14⌋ = 3, ⌊−3,14⌋ = −4 (эту
величину — целую часть
a — записывают и как [
a]). Соответственно, ⌈
a⌉ есть результат округления
a до целого в большую сторону:
⌈3,14⌉ = 4, ⌈−3,14⌉ = −3. Если
a — целое, то ⌊
a⌋ = ⌈
a⌉ =
a.
Рассмотрим три простых примера.

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

Пример .. Один из очевидных алгоритмов распознавания простоты данного целого
n ⩾ 2, который мы будем называть алгоритмом
пробных делений, состоит в выяснении того, имеется ли среди чисел
2, 3, ..., ⌊n⌋ хотя бы одно, делящее
n; легко заметить, что
d ⩽ ⌊n⌋
для целого
d ⩾ 2, если и только если

n

d ⩾
d. Количество проверок делимости
n на те или иные целые числа (для краткости можно говорить о «числе делений») колеблется от 0 до ⌊n⌋ − 1. Этот алгоритм далее будет обозначаться буквами TD, от английских слов trial
divisions — пробные деления.

Пример .. При сортировке простыми вставками число сравне
ний  колеблется от
n − 1 до

n(
n − 1)

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