Смысл O-нотации

Помогите разобраться с O-нотацией. Насколько я понял:


O(h(n)) означает, что алгоритм ведет себя в наихудшем случает как c*h(n), начиная с какой-то величины n0, где c — константа.
Ω(h(n)) означает, что алгоритм ведет себя в наилучшем случае как
c*h(n), начиная с какой-то величины n0, где c — константа.
ο(h(n)) означает, что алгоритм ведет себя в наихудшем случае
«асимптотически лучше», чем c*h(n), начиная с какой-то величины n0, где c — константа.
ω(h(n)) означает, что алгоритм ведет себя в наилучшем случае
«асимптотически хуже», чем c*h(n), начиная с какой-то величины n0, где c — константа.


Не могу понять что означает Θ(h(n)), поясните пожалуйста. И если я ошибся в предыдущих определениях, поправьте пожалуйста.
    

Ответы

Ответ 1

Смотрите. Пусть f(n) — количество шагов алгоритма.

Сложность O(h(n)) означает, что алгоритм требует количества шагов, не большего, чем h(n), умноженное на какую-то константу. То есть, lim f(n)/h(n) при растущем n конечен.

Так вот, говорят, что f(n) = Θ(h(n)), если f(n) = O(h(n)) и одновременно h(n) = O(f(n)). Это значит, что функции f(n) и h(n) имеют как бы одинаковый порядок роста.



Пример: если настоящая сложность алгоритма f(n) = 2n^2 + 30n + log(n^4), то f(n
= O(n^2), т. к. 2n^2 + 30n + log(n^4) / n^2 = 2 + 30/n + 4 log n/n^2 -> 2 при бесконечно растущем n.

Но одновременно f(n) = O(n^100). Действительно, 2n^2 + 30n + log(n^4) / n^100 = 2/n^9
+ 30/n^99 + 4 log n/n^100 -> 0 при бесконечно растущем n. Видите? То есть, O(h(n)) есть как бы лишь верхняя оценка сложности алгоритма, как угодно грубая.

Далее: f(n) = Θ(n^2). Действительно, f(n) / h(n) -> 2 (как мы уже выясняли), а h(n) / f(n) очевидно стремится к 0.5.

С другой стороны, f(n) ≠ Θ(n^100), потому что n^100 / (2n^2 + 30n + log(n^4)) = n^9
* (n^2) / (2n^2 + 30n + log(n^4)) = n^98 * (1 / (2 + 30/n + 4 log n / n)), а этот предел расходится, т. к. знаменатель ограничен, а n^98 стремится к бесконечности.



Таким образом, Θ является более точной оценкой сложности алгоритма.



Примечание для математиков-пуристов: да, предел не обязательно существует, строго говоря, нужен lim sup.