Основы анализа алгоритмов

Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов.

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

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

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

Число элементарных операций и измеряет относительное время выполнения алгоритма.

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

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

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

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

Формальное описание:

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

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

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

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

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

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

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

S_d – память для хранения промежуточных результатов;

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

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

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

Функцией трудоемкости F_a (N) называется отношение, связывающие входные данные алгоритма с количеством элементарных операций.

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

y_A=c₁ * F_a(N) + c₂ * M + c₃ * S_d + c₄ * S_r, где c_i – веса ресурсов.

Трудоёмкость алгоритмов по-разному зависит от входных данных.

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

Пусть D_А – множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D Î D_А –конкретная проблема и |D| = N.

В общем случае существует собственное подмножество множества D_А, включающее все конкретные проблемы, имеющие мощность N:

обозначим это подмножество через D_N: D_N = {DÎ D_N,: |D| = N} имощность множества D_N через M_DN → M_DN = |D_N |.

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

Ведем следующие обозначения:

1. F_a^Ù(N) – худший случай – наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

DÎDN

F_a^Ù(N) = max {F_a (D)} – худший случай на D_N

2. F_a^Ú(N) – лучший случай – наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

DÎDN

F_a^Ú(N) = min {F_a (D)} – лучший случай на D_N

3. ` F_a(N) – средний случай – среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

DÎDN

`F_a(N) = (1 / M_DN)*å {F_a (D)} – средний случай на D_N

Классификация алгоритмов по виду функции трудоёмкости.

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