В чем разница между Θ (n) и O (n)?

Question

Иногда я вижу Θ (n) со странным символом with с чем-то посередине, а иногда просто O (n). Это просто лень печатать, потому что никто не знает, как печатать этот символ, или это означает что-то другое?

Answer 1

Краткое объяснение:

Если алгоритм имеет Θ (g (n)), это означает, что время выполнения алгоритма при увеличении n (входного размера) пропорционально g (n).

Если алгоритм имеет значение O (g (n)), это означает, что время выполнения алгоритма при увеличении n равно не более пропорционально g (n).

Обычно, даже когда люди говорят о O (g (n)), они на самом деле означают Θ (g (n)), но технически есть разница.

<ч />

Более технически:

O (n) представляет верхнюю границу. Θ (n) означает тесную связь. Ω (n) представляет нижнюю границу.

f (x) = Θ (g (x)) тогда и только тогда, когда f (x) = O (g (x)) и f (x) = Ω (g (x))

В основном, когда мы говорим, что алгоритм имеет O (n), это также O (n ² ), O (n ^1000000 ), O (2 ^{n *) 1028 *), ... но алгоритм Θ (n) равен , а не Θ (n 2 ).}

Фактически, поскольку f (n) = Θ (g (n)) означает, что для достаточно больших значений n, f (n) может быть ограничено в пределах c ₁ g (n) и c ₂ g (n) для некоторых значений c ₁ и c ₂ , т.е. скорость роста f асимптотически равна g: g может быть нижней границей и и верхняя граница f. Это непосредственно означает, что f может быть как нижней, так и верхней границей g. Следовательно,

f (x) = Θ (g (x)) тогда и только тогда, когда g (x) = Θ (f (x))

Точно так же, чтобы показать f (n) = Θ (g (n)), достаточно показать, что g является верхней границей f (т. Е. F (n) = O (g (n))), а f является нижняя граница g (т. е. f (n) = Ω (g (n)), что точно так же, как g (n) = O (f (n))). Лаконично,

f (x) = Θ (g (x)) тогда и только тогда, когда f (x) = O (g (x)) и g (x) = O (f (x))

---

Существуют также нотации о-о и-омега (ω), представляющие свободные верхние и нижние нижние границы функции.

Подведем итог:

f(x) = O(g(x)) (big-oh) означает, что скорость роста f(x) составляет асимптотически меньше или равно до до темпов роста g(x).

f(x) = Ω(g(x)) (биг-омега) означает что темпы роста f(x) асимптотически больше или равен темпу прироста g(x)

f(x) = o(g(x)) (мало-ой) означает, что скорость роста f(x) составляет асимптотически меньше темпы роста g(x).

f(x) = ω(g(x)) (мало-омега) означает что темпы роста f(x) асимптотически больше скорость роста g(x)

f(x) = Θ(g(x)) (тета) означает, что скорость роста f(x) составляет асимптотически равен темпы роста g(x)

Для более подробного обсуждения вы можете прочитать определение в Википедии или обратиться к классическому учебнику, например, «Введение в алгоритмы» Кормена и др.

Answer 2

Есть простой способ (уловка, я полагаю), чтобы запомнить, какая запись означает, что.

Все обозначения Big-O могут считаться столбцом.

При взгляде на Ω столбец находится внизу, поэтому он является (асимптотическим) нижней границей.

Когда вы смотрите на Θ, планка явно посередине. Так что это (асимптотическая) жесткая граница.

Когда почерк O, вы обычно заканчиваете вверху и рисуете загогулины. Следовательно, O (n) является верхней границей функции. Чтобы быть справедливым, этот не работает с большинством шрифтов, но это оригинальное обоснование имен.

Answer 3

один большой "O"

одна большая тета

http://en.wikipedia.org/wiki/Big_O_notation

Большой O означает, что ваш алгоритм будет выполняться не более, чем в заданном выражении (n ^ 2)

Большая Омега означает, что ваш алгоритм будет выполняться не менее, чем в заданном выражении (n ^ 2)

Когда оба условия выполняются для одного и того же выражения, вы можете использовать большую тета-нотацию ...

Answer 4

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

Предположим, что время выполнения f(i) равно O(1). Ниже приведен фрагмент кода с асимптотическим временем выполнения Θ(n). всегда вызывает функцию f(...) n раз. Нижняя и верхняя границы равны n.

for(int i=0; i<n; i++){
    f(i);
}

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

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}

Answer 5

A диаграмма может облегчить понимание предыдущих ответов:

Θ-нотация - тот же порядок | O-обозначение - верхняя граница

На английском

Слева обратите внимание, что есть верхняя граница и нижняя граница, которые имеют одинаковый порядок величины (т. Е. g (n) ). Игнорируйте константы, и если верхняя граница и нижняя граница имеют одинаковый порядок величины, можно с уверенностью сказать, что f (n) = Θ (g (n)) или f (n) равно в большой тэте г (н) .

Начиная с правого, более простого примера, он говорит, что верхняя граница g (n) - это просто порядок величины и игнорирует постоянную c (как и все *) 1025 * большое обозначение O делает).

Answer 6

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

Таким образом, если кто-то заявляет The Theta is expression q, то они также обязательно заявляют, что Big O is expression q и Omega is expression q.

---

Грубая аналогия:

Если: Тета утверждает: «У этого животного 5 ног». тогда следует, что: Большой O истинен («У этого животного меньше или равно 5 ногам».) а также Омега верна («У этого животного больше или равно 5 ног».)

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

Answer 7

f(n) принадлежит O(n), если существует положительное значение k как f(n)<=k*n

f(n) принадлежит Θ(n), если существует положительное значение k1, k2 как k1*n<=f(n)<=k2*n

Статья в Википедии о системе обозначений Big O

Answer 8

Вывод: мы рассматриваем большие O, большие θ и большие Ω как одно и то же.

Почему? Я расскажу причину ниже:

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

Чтобы четко объяснить связь между большим O и большим θ, сначала я объясню связь между большим O и малым o. Из определения мы можем легко узнать, что small o - это подмножество больших O. Например:

T (n) = n ^ 2 + n, можно сказать, T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (п ^ 4). Но для малых o T (n) = o (n ^ 2) не соответствует определению малых o. Так что просто T (n) = o (n ^ 3), T (n) = o (n ^ 4) верны для малого o. Избыточный T (n) = O (n ^ 2) это что? Это большой θ!

Как правило, мы говорим, что большой O - это O (n ^ 2), вряд ли T (n) = O (n ^ 3), T (n) = O (n ^ 4). Зачем? Потому что мы подсознательно считаем большой О большим θ.

Точно так же мы подсознательно рассматриваем большие Ω как большие θ.

Одним словом, большие O, большие θ и большие Ω - это не одно и то же из определений, но это одно и то же в нашем рту и мозге.

Answer 9

Использование лимитов

Давайте рассмотрим f(n) > 0 и g(n) > 0 для всех n. Это нормально, потому что самый быстрый реальный алгоритм имеет хотя бы одну операцию и завершает свое выполнение после запуска. Это упростит исчисление, потому что мы можем использовать значение (f(n)) вместо абсолютного значения (|f(n)|).

1. f(n) = O(g(n))

   Общие сведения:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞   g(n)
   

   Для g(n) = n:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞    n
   

   Примеры:

       Expression               Value of the limit
   ------------------------------------------------
   n        = O(n)                      1
   1/2*n    = O(n)                     1/2
   2*n      = O(n)                      2
   n+log(n) = O(n)                      1
   n        = O(n*log(n))               0
   n        = O(n²)                     0
   n        = O(nⁿ)                     0
   

   Контрпримеры:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ O(log(n))                 ∞
   1/2*n    ≠ O(sqrt(n))                ∞
   2*n      ≠ O(1)                      ∞
   n+log(n) ≠ O(log(n))                 ∞
   

2. f(n) = Θ(g(n))

   Общие сведения:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞   g(n)
   

   Для g(n) = n:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞    n
   

   Примеры:

       Expression               Value of the limit
   ------------------------------------------------
   n        = Θ(n)                      1
   1/2*n    = Θ(n)                     1/2
   2*n      = Θ(n)                      2
   n+log(n) = Θ(n)                      1
   

   Контрпримеры:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ Θ(log(n))                 ∞
   1/2*n    ≠ Θ(sqrt(n))                ∞
   2*n      ≠ Θ(1)                      ∞
   n+log(n) ≠ Θ(log(n))                 ∞
   n        ≠ Θ(n*log(n))               0
   n        ≠ Θ(n²)                     0
   n        ≠ Θ(nⁿ)                     0