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

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

Q - отношение

Запись f(n) = Q(g(n)) означает, что $ c₁, c₂ Î R⁺ и $ n₀Î N такие, что " n>n₀ выполняется:

c₁g(n) £ f(n) £ c₂g(n). (1)

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

Пример

Покажем, что . Требуется показать, что существуют c₁, c₂, n>n_o такие, что

или .

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

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

c₁ £ f(n) £ c₂.

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

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

Запись 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)), тогда $с₁,с₂,n₀: c₁c g(n) £ f(n)) £ c₂c g(n), что и доказывает необходимое.

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

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

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

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

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

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

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

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

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

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