Смысл O-нотации
1,00
р.
Помогите разобраться с 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)), поясните пожалуйста. И если я ошибся в предыдущих определениях, поправьте пожалуйста.
Ответ
Смотрите. Пусть 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.
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)), поясните пожалуйста. И если я ошибся в предыдущих определениях, поправьте пожалуйста.
Ответ
Смотрите. Пусть 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.
