О – символика

Вообще в общем случае 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².