Каково различие между O, Ω, и Θ?
Я изучаю анализ алгоритма. Я испытываю затруднения при понимании различия между O, Ω, и Θ.
Путем они определяются, следующие:
f(n) = O(g(n))средстваc · g(n)верхняя граница наf(n). Таким образом там существует некоторая константаcтаким образом, чтоf(n)всегда ≤c · g(n), для достаточно большогоn(т.е.n ≥ n0для некоторой константыn0).f(n) = Ω(g(n))средстваc · g(n)нижняя граница наf(n). Таким образом там существует некоторая константаcтаким образом, чтоf(n)всегда ≥c · g(n), для всехn ≥ n0.f(n) = Θ(g(n))средстваc1 · g(n)верхняя граница наf(n)иc2 · g(n)нижняя граница наf(n), для всехn ≥ n0. Таким образом там существуйте константыc1иc2таким образом, чтоf(n) ≤ c1 ·g(n)иf(n) ≥ c2 ·g(n). Это означает этоg(n)обеспечивает хорошее, привязанное трудноеf(n).
Путем я понял, что это:
O(f(n))дает худшую сложность случая заданной функции / алгоритм.Ω(f(n))дает лучшую сложность случая заданной функции / алгоритм.Θ(f(n))дает среднюю сложность случая заданной функции / алгоритм.
Исправьте меня, если я неправ. Если это имеет место, временная сложность каждого алгоритма должна быть выражена во всех трех нотациях. Но я заметил, что это выражается или как O, Ω, или как Θ; почему не все три?
5 ответов
Важно помнить, что нотация, будь то O, Ω или Θ, выражает асимптотический рост функции ; по своей природе она не имеет ничего общего с алгоритмами как таковыми . Функция, о которой идет речь, может быть "сложностью" (временем выполнения) алгоритма, либо наихудшим, лучшим, либо средним случаем, но при этом нотация не зависит от того, откуда взялась эта функция. Например, функция f(n)=3n2+5 является:
- O(n2), она также является O(n2log n), O(n3), O(n4) и т.д., но не является O(n).
- Ω(n2), это также Ω(n log n), Ω(n) и т.д., но не Ω(n3).
- Θ(n2). Это даже не Θ(n2log n) и не Θ(n2/log n).
Now, Обычно рассматриваемая функция является наихудшей сложностью алгоритма, и какая из трех нотаций используется, зависит от того, что мы хотим о ней сказать, и от того, насколько тщательно мы выполняем анализ. Например, можно заметить, что из-за наличия двух вложенных циклов наихудшим случаем выполнения является O(n2), не заботясь о том, достигается ли это на самом деле для какого-то входа. (Обычно это очевидно.) Или, можно сказать, что наихудшее время сортировки - Ω(n log n), потому что должно быть несколько входов, для которых нужно выполнить хотя бы cn(log n) шагов. Или, мы можем посмотреть на конкретный алгоритм слияния и увидеть, что в наихудшем случае он делает большинство шагов O(n log n) и , что некоторые входы заставляют его делать n шагов log n, так что наихудшее время сортировки - Θ(n log n).
Обратите внимание, что во всех трех вышеприведенных примерах все равно было проанализировано одно и то же (наихудшее) время работы. Вместо этого мы можем проанализировать лучший или средний случай, но опять же, какая нотация из трех, которые мы используем, зависит от того, что мы хотим сказать - хотим ли мы дать верхнюю, нижнюю границу, или жесткую границу по порядку роста той же функции .
.Θ обозначает асимптотически плотную верхнюю и нижнюю границу.
O обозначает верхнюю границу, но эта граница может быть или не быть плотной.
.
o обозначает верхнюю границу, которая не является узкой.
Ω означает нижний предел, но этот предел может быть, а может и не быть жестким.
ω обозначает нижнюю границу, которая не является узкой.
Вот некоторые из ресурсов, которые действительно помогут вам:
О том, что означают эти трое, см. ответ Кан Берка Гюдера.
Заметьте также, что они вообще не имеют никакого отношения к лучшему, худшему и среднему случаю. Сортировкой пузырьков, например, является Θ(n) best case (потому что если данные уже отсортированы, то нужны только n-1 сравнения), и Θ(n^2) worst case. Это средний случай Θ(n^2) в предположении случайно перепутанных входных данных. Следовательно, этот средний случай также O(n^2), и O(n^3), и O(2^n).
Итак, O, Θ и Ω говорят о том, какая это привязка. Они не говорят вам, что такое ограничение. В контексте, это может быть лимит на лучший случай, худший случай, средний случай, или алгоритм в целом (все случаи).
Конечно, если алгоритм имеет Ω(g) лучший случай, то он сам по себе Ω(g). Если он имеет O(g) наихудший случай, то это O(g). Таким образом, там есть связь. Но если у него есть средний регистр Θ(g), то это почти ничего не говорит о лучших и худших случаях.
Что касается "почему бы не все три?".
Если ваша функция имеет Θ(g), то это также O(g) и Ω(g). Так что нет особого смысла предоставлять другие границы наряду с границей Θ.
Когда вы видите одну из других, это обычно потому, что мы заботимся только о верхней границе, или мы заботимся только о нижней. Так что мы говорим, что все виды сравнения обязательно являются худшим случаем Ω(n log n), и этот вид пузырьков - худший случай O(n^2), но лучший случай O(n), потому что мы не пытаемся полностью описать временную сложность, мы просто выражаем те границы, которые нас волнуют в конкретном контексте.
И в любом случае большинство людей кажутся ленивыми и не хотят печатать греческие буквы. Я знаю, что так и есть. Так что мы просто говорим, что сравнительные сорта - это "в лучшем случае O(n log n)". На самом деле, это злоупотребление нотацией, но это все меняет.
Большую нотацию часто называют сложностью алгоритма, так как она уверяет нас, что алгоритм не будет работать значительно хуже для большого n. Однако, как было справедливо отмечено ранее, Big-O дает нам асимптотическую оценку, и наш алгоритм может вести себя по-другому, когда задан определенный вход. Например, быстрой сортировкой может быть O(n^2), когда массив уже отсортирован. OTOH, асимптотическую ситуацию на практике можно улучшить аккуратной реализацией
.