25

Помогите разобраться с 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

1 ответ 1

16

Смотрите. Пусть 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^98 + 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^98 * (n^2) / (2n^2 + 30n + log(n^4)) = n^98 * (1 / (2 + 30/n + 4 log n / n)), а этот предел расходится, т. к. знаменатель ограничен, а n^98 стремится к бесконечности.


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


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

2
  • выходит что разница между O(h(n)) и ο(h(n)) в том что ο(h(n)) всегда грубая "оценка сверху" а O(h(n)) может совпадать с "точной" ?
    – NEvOl
    Commented 25 июн. 2016 в 19:29
  • @SergeyNikolaev: Так и есть, да.
    – VladD
    Commented 25 июн. 2016 в 22:11

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.