Анализ

Ввеление

Приниипы анализа алгоритмов

Введение

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

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

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

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

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

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

1.1 Алгоритмы

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

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

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

Основная побудительная причина изучения алгоритмов состоит в том, что это позволяет обеспечить огромную экономию ресурсов, вплоть до получения решений за-