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

Асимптотические классы и отношения

Читайте также:
  1. Biglnteger Классы
  2. I.Диагностика самоотношения.
  3. Object классы
  4. Абстрактные классы и чистые виртуальные функции. Виртуальные деструкторы. Дружественные функции. Дружественные классы.
  5. Аграрные отношения и формы землевладения. Усиление эксплуатации общинников.
  6. Аграрные отношения феодальной Индии. Крестьянская община
  7. Аграрные отношения. Экономическая и социальная политика Комнинов.
  8. Административно-правовые нормы. Административно-правовые отношения.
  9. Административно-правовые отношения. Особенности административно-правовых отношений.
  10. Административно-процессуальные нормы и отношения
  11. Баланс предприятия, его агрегированная форма. Основные балансовые соотношения.

 

Напомним, что основной характеристикой функции сложности алгоритма F(n) является ее скорость роста при n ® ¥. Для оценки и характеризации скорости роста функций сложности используется особый вид отношений на множестве функций - т.н. асимптотические отношения.

Q - отношение

Запись f(n) = Q(g(n)) означает, что $ c1, c2 Î R+ и $ n0Î N такие, что " n>n0 выполняется:

c1g(n) £ f(n) £ c2g(n). (1)

Если это так, будем говорить, что для функций f(n), g(n) выполнено асимптотическое
Q-отношение. Это можно понимать так: скорость роста f(n) не более, но и не менее скорости роста g(n) (скорость роста f(n) равна скорости роста g(n)). Функцию g(n) называют асимптотически точной оценкой скорости роста функции f(n).

Пример

Покажем, что . Требуется показать, что существуют c1, c2, n>no такие, что

или .

При c1 = 1/14, c2 = 1/2, n > 7 последнее выполняется.

 

Запись f(n) = Q(1) означает, что для f(n) выполняется

c1 £ f(n) £ c2.

А так как f(n) всегда не отрицательна и в качестве c1 можно выбрать 0, то последние неравенства переходят в такое:

f(n) £ c при n > no.

Запись Q(g(n)) можно понимать как обозначение множества (класса) функций f(n), для которых выполнено условие (1), тогда запись f(n) = Q(g(n)) говорит о принадлежности функции f(n) множеству (асимптотическому классу) Q(g(n)).

 

O, W - отношения

Запись f(n) = Q(g(n)) включает в себя две оценки: верхнюю и нижнюю. Можно рассматривать отдельно верхнюю и нижнюю оценки:

f(n) = O(g(n)) - верхняя, означает, что f(n) £ cg(n);

f(n) = W (g(n)) - нижняя, означает, что f(n) ³ cg(n).

Имеет место теорема:

Теорема 1

Для любых двух функций f(n) и g(n):

1) отношение f(n) = Q(g(n)) выполнено тогда, и только тогда, когда f(n) = O(g(n)) и
f(n) = W(g(n));

2) отношения f(n) = O(g(n)) и g(n) = W(f(n)) равносильны.

 

o, w - отношения

Запись f(n) = o(g(n)) означает, что имеет место f(n) = O(g(n)) и, кроме того,

.

Т.о. f(n) с ростом n растет медленнее, чем g(n).

Запись f(n) = w(g(n)) означает, что имеет место f(n) = W(g(n)) и, кроме того,

.

Это значит, что f(n) с ростом n растет быстрее, чем g(n).

 

Свойства асимптотических отношений

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

1. Транзитивность выполняется для всех рассматриваемых отношений. Например,

из f(n) = Q(g(n)) и g(n) = Q(h(n)) следует f(n) = Q(h(n)).

2. Рефлексивность выполняется только для Q, O, W: f(n) = Q(f(n)). Таким образом, для данных отношений асимптотический класс включает в себя порождающую функцию.

3. Симметричность выполняется только для Q: f(n) = Q(g(n)) Û g(n) = Q(f(n)).

4. f(n) = O(g(n)) и f(n) = W (g(n)) Û f(n) = Q(g(n)).

5. "с>0: Q(cg(n)) = Q(g(n)). То же самое и для O, W.

Доказательство

Будем доказывать следующее: "f(n): f(n) = Q(cg(n)) Þ f(n) = Q(g(n))

Пусть f(n) = Q(cg(n)), тогда $с12,n0: c1c g(n) £ f(n)) £ c2c g(n), что и доказывает необходимое.

6. Закон поглощения. Если g(n) имеет более высокую скорость роста, чем h(n), тогда скорость роста суммы g(n) + h(n) будет равна скорости роста g(n). Отсюда

Q(g(n) + h(n)) = Q(g(n)).

Такой же закон выполняется и всех остальных асимптотических отношений.

 

Сложность алгоритма

Сложность алгоритма характеризуют асимптотическим классом, к которому принадлежит его функция сложности. Например, говорят: "Сложность алгоритма А есть О(n3)". Асимптотический класс алгоритма определяет его категорию сложности. Примеры некоторых категорий сложности алгоритмов:

- алгоритмы полиномиальной сложности, F(n) = O(np);

- алгоритмы экспоненциальной сложности, F(n) = O(ea n);

- алгоритмы факториальной сложности, F(n) = O(n!).

Алгоритмы, имеющие полиномиальную функцию сложности математики называют эффективными.

 

 


1 | 2 | 3 | 4 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)