При попытке понять разницу между обозначениями Thetastrong > и O я столкнулся с следующим утверждением:
The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.
Но я этого не понимаю. Книга объясняет это математически, но она слишком сложна и становится очень скучной для чтения, когда я действительно не понимаю.
Может ли кто-нибудь объяснить разницу между двумя, используя простые, но мощные примеры.
Большой О дает только верхнюю асимптотическую границу, в то время как большая Тета также дает нижнюю границу.
Все, что есть 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 2), поскольку n 2 асимптотически "больше", чем Это. Однако это НЕ Тета (n 2), поскольку алгоритм НЕ является Омегой (n 2).
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) дают только асимптотическую информацию ("для большого ввода"):
Обратите внимание, что эта нотация не связана с анализом алгоритмов наилучшего, наихудшего и среднего случаев. Каждый из них может быть применен к каждому анализу.
Я просто приведу цитату из Knuth TAOCP Volume 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 ^ 4 и n ^ 3 и (1/3) n ^ 3 + n ^ 2 [а не просто n ^ 2]
Большая Омега для нижних границ. Алгоритм с Omega (n ^ 2) не будет столь же эффективным, как один с O (N logN) при больших N. Однако мы не знаем, при каких значениях N (в том смысл, который мы знаем примерно)
Большая тэта предназначена для точного порядка роста, как нижней, так и верхней.
Здесь моя попытка:
Функция f(n) равна O(n), тогда и только тогда, когда существует константа c, такая, что f(n) <= c*g(n).
Используя это определение, можем ли мы сказать, что функция f(2^(n+1)) равна O(2^n)?
Другими словами, существует ли константа 'c' такая, что 2^(n+1) <= c*(2^n)? Обратите внимание, что вторая функция (2^n) - это функция после Big O в указанной выше проблеме. Сначала это смутило меня.
Итак, используйте ваши базовые навыки алгебры, чтобы упростить это уравнение. 2^(n+1) разбивается на 2 * 2^n. Для этого у нас осталось:
2 * 2^n <= c(2^n)
Теперь его легко, уравнение выполняется для любого значения c, где c >= 2. Итак, да, мы можем сказать, что f(2^(n+1)) - O(2^n).
Big Omega работает одинаково, за исключением того, что для некоторой константы 'c' она вычисляет f(n) > = c*g(n).
Итак, упрощая вышеуказанные функции одинаково, мы остаемся с (обратите внимание нa >= сейчас):
2 * 2^n >= c(2^n)
Итак, уравнение работает для диапазона 0 <= c <= 2. Итак, мы можем сказать, что f(2^(n+1)) - большая омега (2^n).
Теперь, поскольку BOTH тех, что удержаны, мы можем сказать, что функция Big Theta (2^n). Если один из них не будет работать для константы 'c', то его не большая тэта.
Приведенный выше пример был взят из Руководства по разработке алгоритма, которое является фантастической книгой.
Надеюсь, что это поможет. Это действительно сложная концепция для упрощения. Не зацикливайтесь на том, что 'c', просто сложите его на более простые термины и используйте свои основные навыки алгебры.
Если время выполнения выражается в нотации Big-O, вы знаете, что время выполнения не будет медленнее, чем данное выражение. Он выражает наихудший сценарий.
Но с обозначением Тэта вы также знали, что это будет не быстрее. То есть, нет лучшего сценария, когда алгоритм будет перенастраиваться быстрее.
Это дает более точную привязку к ожидаемому времени работы. Однако для большинства целей проще игнорировать нижнюю границу (возможность более быстрого выполнения), в то время как вы, как правило, обеспокоены наихудшим сценарием.
Я собираюсь использовать пример, чтобы проиллюстрировать разницу.
Пусть функция 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 используется для лучшего анализа алгоритма. Большая тэта используется для анализа алгоритма, когда анализ наилучшего и наихудшего случаев совпадает.
Допустим, вы ищете число в отсортированном массиве, используя алгоритм двоичного поиска.
[1 2 3 4 5 6 7]
В худшем случае, например, когда целью является 1, он должен выполнить log (n) разделенных проверок, что в нашем случае - log (7). Это может быть выражено как O (n).
В лучшем случае, например, когда цель равна 3, она выполняет только одну операцию. Это можно выразить как Ω (1)