Разница между нотациями Big-Theta и Big O на простом языке

Большой O дает только верхнюю асимптотическую границу, в то время как большой Theta также дает нижнюю границу.

Все, что Theta(f(n)), также является O(f(n)), но не наоборот.
T(n) называется Theta(f(n)), если одновременно O(f(n)) и Omega(f(n))

По этой причине нотация big-Theta более информативна, чем нотация big-O, поэтому, если мы можем сказать, что что-то является big-Theta, обычно это предпочтительнее. Однако доказать, что что-то является большим Тета, труднее, чем доказать, что это большое О.

Например, пример, сортировка слиянием имеет одновременно O(n*log(n)) и Theta(n*log(n)), но также O(n²), так как n² асимптотически "больше" его. Однако это НЕ тета (n²), поскольку алгоритм НЕ является омега (n²).

Omega(n) — это асимптотическая нижняя граница. Если T(n) равно Omega(f(n)), это означает, что из определенного n0 существует константа C1 такая, что T(n) >= C1 * f(n). В то время как big-O говорит, что существует константа C2 такая, что T(n) <= C2 * f(n)).

Все три (Omega, O, Theta) дают только асимптотическую информацию ("для больших входных данных"):

• Большой O дает верхнюю границу
• Большая Омега дает нижнюю границу и
• Big Theta дает как нижнюю, так и верхнюю границу

Обратите внимание, что это обозначение не связано с анализом алгоритмов в наилучшем, наихудшем и среднем случаях. Каждый из них может быть применен к каждому анализу.

Я просто приведу цитату из TAOCP Кнута, том 1 — стр. 110 (у меня есть индийское издание). Я рекомендую прочитать страницы 107-110 (раздел 1.2.11 Асимптотические представления)

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

На странице 107,

1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 = O (n ^ 4) и

1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 = O (n ^ 3) и

1^2 + 2^2 + 3^2 + ... + n^2 = (1/3) n^3 + O(n^2)

Big-Oh для приближений. Это позволяет вам заменить ~ на знак равенства =. В приведенном выше примере для очень большого n мы можем быть уверены, что количество останется ниже n ^ 4 и n ^ 3 и (1/3) n ^ 3 + n ^ 2 [а не просто n ^ 2]

Большая омега предназначена для нижних границ. Алгоритм с омега (n ^ 2) будет не таким эффективным, как алгоритм с O (N logN) для больших N. Однако мы не знаем, при каких значениях N (в этом смысле мы знаем примерно)

Большая тета предназначена для точного порядка роста, как нижней, так и верхней границы.

Если время выполнения выражено в виде большого O, вы знаете, что время выполнения не будет медленнее заданного выражения. Он выражает наихудший сценарий.

Но с тета-нотацией вы также знаете, что это не будет быстрее. То есть не существует наилучшего сценария, при котором алгоритм будет перестраиваться быстрее.

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

Вот моя попытка:

Функция f(n) есть O(n) тогда и только тогда, когда существует константа c, такая что f(n) <= c*g(n).

Используя это определение, можем ли мы сказать, что функция f(2^(n+1)) есть O(2^n)?

1. Другими словами, существует ли константа 'c' такая, что 2^(n+1) <= c*(2^n)? Обратите внимание, что вторая функция (2^n) — это функция после большой O в приведенной выше задаче. Меня это сначала смутило.

2. Итак, тогда используйте свои базовые навыки алгебры, чтобы упростить это уравнение. 2^(n+1) разбивается на 2 * 2^n. При этом у нас остается:

   2 * 2^n <= c(2^n)

3. Теперь все просто, уравнение выполняется для любого значения c, где c >= 2. Итак, да, мы можем сказать, что f(2^(n+1)) это O(2^n).

Big Omega работает так же, за исключением того, что она оценивает f(n) >= c*g(n) для некоторой константы 'c'.

Итак, упростив вышеуказанные функции таким же образом, у нас осталось (обратите внимание на >= сейчас):

2 * 2^n >= c(2^n)

Итак, уравнение работает для диапазона 0 <= c <= 2. Итак, мы можем сказать, что f(2^(n+1)) — это Большая Омега (2^n).

Теперь, поскольку ОБЕ из них выполняются, мы можем сказать, что это функция Big Theta (2^n). Если один из них не будет работать для константы 'c', то это не Big Theta.

Приведенный выше пример был взят из «Руководства по проектированию алгоритмов» Скиены, фантастической книги.

Надеюсь, это поможет. Это действительно сложная концепция для упрощения. Не зацикливайтесь на том, что такое 'c', просто разбейте его на более простые термины и используйте свои базовые навыки алгебры.

Я собираюсь использовать пример, чтобы проиллюстрировать разницу.

Пусть функция f(n) определена как

if n is odd f(n) = n^3
if n is even f(n) = n^2

Из CLRS

Функция f(n) принадлежит множеству Θ(g(n)), если существуют положительные константы c1 и c2 такие, что ее можно «зажать» между c1g(n) и c2g(n) при достаточно больших n.

И

O(g(n)) = {f(n): существуют положительные константы c и n0 такие, что 0 ≤ f(n) ≤ cg(n) для всех n ≥ n0}.

И

Ω(g(n)) = {f(n): существуют положительные константы c и n0 такие, что 0 ⩽ cg(n) ⩽ f(n) для всех n ⩾ n0}.

Верхняя граница f(n) равна n^3. Итак, наша функция f(n) явно равна O(n^3).

Но это Θ (n ^ 3)?

Чтобы f(n) находилась в Θ(n^3), она должна быть зажата между двумя функциями, одна из которых образует нижнюю границу, а другая — верхнюю границу, обе из которых выросли при n^3. В то время как верхняя граница очевидна, нижняя граница не может быть n ^ 3. Нижняя граница на самом деле n ^ 2; f(n) равно Ω(n^2)

Из CLRS

Для любых двух функций f(n) и g(n) имеем f(n) = Θ(g(n)) тогда и только тогда, когда f(n) = O(g(n)) и f(n) = Ω(g(n)).

Следовательно, f (n) не находится в Θ (n ^ 3), а находится в O (n ^ 3) и Ω (n ^ 2)

На очень простом языке разница будет такой:

Обозначение Big O используется для анализа алгоритма в наихудшем случае. Big Omega используется для анализа алгоритма в наилучшем случае. Big Theta используется для анализа алгоритма, когда анализ наилучшего и наихудшего случаев одинаков.

Допустим, вы ищете число в отсортированном массиве, используя алгоритм двоичного поиска.

[1 2 3 4 5 6 7] 

В худшем случае, например, когда целью является 1, он должен выполнить log(n) разделенных проверок, что в нашем случае составляет log(7). Это может быть выражено как O (n).

В лучшем случае, например, когда цель равна 3, выполняется только одна операция. Его можно выразить как Ω(1)