Алгоритмы на С++

Алгоритмы на С++

2-е издание, исправленное

Седжвик Р.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Алгоритмы на С++/ Р. Седжвик - М.: Национальный Открытый Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2015-2016
(c) Седжвик Р., 2015-2016

3

Введение

В лекции дается объяснение понятия “алгоритм”, приводятся некоторые примеры и
утверждения об алгоритмах.

Алгоритмы

В общем случае при создании компьютерной программы мы реализуем метод, который
ранее был разработан для решения какой-либо задачи. Часто этот метод не зависит от
конкретного используемого компьютера — он примерно одинаково пригоден для
многих компьютеров и многих компьютерных языков. именно метод, а не саму
программу нужно исследовать для выяснения способа решения задачи. Для метода
решения задачи, пригодного для реализации в виде компьютерной программы, в
компьютерных науках используется термин алгоритм. Алгоритмы составляют основу
компьютерных наук: это основные объекты изучения во многих, если не в
большинстве областей этих наук.

В основном представляющие интерес алгоритмы тесно связаны с методами
организации данных, участвующих в вычислениях. Созданные таким образом объекты
называются структурами данных, и они также являются центральными объектами
изучения в компьютерных науках. То есть алгоритмы и структуры данных идут рука об
руку. В этом курсе мы покажем, что структуры данных существуют в качестве
побочных или конечных продуктов алгоритмов и, следовательно, их нужно изучить,
чтобы понять алгоритмы. Простые алгоритмы могут порождать сложные структуры
данных и наоборот, сложные алгоритмы могут использовать простые структуры
данных. В этом курсе будут изучены свойства множества структур данных, так что
курс вполне мог бы называться “Алгоритмы и структуры данных на C++”.

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

Основная побудительная причина изучения алгоритмов состоит в том, что это
позволяет обеспечить огромную экономию ресурсов, вплоть до получения решений
задач, которые в противном случае были бы невозможны. В приложениях, в которых
обрабатываются миллионы объектов, часто хорошо разработанный алгоритм позволяет
ускорить работу программы в миллионы раз. Подобный пример приводится в разделе
1.2 и в множестве других разделов курса. Для сравнения: затраты дополнительных
денег или времени для приобретения и установки нового компьютера потенциально
позволяет ускорить работу программы всего в 10—100 раз. Тщательная разработка
алгоритма — исключительно эффективная часть процесса решения сложной задачи в
любой области применения.

4

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

Совместное использование программ в компьютерных системах становится все более
распространенным, поэтому, хотя можно ожидать, что использовать придется многие
из рассмотренных в курсе алгоритмов, одновременно можно надеяться, что
реализовывать придется лишь немногие из них. Например, библиотека стандартных
шаблонов (Standard Template Library) C++ содержит реализации множества базовых
алгоритмов. Однако реализация простых версий основных алгоритмов позволяет
лучше их понять и, следовательно, эффективнее использовать и настраивать более
совершенные библиотечные версии. И что еще важнее, очень часто возникает
необходимость самостоятельной реализации основных алгоритмов. Основная причина
состоит в том, что мы очень часто сталкиваемся с совершено новыми
вычислительными средами (аппаратными и программными), новые свойства которых
не могут наилучшим образом использоваться старыми реализациями. То есть чтобы
наши решения были более переносимыми и применимыми, часто приходится
реализовывать базовые алгоритмы, приспособленные к конкретной задаче, а не
основывающиеся на системных подпрограммах. Другая часто возникающая причина
самостоятельной реализации базовых алгоритмов заключается в том, что несмотря на
усовершенствования, встроенные в C++, механизмы, используемые для совместного
использования программ, не всегда достаточно мощны, чтобы библиотечные
программы можно было легко приспособить к эффективному выполнению конкретных
задач.

Компьютерные программы часто чрезмерно оптимизированы. Обеспечение наиболее
эффективной реализации конкретного алгоритма может не стоить затраченных усилий,
если только алгоритм не должен использоваться для решения очень сложной задачи
или же многократно. В противном случае вполне сгодится качественная, сравнительно
простая реализация: достаточно быть уверенным в ее работоспособности и в том, что,
скорее всего, в худшем случае она будет работать в 5—10 раз медленнее наиболее
эффективной версии, что может означать увеличение времени выполнения на
несколько дополнительных секунд. И напротив, правильный выбор алгоритма может
ускорить работу в 100—1000 и более раз, что во время выполнения может сэкономить
минуты, часы и даже более того. В этом курсе основное внимание уделяется
простейшим приемлемым реализациям наилучших алгоритмов.

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

5

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

Пример задачи: связность

Предположим, что имеется последовательность пар целых чисел, в которой каждое
целое число представляет объект некоторого типа, а пара p-q означает “p связано с q”.
Предполагается, что отношение “связано с” является транзитивным: если p связано с q,
а q связано с r, то p связано с r. Задача состоит в написании программы для
исключения лишних пар из набора: когда программа вводит пару p-q, она должна
выводить эту пару только в том случае, если из просмотренных до данного момента
пар не следует, что p связано с q. Если в соответствии с ранее просмотренными парами
следует, что p связано с q, программа должна игнорировать пару p-q и переходить ко
вводу следующей пары. Пример такого процесса показан на рис. 1.1.

Рис. 1.1.  Пример связности

При заданной последовательности пар целых чисел, представляющих связи между
объектами (слева) алгоритм определения связности должен выводить только те пары,
которые определяют новые связи (в центре). Например, пара 2-9 не должна
выводиться, поскольку связь 2-3-4-9 определяется ранее указанными связями
(подтверждение этого показано справа).

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

6

Например, целые числа могли бы представлять компьютеры в большой сети, а пары
могли бы представлять соединения в сети. Тогда такая программа могла бы
использоваться для определения того, нужно ли устанавливать новое прямое
соединение между p и q, чтобы они могли обмениваться информацией, или же для
установки коммуникационного пути можно использовать существующие соединения.
В подобных приложениях может потребоваться обработка миллионов точек и
миллиардов или более соединений. Как мы увидим, решить задачу для такого
приложения было бы невозможно без эффективного алгоритма. Аналогично, целые
числа могли бы представлять контакты в электрической сети, а пары могли бы
представлять связывающие их проводники. В этом случае программу можно было бы
использовать для определения способа соединения всех точек без каких-либо
избыточных соединений, если это возможно. Не существует никакой гарантии, что
связей в списке окажется достаточно для соединения всех точек — действительно,
вскоре мы увидим, что определение факта, так ли это, может быть основным
применением нашей программы.

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

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

Такие приложения, как задача установления эквивалентности имен переменных,
описанная в предыдущем абзаце, требует, чтобы с каждым отдельным именем
переменной было сопоставлено целое число. Это сопоставление подразумевается
также и в описанных приложениях сетевого соединения и соединения в электрической
цепи. В лекциях 10—16 мы рассмотрим ряд алгоритмов, которые могут эффективно
обеспечить такое сопоставление. Таким образом, в этой лекции без ущерба для
общности можно предположить, что имеется N объектов с целочисленными именами от
0 до N — 1 .

7

Рис. 1.2.  Большой пример задачи связности

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

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

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

8

Добавление в определение такого требования усложнило бы задачу и привело к
другому семейству алгоритмов, которое будет кратко рассматриваться в “Рекурсия и
деревья” и подробно — в части VII.

Упомянутые в предыдущем абзаце определения требуют больше информации, чем
первоначальное; может также требоваться и меньше информации. Например, может
потребоваться просто ответить на вопрос: “Достаточно ли M связей для соединения
всех N объектов?”. Эта задача показывает, что для разработки эффективных
алгоритмов часто требуется выполнение умозаключений об абстрактных
обрабатываемых объектах на высоком уровне. В данном случае из фундаментальных
положений теории графов следует, что все N объектов связаны тогда и только тогда,
когда количество пар, образованных алгоритмом решения задачи связности, равно
точно N — 1 (см. “Рекурсия и деревья”). Иначе говоря, алгоритм решения задачи
связности никогда не выводит более N — 1 пар, поскольку как только он выведет N — 1
пару, любая встретившаяся после этого пара будет уже связанной. Соответственно,
можно создать программу, отвечающую “да-нет” на только что поставленный вопрос,
изменив программу, которая решает задачу связности, на такую, которая увеличивает
значение счетчика, а не записывает ранее не связанную пару, отвечая “да”, когда
значение счетчика достигает N— 1 , и “нет”, если это не происходит. Этот вопрос —
всего лишь один из множества вопросов, которые могут возникнуть относительно
связности. Входной набор пар называется графом (graph), а выходной набор пар —
остовным деревом (spanning tree) этого графа, которое связывает все объекты.
Свойства графов, остовных деревьев и всевозможные связанные с ними алгоритмы
будут рассматриваться в части VII.

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

находить набор, содержащий данный элемент
замещать наборы, содержащие два данных элемента, их объединением.

Организация алгоритмов посредством этих абстрактных операций, похоже, не отсекает
никакие варианты решения задачи связности, и эти операции могут оказаться
полезными при решении других задач. Разработка уровней абстракции с еще
большими возможностями — важный процесс в компьютерных науках в целом и в
разработке алгоритмов в частности, и в этом курсе мы будем обращаться к нему
многократно. В данной лекции для разработки программ решения задачи связности мы
используем неформальное абстрактное представление; а в “Абстрактные типы данных”
эти абстракции будут выражены в коде C++.

9

Задача связности легко решается с помощью абстрактных операций поиск (find) и
объединение (union). После считывания новой пары p-q мы выполняем операцию
поиск для каждого члена пары. Если оба члена пары находятся в одном множестве, мы
переходим к следующей паре; если нет, то выполняем операцию объединение и
записываем пару. Наборы представляют собой связанные компоненты: подмножества
объектов, характеризующиеся тем, что любые два объекта в данном компоненте
связаны. Этот подход сводит разработку алгоритмического решения задачи связности к
задачам определения структуры данных, которая представляет множества, и
разработке алгоритмов объединение и поиск, которые эффективно используют эту
структуру данных.

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

Упражнения

1.1. Приведите выходные данные, которые должен выдавать алгоритм связности для
входных пар 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3.

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

1.3. Опишите простой метод подсчета количества наборов, остающихся после
применения операций объединение и поиск для решения задачи связности, как описано
в тексте.

Алгоритмы объединения и поиска

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

Первое, что приходит в голову — организовать способ сохранения всех вводимых пар,
а затем создать функцию для их просмотра, чтобы попытаться выяснить, связана ли
очередная пара объектов. Однако мы используем другой подход. Во-первых,
количество пар может быть настолько велико, что не позволит хранить их все в памяти
в используемом на практике приложении. Во-вторых, что гораздо важнее, не
существует никакого простого метода, который сам по себе позволяет определить,
связаны ли два объекта в наборе всех соединений, даже если бы удалось их все
сохранить! Базовый метод, использующий этот подход, рассматривается в “Рекурсия и

10