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

Введем понятия функции роста числа трудоемкости выполнения алгоритма f(N), тогда: пусть все функции времени выполнения определенны на множестве не отрицательных целых чисел ≥ 0.

Время выполнения T(N) имеет порядок O(f(N)), если существует const C и такое Nо > 0 при любом N≥ nо величина C*f(N) ≥ T(n), т.е. для алгоритмов имеет порядок O(f(N)) вследствие того, что они имеют порядок или степень роста f(N).

«O(f(N))» запись представлена в «О» символике, в которой показываются характер изменения функции роста.

Пример: пусть мы смогли определить T(0) = 1, Т(1) = 4 величины или в общем случае T(n) = (n + 1)². Требуется найти асимптотическую оценку, т.е. некоторую функцию вида C(f).

T(n) = (n + 1)² = n² + 2n + 1

В качестве f(n) можно взять функцию вида f ’(N) = n³.

2n² ≥ n² + 2n + 1

C = 2 → nо = 3; C = 3 → nо = 2; C = 4 → nо = 1

В качестве асимптотической оценки, т.е. функции расположенной над T(n) можно взять функцию f(n) = n² однако тем самым мы ухудшим «мнение» эксперта о алгоритме (он работает быстрее). Если предположить что f(N) = n², то T(n) ≤ n² * C будет выполняться при С = 2, начиная с nо = 3, исключая коды длиной 1-2, более правильно положить С = 4, тогда nо = 1, тогда “O(f(n))” = n².

О – символика

Вообще в общем случае T(n) как функцию времени задать нельзя аналитически. Единственный выход – найти верхнюю и нижнюю асимптотическую оценку характера изменения T(n). Для чего вводиться функция Ω(f(n)) – омега, которая представляет нижнюю асимптотику. Можно подобрать такое значение функции роста для О и Ω, что они совпадут, тогда получим точную асимптотическую оценку функции T(n). Функция y(n) = Ө(g(n)), то говорят что g(n) является точной асимптотической оценкой для функции y(n). Если y(n) = Ө(g(n)) → g(n) = Ө(y(n)). Запись y(n) включает в себя 2 оценки верхнюю и нижнюю, т.е. C1f(n) ≤ Ө(n) ≤ C2f(n). Для нашего случая n², C1*n² ≤ n² + 2n + 1 ≤ C2 * n² на всем интервале n>no. Следовательно, f(n) = n² есть асимптотически точная оценка T(n) = Ө(n²). Говорят y(n) = Ω(g(n)), если найдется такая константа С > 0 и no, что О ≤ С*g(n) ≤ y(n) для всех n ≥ 0 теорема: для любых двух функций y(n) и g(n) свойства y(n) = Ө(g(n)) выполняется тогда и только тогда, когда следует, что y(n) = О(g(n)), g(n) = Ω (y(n)) следует, что любые две функции y(n) и g(n) по свойствам равносильны.

Обозначение - Ө, Ω, О: часто используются в формулах. Например, T(n + 1) = T(n) + Ө(n²) в рекуррентной формуле это обозначение означает, что время увеличивается при изменение длины аргумента пропорционально n², а в алгоритме этому члену выражения соответствует фрагмент асимптотическим выражениям, которые имеют n².

O и W – обозначения

y(n) = О(g(n)) означает, что отношение с ростом n является ограниченным, к тому же если

lim n→∞(y(n))/(g(n)) = 0, то записывается y(n) = О(g(n)), т.е. y(n) и g(n), если для всякого ε найдется такое no, О ≤ y(n) ≤ ε*g(n).

2n = O(n²), но 2n² ≠ О(n²)

lim n→∞(2n)/ n² = 0 lim n→∞(2n)/ n² = 2 ≠ 0

Найдется такое no, что O ≤ C*g(n) ≤ y(n), n²/2 = W(n) W/2 = W(n²) выполняются следующие свойства:

1. Транзитивный

y(n) = Ө(g(n)) и g(n) = Ө(h(n)), то y(n) = Ө(h(n))

O O O

Ω Ω Ω

O O O

W W W

2. Рефлексивность (отражение)

y(n) = Ө(y(n))

y(n) = O(y(n))

y(n) = Ω(y(n))

3. Симметричность

y(n) = (g(n)) ↔ g(n ) = Ө(y(n))

4. Обратимость(обращение)

y(n) = O(y(n)), если и только если g(n) = Ω(y(n)) g(n) = W(y(n))

5.

Пусть a = y(n), b = g(n):

y(n) = O(g(n)) a ≤ b

y(n) = Ω(g(n)) a ≥ b

y(n) = Ө(g(n)) a = b

y(n) = o(g(n)) a < b

y(n) = W(g(n)) a > b