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

Question

Parfois je vois Θ(n) avec le symbole de l’étrange Θ avec quelque chose au milieu d’elle et parfois juste o (n). C’est la paresse il suffit de taper car personne ne sait comment taper ce symbole, ou cela signifie quelque chose de différent ?

Answer 1

Pour l'expliquer à votre grand-mère:

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

Par exemple, une limite supérieure pour les naïfs récursive pour calculer la suite de Fibonacci est:

Fib(x) = O(2ⁿ)

mais le resserrement lié est

Fib(x) = Θ(F_n) où F_n est la suite de Fibonacci.

ce qui est aussi valable à la limite supérieure.

Fondamentalement, lorsque nous disons qu'un algorithme est de O(n), il est également en O(n²), O(n^1000000), O(2ⁿ), ... mais Θ(n) de l'algorithme est pas en Θ(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 des petits-oh, et petite-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)) (grande-oh) signifie que le taux de croissance de l' f(x)est asymptotiquement égal ou inférieur pour le taux de croissance de l' g(x).

f(x) = Ω(g(x)) (grande-omega) signifie que le taux de croissance f(x)est asymptotiquement supérieure ou égal au taux de croissance de l' g(x)

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

f(x) = ω(g(x)) (petit-omega) signifie que le taux de croissance f(x)est asymptotiquement plus grand quela le taux de croissance de l' g(x)

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

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

Answer 2

Il existe un moyen simple (un truc, je suppose) pour se souvenir de qui la notation signifie que ce qui.

Tous les Big-O notations peuvent être considérés comme ayant un bar.

Lorsque l'on regarde un Ω, la barre est en bas, donc c'est un (asymptotique) de la limite inférieure.

Lorsque l'on regarde un Θ, le bar est à l'évidence dans le milieu. C'est donc un (asymptotique) serré lié.

Lors de l'écriture manuscrite O, habituellement, vous pouvez finir à la première place, et dessiner un cercle. Donc O(n) est la limite supérieure de la fonction. Pour être juste, celui-ci ne fonctionne pas avec la plupart des polices de caractères, mais c'est la justification initiale des noms.

Answer 3

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

Answer 4

Plutôt que de proposer une définition théorique, qui sont magnifiquement résumée ici déjà, je vais donner un exemple simple:

Supposons que le temps d'exécution d' f(i) est O(1). Ci-dessous est un fragment de code dont asymptotique d'exécution est - Θ(n). Il toujours les appels de la fonction f(...) n temps. À la fois inférieure et la limite supérieure est n.

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

Le deuxième fragment de code ci-dessous a l'asymptotique d'exécution de l' O(n). Il appelle la fonction f(...) au plus, n temps. La limite supérieure est n, mais la limite inférieure pourrait être Ω(1) ou Ω(log(n)), selon ce qui se passe à l'intérieur d' f2(n).

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

Answer 5

f(n) appartient O(n) s'il existe positif k comme f(n)<=k*n

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

Article de wikipédia sur la Notation Grand O