Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Основные определения асимптотического анализа алгоритмов



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

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

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

В асимптотическом анализе приняты следующие обозначения:

1) Оценка Q (тетта)

Пусть f(n) и g(n) – положительные функции положительного аргумента, n ≥ 1 (количество объектов на входе и количество операций – положительные числа), тогда:f(n) = Q (g(n)), если существуют положительные с1, с2, n0, такие, что: с1 * g(n) £ f(n) £ c2 * g(n), при n > n0

Рисунок 2.1 – Оценка Q

 

Обычно говорят, что при этом функция g(n) является асимптотически точной оценкой функции f(n), т.к. по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя.

Отметим, что из f(n) = Q (g(n)) следует, что g(n) = Q (f(n)).

Примеры:

1) f(n)=4n2+nlnN+174 – f(n)= Q(n2);

2) f(n)=Q(1) – запись означает, что f(n) или равна константе, не равной нулю, или f(n) ограничена константой на ¥ : f(n) = 7+1/n = Q(1).

2) Оценка О (О большое)

В отличие от оценки Q, оценка О требует, чтобы функция f(n) не превышала g(n) начиная с n > n0, с точностью до постоянного множителя:

$ c > 0, n0 > 0 :

0 £ f(n) £ c * g(n), "n > n0

 

Рисунок 2.2 – Оценка О (О большое)

 

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

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

Это требует практического сравнительного анализа алгоритмов, для чего осуществляется:

· детальный анализ трудоемкости алгоритмов, получение в явном виде функции трудоемкости;

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

Реализация второго этапа – сравнительного анализа функций трудоемкости – предполагает определение характеристических значений реального множества исходных данных задачи (Da), при которых предпочтение может быть отдано одному из анализируемых алгоритмов. Можно считать, что таким характеристическим значением является размерность множества исходных данных - n , а трудоемкость алгоритма в основном определяется количеством исходных данных - f(Da) = f(n).

Таким образом, сравнительный анализ функций трудоемкости предполагает определение тех интервалов аргумента функций трудоемкости, при которых данный алгоритм может быть выбран в качестве рационального. В связи с этим предлагаемый ниже метод назван интервальным анализом функций (трудоемкости алгоритмов) по аналогии с асимптотическим анализом - определением сложности алгоритмов.

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

Реально выбор данного алгоритма как предпочтительного, может быть произведен даже тогда, когда его трудоемкость на данном интервале несколько хуже, не более, чем на порог φ, чем трудоемкость других алгоритмов. Или несколько алгоритмов могут быть использованы на этом интервале эквивалентно, с расхождением на более чем на порог φ. Это приводит к необходимости введения специальных обозначений в аппарате интервального анализа.

 

2.2 Система обозначений в интервальном анализе функций

 

Пусть трудоемкости двух алгоритмов заданы в явном виде функциями и соответственно, пусть задан также порог φ допустимого расхождения значений функций на интервале, мера расхождения функций при данном и интервал значений . Тогда считаем, что:

а) ;

б) ;

в) .

2.3 Метод интервального анализа

 

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

· Определение для данной конкретной задачи допустимого интервала изменения размерности множества исходных данных ;

· Получение в явном виде функций трудоемкости анализируемых алгоритмов и ;

· Разбиение интервала на подинтервалы, в каждой целочисленной точке которых явно выполняется одно из следующих соотношений для принятой меры :

1) если , то и предпочтительным на данном подинтервале является алгоритм, имеющий функцию трудоемкости .

2) если , то и оба алгоритма с точностью до порога могут быть использованы на этом подинтервале.

3) если , то и предпочтительным на данном подинтервале является алгоритм, имеющий функцию трудоемкости .

 

2.4 Мера

 

Мера расхождения значений функций и при фиксированном n должна удовлетворять следующим требованиям:

- ;

- .

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

;

Поскольку значения функций трудоемкости положительны, то при таком определении меры значения ограничены между π/2 и - π/2. Пороговое значение может быть интерпретировано, как максимальное значение угла расхождения, для которого алгоритмы могут быть признаны равноприменимыми на интервале.

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

 

 

 

 

 


 

 




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.