Теория алгоритмов. Зюзысов В.М. - 55 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

(он может повлиять только на выбор констант c
1
и c
2
). Например, рассмотрим
квадратичную функцию f(n) = an
2
+ bn + c, где a, b и c – некоторые константы и a>0.
Отбрасывая члены младших порядков и коэффициент при старшем члене, находим, что
f(n) = Θ(n
2
). Чтобы убедиться в этом формально, можно положить c
1
= a/4, c
2
= 7a/4 и n
0
=
2×max(|b|/a,
ac /||
). Вообще, для любого полинома p(n) степени d с положительным
старшим коэффициентом имеем p(n) = Θ(n
d
).
Упомянем важный частный случай использования Θ-обозначений: Θ(1) обозначает
ограниченную функцию, отделенную от нуля некоторой положительной константой при
достаточно больших значениях аргумента.
O– и Ω-обозначения
Запись f(n) = Θ(g(n)) включает в себя две оценки: верхнюю и нижнюю. Их можно
разделить.
Если f(n) и g(n) – некоторые функции, то
• запись f(n) = Ο(g(n)) означает, что найдётся такая константа c > 0 и такое n
0
, что
f(n) ≤ cg(n) для всех n ≥ n
0
;
• запись f(n) = Ω(g(n)) означает, что найдётся такая константа c > 0 и такое n
0
, что
0 ≤ cg(n) ≤ f(n)для всех n ≥ n
0
.
Теорема 26.
1. Для любых двух функций f(n) и g(n) свойство f(n) = Θ(g(n)) выполнено тогда и только
тогда, когда f(n) = Ο(g(n)) и f(n) = Ω(g(n)).
2. Для любых двух функций f(n) и g(n) свойство f(n) = Ο(g(n
)) выполнено тогда и только
тогда, когда g(n) = Ω(f(n)).
Как мы видели, an
2
+ bn + c = Θ(n
2
) (при a>0). Поэтому an
2
+ bn + c = Ο(n
2
). Другой
пример: при a>0 можно записать an + b = Ο(n
2
) (положим c = a + |b| и n
0
= 1). Заметим, что
в этом случае an + b ≠ Ω(n
2
) и an + b ≠ Θ(n
2
).
Работая с символами Ο, Θ и Ω мы имеем дело с односторонними равенствами – эти
символы могут стоять только справа от знака =.
Введенные нами определения обладают некоторыми свойствами транзитивности,
рефлексивности и симметричности.
Транзитивность
f(n) = Θ(g(n)) и g(n) = Θ(h(n)) влечет f(n) = Θ(h(n)).
f(n) = Ο(g(n)) и g(n) = Ο(h(n)) влечет f(n) = Ο(h(n)).
f(n) = Ω(g(n)) и g(n) = Ω(h(n)) влечет f(n) = Ω(h(n)).
Рефлексивность
f(n) = Θ(f(n)), f(n) = Ο(f(n)), f(n) = Ω(f(n))
Симметричность
f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n))

Страницы