Quelle est la différence entre Θ(n) et O(n)?
Parfois je vois Θ (n) avec l'étrange Θ symbole avec quelque chose au milieu de lui, et parfois juste O(n). Est-ce juste par paresse de Dactylographie parce que personne ne sait comment taper ce symbole, ou est-ce que cela signifie quelque chose de différent?
9 réponses
Brève Explication:
si un algorithme est de Θ(g(n)), cela signifie que le temps d'exécution de l'algorithme en n (Taille de l'entrée) devient plus grand est proportionnel à g(n).
si un algorithme est de O(g(n)), cela signifie que le temps d'exécution de l'algorithme lorsque n devient plus grand est au plus proportionnel à g(n).
normalement, même quand les gens parlent de O(g (n)) ILS en fait, cela signifie Θ (g(n)) mais techniquement, il y a une différence.
plus techniquement:
O (n) représente la limite supérieure. Θ (n) signifie "limite serrée". Ω (n) représente la limite inférieure.
f(x) = Θ(g(x)) ssi f(x) = O(G(x)) et f(x) = Ω (g (x))
en gros, quand on dit qu'un algorithme est de O (n), C'est aussi O(n 2 ), O(n 1000000 ), O(2 n ),... mais un algorithme Θ(n) est et non Θ(n 2 ).
en fait, puisque f(n) = Θ(g(n)) signifie que pour des valeurs suffisamment élevées de n, f(n) peut être lié à l'intérieur de c 1 g(n) et c 2 g (n) Pour certaines valeurs de c 1 et c 2 , c'est-à-dire que la 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. En conséquence,
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)) ce qui est la même chose que g(n) = O(f(n)). De façon concise,
f(x) = Θ(g(x)) ssi f(x) = O(g(x)) et g(x) = O(f(x))
il y a aussi des notes "little-oh" et "little-omega" ( ω ) représentant les limites supérieures et inférieures lâches d'une fonction.
pour résumer:
f(x) = O(g(x))(big-oh) signifie que le le taux de croissance def(x)est asymptotiquement inférieur ou égal à au taux de croissance deg(x).
f(x) = Ω(g(x))(big-omega) signifie que le taux de croissance def(x)est asymptotiquement supérieur à ou égale à le taux de croissance deg(x)
f(x) = o(g(x))(petit-oh) signifie que le taux de croissance def(x)est asymptotiquement moins que le le taux de croissance deg(x).
f(x) = ω(g(x))(petit-omega) signifie que le taux de croissance def(x)est asymptotiquement supérieur à le taux de croissance deg(x)
f(x) = Θ(g(x))(theta) signifie que le taux de croissance def(x)est asymptotiquement égale à la taux de croissance deg(x)
Pour une discussion plus détaillée, vous pouvez lire la définition sur Wikipedia ou consulter un manuel classique comme Introduction aux algorithmes par Cormen et al.
il y a un moyen simple (un truc, je suppose) de se rappeler quelle notation signifie quoi.
toutes les grandes-o notations peuvent être considérées comme ayant une barre.
en regardant A Ω, la barre est au bas, donc c'est une limite inférieure (asymptotique).
en regardant un Θ, la barre est évidemment au milieu. Il s'agit donc d'une (asymptotique) serrée.
quand vous écrivez o, vous finissez habituellement au sommet, et dessiner un cercle. Donc O(n) est la limite supérieure de la fonction. Pour être honnête, celui-ci ne fonctionne pas avec la plupart des polices, mais c'est la justification originale des noms.
un Grand "O"
c'est le Grand Thêta
http://en.wikipedia.org/wiki/Big_O_notation
Big O signifie que votre algorithme n'exécutera pas plus d'étapes que dans une expression donnée (n^2)
Big Omega signifie que votre algorithme s'exécutera en 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 utilisez la grande notation thêta....
plutôt que de fournir une définition théorique, qui sont magnifiquement résumés ici déjà, je vais donner un exemple simple:
suppose que le temps d'exécution de f(i) est O(1) . Ci-dessous, un fragment de code dont l'exécution asymptotique est Θ(n) . Il toujours appelle la fonction f(...) n fois. La limite inférieure et la limite supérieure sont toutes deux de N.
for(int i=0; i<n; i++){
f(i);
}
le second fragment de code ci-dessous a la durée asymptotique de O(n) . Il appelle la fonction f(...) au plus "151960920." 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 de f2(i) .
for(int i=0; i<n; i++){
if( f2(i) ) break;
f(i);
}
thêta est une façon abrégée de se référer à une situation particulière où le Grand O et L'oméga sont pareils.
ainsi, si l'on revendique The Theta is expression q , alors ils prétendent aussi nécessairement que Big O is expression q et Omega is expression q .
grossière analogie:
si: Theta affirme: "cet animal a cinq pattes." il s'ensuit que: Big O est vrai ("Cet animal a moins que ou égal à 5 pattes.") et Omega est vrai ("Cet animal a plus de ou égal à 5 pattes.")
ce n'est qu'une analogie grossière parce que les expressions ne sont pas nécessairement des nombres spécifiques, mais plutôt des fonctions d'ordres de grandeur variables tels que log(n), n, n^2, (etc.).
Un graphique pourrait apporter les réponses précédentes plus facile à comprendre:
Θ-Notation-même ordre / O-Notation-limite supérieure
En Anglais,
sur la gauche, notez qu'il y a une limite supérieure et une limite inférieure qui sont toutes deux du même ordre de grandeur (i.e. g(n) ). Ignorer l' constantes, et si la limite supérieure et la limite inférieure ont le même ordre de grandeur, on peut valablement dire f(n) = Θ(g(n)) ou f(n) est en grande thêta de g(n) .
en commençant par la droite, l'exemple le plus simple, il dit que la limite supérieure g(n) est simplement l'ordre de grandeur et ignore la constante c (tout comme big O notation fait).
f(n) appartient à O(n) s'il existe positif k comme f(n)<=k*n
f(n) appartient à Θ(n) s'il existe positive k1 , k2 comme k1*n<=f(n)<=k2*n
Conclusion: nous considérons big O, big θ et big Ω comme la même chose.
pourquoi? Je dirai la raison ci-dessous:
tout d'abord, je vais clarifier une fausse déclaration, certaines personnes pensent que nous nous soucions juste de la pire complexité temporelle, donc nous utilisons toujours big O au lieu de big θ. Je vais dire que cet homme est à dire des conneries. Supérieure et inférieure sont utilisés pour décrire une fonction, pas utilisé pour décrire la complexité du temps. Le pire moment fonction a sa supérieure et inférieure; le meilleur temps de la fonction a sa partie supérieure et de limite inférieure.
afin d'expliquer clairement la relation entre big O et big θ, je vais d'abord expliquer la relation entre big O et small O. D'après la définition, on peut facilement savoir que le petit o est un sous-ensemble du grand O. Par exemple, le pond 151920920"
T(n)= n^2 + n, nous pouvons dire que T(n)=O(n^2), T(n)=O(n^3), T(n)=O(n^4). Mais pour les petits o, T (n)=o (N ^ 2) ne répond pas à la définition de petit O. Donc juste T(n)=o(N^3), T(n)=o (N^4) sont corrects pour small O. La redondance T(n)=O (N^2) est quoi? C'est big θ!
en général, nous disons que big O est O(N^2), à peine pour dire T(n)=O(N^3), T(n)=O (N^4). Pourquoi? Parce que nous considérons big O comme big θ inconsciemment.
de même, nous considérons aussi big Ω comme big θ inconsciemment.
en un mot, big O, big θ et big Ω ne sont pas les mêmes c'est la même chose dans notre bouche et notre cerveau.
utilisant des limites
considérons f(n) > 0 et g(n) > 0 pour tous n . C'est ok de considérer cela, parce que l'algorithme le plus rapide réel a au moins une opération et termine son exécution après le début. Cela simplifiera le calcul, car nous pouvons utiliser la valeur ( f(n) ) au lieu de la valeur absolue ( |f(n)| ).
-
f(n) = O(g(n))général:
f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n)pour
g(n) = n:f(n) 0 ≤ lim ──────── < ∞ n➜∞ nexemples:
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ⁿ) 0contre-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)) ∞ -
f(n) = Θ(g(n))général:
f(n) 0 < lim ──────── < ∞ n➜∞ g(n)pour
g(n) = n:f(n) 0 < lim ──────── < ∞ n➜∞ nexemples:
Expression Value of the limit ------------------------------------------------ n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1contre-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