В чем разница между O, Ω и Θ?

Question

Я изучаю алгоритм анализа. У меня проблемы с пониманием разницы между 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, Ω или Θ; почему не все три?

Answer 1

Важно помнить, что обозначения, будь то O, Ω или Θ, выражают асимптотический рост функции ; он не имеет ничего общего с алгоритмами как таковыми . Рассматриваемая функция может быть "сложностью" (временем выполнения) алгоритма, наихудшего, наилучшего или среднего случая, но запись не зависит от того, откуда взялась функция.

Например, функция f (n) = 3n ² + 5 равна:

• O (n ² ), это также O (n ² log n), O (n ³ ), O (n ^{) 4} ) и т. Д., Но не O (n).
• Ω (n ² ), это также Ω (n log n), Ω (n) и т. Д., Но не Ω (n ³ ).
• Θ (п ² ). Это даже не Θ (n ² log n) или Θ (n ² / log n).

Теперь обычно рассматриваемая функция представляет собой сложность алгоритма в худшем случае, и то, какое обозначение из трех используется, зависит от того, что мы хотим сказать об этом, и от того, насколько тщательно мы проводим анализ. Например, мы можем наблюдать, что, поскольку есть два вложенных цикла, время выполнения в худшем случае составляет самое большее O (n ² ), не заботясь о том, действительно ли это достигается для некоторый вклад. (Обычно очевидно, что это так.) Или, мы можем сказать, что наихудшее время выполнения сортировки - это Ω (n log n), потому что должны быть некоторые входы, для которых должно быть не менее cn (log n) шаги. Или мы можем взглянуть на конкретный алгоритм сортировки слиянием и увидеть, что в худшем случае и требуется не более O (n log n) шагов, что при некотором вводе он делает n log n шагов, поэтому наихудшее время выполнения Θ (n log n).

Обратите внимание, что во всех трех приведенных выше примерах анализировалось все то же время (в худшем случае). Вместо этого мы можем проанализировать наилучший или средний случай, но опять-таки, какое обозначение из трех мы используем, зависит от того, что мы хотим сказать - хотим ли мы дать верхнюю границу, нижнюю границу или жесткую границу порядка рост та же функция .

Answer 2

Θ обозначает асимптотически плотную верхнюю и нижнюю границу.

O обозначает верхнюю границу, но эта граница может быть или не быть жесткой.
o обозначает верхнюю границу, которая не является жесткой.

Ω обозначает нижнюю границу, но эта граница может быть или не быть жесткой.
ω обозначает нижнюю границу, которая не является жесткой.

Answer 3

О том, что означают эти три, см. Ответ Can Berk Güder.

Обратите внимание, что они не имеют ничего общего с лучшим случаем, наихудшим случаем и средним случаем. Например, сортировка по пузырькам - это best (n) лучший случай (потому что если данные уже отсортированы, требуется только n-1 сравнение), и Θ (n ^ 2) наихудший случай. Это Θ (n ^ 2) средний случай, предполагающий случайный случайный ввод. Таким образом, этот средний случай также является O (n ^ 2), O (n ^ 3) и O (2 ^ n).

Итак, O, Θ и Ω говорят вам, что это за граница. Они не говорят вам, на что ограничен предел. В контексте это может быть ограничение на лучший случай, наихудший случай, средний случай или алгоритм в целом (все случаи).

Конечно, если алгоритм имеет Ω (g) лучший случай, то он сам является Ω (g). Если он имеет O (g), то в худшем случае это O (g). Так что здесь есть связь. Но если он имеет среднее значение g (g), это почти ничего не говорит о лучших и худших случаях.

Что касается "почему не все три?".

Если ваша функция Θ (g), то это также O (g) и Ω (g). Так что нет смысла предоставлять другие границы наряду с Θ границей.

Когда вы видите одного из других в одиночку, это обычно потому, что мы заботимся только о верхней границе, или мы заботимся только о нижней границе. Таким образом, мы говорим, что все виды сравнения обязательно являются Ω (n log n) наихудшим случаем, и что пузырьковая сортировка является O (n ^ 2) наихудшим случаем, но O (n) лучшим, потому что мы не пытаемся полностью описать время сложности, мы просто выражаем границы, о которых мы заботимся в определенном контексте.

И в любом случае большинство людей кажутся ленивыми и не хотят печатать греческие буквы. Я знаю, что я есть. Так что мы просто говорим, что сортировки сравнения "в лучшем случае O (n log n)". На самом деле это злоупотребление нотацией, но оно дает понять смысл.

Answer 4

Вот некоторые из ресурсов, которые действительно помогут вам:

• Википедии
• Wiki book
• Видео лекции MIT
• Видео с IITB, Индия

Answer 5

Нотация Big-O часто упоминается как сложность алгоритма, потому что она убеждает нас, что алгоритм не будет работать существенно хуже при больших n. Однако, как справедливо указывалось ранее, Big-O дает нам асимптотическую оценку, и наш алгоритм может вести себя по-разному, когда задан определенный вход. Например, быстрая сортировка может быть O (n ^ 2), когда массив уже отсортирован. OTOH, асимптотическая ситуация может быть улучшена на практике с аккуратной реализацией.