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

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

все обозначения Big-O можно считать имеющими бар.

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

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

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

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

один большой тета

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

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

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

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

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

предположим, что время выполнения 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);
}

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

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

---

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

Если: Тета утверждает: "у этого животного 5 ног." тогда получается, что: Большое О верно ("это животное имеет меньше или равно 5 ног.") и Омега истинна ("это животное имеет больше или равно 5 ноги.")

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

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

Θ-нотация-тот же порядок / o-нотация-верхняя граница

На Английском Языке

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

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

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

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

статья в Википедии о Big O Notation

вывод: мы рассматриваем big O, big θ и big Ω как одно и то же.

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

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

чтобы ясно объяснить отношение между большим О и большим θ, я сначала объясню отношение между большим О и малым о. Из определения мы можем легко узнать, что малый 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), Т(п)=о(N^4) верны для небольших часов. Избыточные Т(П)=О(N^2) - это что? Это большой θ!

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

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

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

используя пределы

рассмотрим 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