Сравнительные оценки алгоритмов

Анализ алгоритмов

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

Трудоёмкость алгоритмов по-разному зависит от входных данных. Для некоторых алгоритмов трудоемкость зависит только от объема данных, для других алгоритмов — от значений данных, в некоторых случаях порядок поступления данных может влиять на трудоемкость. Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов.

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

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

В целях дальнейшего анализа примем следующие допущения:

- каждая команда выполняется не более чем за фиксированное время;

- исходные данные алгоритма представляются машинными словами по β битов каждое.

Конкретная проблема задается N словами памяти, таким образом, на входе алгоритма - N_β=N•βбит информации. Отметим, что в ряде случаев, особенно при рассмотрении матричных задач N является мерой длины входа алгоритма, отражающей линейную размерность.

Программа, реализующая алгоритм для решения общей проблемы состоит из М машинных инструкций по β_м битов - М_β=М•β_м бит информации.

Кроме того, алгоритм может требовать следующих дополнительных ресурсов абстрактной машины:

- S_α— память для хранения промежуточных результатов;

- S_γ— память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов).

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

Под трудоёмкостью алгоритма для данного конкретного входа - F_α(N), будем понимать количество «элементарных» операций, совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.

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

Ψ_A=С₁ • F_α(N)+ С₂ •М+ С₃ •S_α+ С₄ • S_γ, где С_i - веса ресурсов.