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

Question

Иногда я вижу Θ (n) со странным символом Θ с чем-то в середине, а иногда просто 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) является не Θ(n²).

Фактически, поскольку f(n) = Θ(g(n)) означает для достаточно больших значений n, f (n) может быть привязан в пределах c₁g(n) и c₂g(n) для некоторых значений 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)) (little-oh) означает, что темпы роста f(x) является асимптотически меньше , чем the темпы роста g(x).

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

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

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

Answer 2

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

Можно считать, что все обозначения Big-O имеют полосу.

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

Если смотреть на Θ, то полоса, очевидно, находится посередине.Таким образом, это (асимптотическая) жесткая граница.

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

Answer 3

один из них - Большая буква "О".

один из них - Большая Тета

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

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

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

Когда оба условия верны для одного и того же выражения, вы можете использовать обозначение big theta....

Answer 4

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

Предположим, что время выполнения f(i) является O(1).Ниже приведен фрагмент кода, асимптотическое время выполнения которого равно Θ(n).IT всегда вызывает функцию 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

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

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

---

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

Если:Тета утверждает: "У этого животного 5 ног". из этого следует, что:Значение Big O верно ("У этого животного меньше или равно 5 ногам"). и Значение Omega верно ("У этого животного больше или равно 5 ногам").)

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

Answer 6

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

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

На английском языке,

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

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

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, большое θ и большое Ω как одно и то же.

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

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

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

T (n)= n ^ 2 + n, мы можем сказать T (n)=O (n ^ 2), T (n)=O (n^ 3), T (n)=O (n ^ 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).Почему?Потому что мы подсознательно считаем большое О большим θ.

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

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

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