Анализ алгоритма и его сложности.

1. В начале проводится оценка ресурсов:

• Как будет использовать алгоритм ресурсы машины, например, память (получение оценок или границ для объема памяти).

• Полезно оценить время работы до отладки и программирования.

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

Когда можно считать решение задачи оптимальным? Когда алгоритм настолько хорош, что его невозможно значительно улучшить.

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

Пример: Проведем оценку для "Задачи коммивояжера" при n=20;

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

Критерий оценки качества алгоритма А основан на времени работы в худшем случае:

1. Алгоритм А - полиномиальный, если f_A(n) растет быстрее, чем полином от n.

2. В противном случае алгоритм А называется экспоненциальным (е^х)

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

Введем обозначения:

Функцию f(n) обозначим как О[g(n)] и будем говорить, что она порядка g(n) для больших n, если lim ^f(n)/_g(n)=const0

Функцию f(n) обозначим как o[z(n)] и будем говорить, что она порядка z(n) для больших n, если lim ^f(n)/z_(n)=0

Если f(n)=О[g(n)], то эти две функции возрастают с одинаковой скоростью при n, то есть эти два алгоритма одного класса, они одинаково растут.

Если f(n)=o[z(n)], то z(n) растет горазда быстрее, чем f(n).

Примеры:

1. Полином f(n)=2n⁵+6n⁴+6n²+18 есть О(n⁵)

2. Функция f(n)=2ⁿ есть о(n!), так как 2ⁿ/n!0

f(n)=O(2ⁿ⁺¹)

f(n)=o(5ⁿ⁺¹)

__

3. f(n)=1000n f(n)=O(n)

Итак, алгоритм А полиномиальный, если f_А(n)=O(P_k(n)) или f_А(n)=о(P_k(n)), где P_k(n)- некоторый многочлен от переменной n произвольной фиксированной степени k.

В противном случае алгоритм является экспоненциальным.

"Задача коммивояжера"

Размерность задачи - n.

Оценка времени работы алгоритма O(n!), так как количество перестановок первых n-1 положительных целых чисел (n-1)!, то есть эта часть алгоритма потребует O(n-1!) шагов. В каждой перестановке можно найти путь и его стоимость за O(n) шагов (т. к. n сумм.)

f_А(n)=O[n(n-1)!]=O(n!) - верхняя граница для общего времени работы.

n=20

время выполнения одной операции:

(сравнение, сложение, поиск элемента матрицы) 10^-7 сек.

Тогда 20!210¹⁸(по формуле Стирлинга n!=210^n-2)

c210¹⁸10^-7=c210¹¹(70 веков), где с константа.

Замечание: Умные люди все это вычисляют на стадии разработки алгоритма, а не после того как запрограммируют.