Алгоритмы и их сложность.

Различают массовые и индивидуальные задачи. Примеры массовых задач:

задача о кратчайшем пути, задача Коммивояжеры, задача о назначениях и др. Индивидуальная задача получается из массовой с помощью фиксаций набора условий. Каждая массовая задача характеризуется размером (мерой количества входных данных). Например, в задаче Коммивояжеры размерность – это число городов. Алгоритм – это общий пошаговый способ получения решения данной задачи. Формализуют понятие алгоритма машину Тьюринга рекурсивной функцией и нормальный алгоритм Марка. Для оценки качества алгоритмов применяют следующие критерии: 1) Временная сложность в худшем случае. Пусть размер массовой задачи определяется параметром n. Обозначим через t(n) максимальное число действий для решения конкретной индивидуальной задачи. t(n) – есть временная сложность алгоритма. 2) Асимптотическая сложность. Это порядок роста сложности при условии, что размер задачи неограниченно возрастает. При сравнении скорости 2-х неотрицательных функций f(n) и g(n) используют следующие обозначения f(n)=0(g(n)). Говорят, что f(n)=0(g(n)), если существуют такие положительные константы c и N, что f(n)<=c*g(n) для всех n>N. В этой же ситуации используют g(n)= . Алгоритм считается достаточно хорошим, если его сложность есть O(n^k), при некотором к>0. В этом случае говорят, что алгоритм имеет полиномиальную сложность. Задача решается за полиномиальное время и называется полиномиально разрешимой. Если сложность алгоритма u(n), то его называют линейным. Если его сложность , то его называют экспоненциальным. Задача о кратчайшем пути и его назначениях называется полиномиальной. Понятие сложности иллюстрируется в следующей таблице:

Пусть 1 шаг работы алгоритма требует для выполнения 1мс.

ПРИМЕРЫ

МТ: опр., примеры.