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

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

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

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

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

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

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

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

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

Например, целые числа могли бы представлять компьютеры в большой сети, а пары могли бы представлять соединения в сети. Тогда такая программа могла бы использоваться для опреде-

РИСУНОК 1.1 ПРИМЕР СВЯЗНОСТИ

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

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

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

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

ЫЕР-IrcjTTtrrt;- u in - ri

РИСУНОК 1.2 БОЛЬШОЙ ПРИМЕР СВЯЗНОСТИ

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