алгоритмов union-find для конкретизации определенных моментов. Несколько новых примеров подробно обсуждаются в разделе 2.6.

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

Полный охват методов анализа алгоритмов сам по себе является предметом книги {см. раздел ссылок), однако здесь рассматриваются основы, которые позволят

Проиллюстрировать процесс.

Описать в одном месте используемые математические соглашения.

Обеспечить основу для обсуждения вопросов высокого уровня.

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

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

2.1. Разработка и эмпирический анализ

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

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

Мы выражаем алгоритмы на С++, но эта книга об алгоритмах, а не о программировании на С++. Конечно же, мы рассматриваем реализации на С++ многих важных задач, и когда существует удобный и эффективный способ решить задачу именно средствами С++, мы пользуемся этим достоинством. Тем не менее, подавляющее большинство выводов о реализации алгоритмов применимы к любой современной среде программирования. Перевод программ из главы 1 или любых других программ в этой книге на другой современный язык профаммирования - это достаточно про-

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

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

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

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

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

Один из первых шагов для продвижения вперед в понимании производительности алгоритмов - это эмпирический анализ. Если есть два алгоритма для решения одной задачи, то в методе нет никакого волшебства: мы запустим оба и определим, который выполняется дольше! Это концепция может показаться слишком очевидной, чтобы о ней стоило говорить, но, тем не менее, это распространенное упущение в сравнительном анализе алгоритмов. Тот факт, что один алгоритм в 10 раз быстрее другого, вряд ли ускользнет от взора того, кто ждет 3 секунды при выполнении одного и 30 секунд - при выполнении другого, однако его легко упустить как небольшой постоянный фактор при математическом анализе. Когда мы отслеживаем про-

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

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

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

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

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