Quelle est la différence entre Θ(n) et O(n)?

Courte explication:

Si un algorithme est de Θ(g(n)), cela signifie que le temps d'exécution de l'algorithme de n (la taille de l'image) est importante, plus est proportionnelle à g(n).

Si un algorithme est de O(g(n)), cela signifie que le temps d'exécution de l'algorithme en tant que n devient plus grand est a plus proportionnelle à g(n).

Normalement, même quand les gens parlent de O(g(n)) qu'ils veulent réellement dire Θ(g(n)), mais, techniquement, il y a une différence.

---

Plus techniquement:

O(n) représente la limite supérieure. Θ(n) signifie serré lié.
Ω(n) représente la limite inférieure.

f(x) = Θ(g(x)) ssi f(x) =
O(g(x)) et f(x) = Ω(g(x))

Fondamentalement, lorsque nous disons qu'un algorithme est de O(n), c'est aussi O(n²), O(n^1000000), O(2ⁿ), ... mais Θ(n) de l'algorithme est pas Θ(n²).

En fait, puisque f(n) = Θ(g(n)) des moyens pour suffisamment grandes valeurs de n, f(n) peut être liée à l'intérieur de c₁g(n) et c₂g(n) pour certaines valeurs de c₁ et c₂, c'est à dire le taux de croissance de f est asymptotiquement égal à g: g peut être une limite inférieure et et une limite supérieure de f. Ceci implique directement f peut être une limite inférieure et une limite supérieure de g ainsi. Par conséquent,

f(x) = Θ(g(x)) ssi g(x) = Θ(f(x))

De même, pour montrer f(n) = Θ(g(n)), il suffit de montrer g est une borne supérieure de f (i.e. f(n) = O(g(n))) et f est une limite inférieure de g (c'est à dire f(n) = Ω(g(n)) qui est exactement la même chose que g(n) = O(f(n))). De manière concise,

f(x) = Θ(g(x)) ssi f(x) = O(g(x)) et g(x) = O(f(x))

---

Il y a aussi un peu-oh et petit-omega (ω) notations représentant lâche supérieure et lâche les limites inférieures d'une fonction.

Pour résumer:

f(x) = O(g(x)) (grand-oh) signifie que
le taux de croissance de f(x) est
asymptotiquement inférieur ou égal
pour pour le taux de croissance de g(x).

f(x) = Ω(g(x)) (grand-omega) signifie
que le taux de croissance de f(x) est
asymptotiquement supérieur ou
égal à le taux de croissance de g(x)

f(x) = o(g(x)) (petit-oh) signifie que
le taux de croissance de f(x) est
asymptotiquement moins le
le taux de croissance de g(x).

f(x) = ω(g(x)) (petit-omega) signifie
que le taux de croissance de f(x) est
asymptotiquement supérieur le
le taux de croissance de g(x)

f(x) = Θ(g(x)) (theta) signifie que
le taux de croissance de f(x) est
asymptotiquement égal le
le taux de croissance de g(x)

Pour une discussion plus détaillée, vous pouvez lire la définition sur Wikipédia ou de consulter un classique des manuels comme Introduction aux Algorithmes par Cormen et coll.

c'est le Grand "O"

c'est le Grand Thêta

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

Big O signifie que votre algorithme s'exécute dans pas plus d'étapes que dans l'expression donnée(n^2)

Gros Omega signifie que votre algorithme s'exécute dans pas moins d'étapes que dans l'expression donnée(n^2)

Lorsque les deux conditions sont vraies pour la même expression, vous pouvez utiliser le grand thêta notation....

Theta est un raccourci façon de se référer à une situtation où
le big O et l'Oméga sont les mêmes.

Ainsi, si l'une des revendications The Theta is expression q, alors ils sont aussi, nécessairement, affirmant que Big O is expression q et Omega is expression q.

---

Grossière analogie:

Si:
Theta revendications", Que l'animal a 5 pattes."
il s'ensuit que:
Big O est vrai ("cet animal est inférieure ou égale à 5 pattes.")
et
Omega est vrai("cet animal est supérieur ou égal à 5 pattes.")

C'est seulement une rude analogie, parce que les expressions ne sont pas nécessairement des numéros spécifiques, mais plutôt des fonctions de divers ordres de grandeur telle que log(n), n, n^2, (etc.).

f(n) appartient à O(n) si il existe positif k comme f(n)<=k*n

f(n) appartient à Θ(n) si il existe positif k1, k2 comme k1*n<=f(n)<=k2*n

Article de wikipédia sur la Notation Grand O

À l'aide de limites

Considérons f(n) > 0 et g(n) > 0 pour tous n. C'est ok pour prendre ceci en considération, parce que la manière la plus rapide réelle de l'algorithme a au moins une opération et termine son exécution après le départ. Ceci permettra de simplifier le calcul, parce que nous pouvons utiliser la valeur (f(n)) au lieu de la valeur absolue (|f(n)|).

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

   Général:

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

   Pour g(n) = n:

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

   Exemples:

       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
   

   Contre-exemples:

       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))

   Général:

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

   Pour g(n) = n:

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

   Exemples:

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

   Contre-exemples:

       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