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

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

Если алгоритм имеет Θ (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) не Θ (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))

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

Обобщить:

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) асимптотически меньше скорости роста g(x).

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

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

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

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

Можно считать, что все нотации Big-O имеют черту.

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

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

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

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

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

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

Большой 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);
}

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

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

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

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

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

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

Таким образом, если кто-то заявляет 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 и т. Д.

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

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

Статья в Википедии о нотации Big O

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

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

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

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

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

Чтобы ясно объяснить связь между большим 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). Почему? Потому что подсознательно мы рассматриваем большую O как большую θ.

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

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