Que représente exactement la grosse notation ?

Question

Je suis vraiment confus quant aux différences entre les notations big O, big Omega et big Theta.

Je comprends que le grand O est la limite supérieure et le grand Omega la limite inférieure, mais que représente exactement le grand (thêta) ?

J'ai lu que cela signifie lien étroit mais qu'est-ce que ça veut dire ?

Answer 1

Tout d'abord, comprenons ce que sont le grand O, le grand Thêta et le grand Omega. Ils sont tous fixe de fonctions.

Big O donne le haut limite asymptotique tandis que Big Omega donne une limite inférieure. Big Theta donne les deux.

Tout ce qui est (f(n)) est également O(f(n)) mais pas l'inverse.
T(n) est dit être dans (f(n)) s'il est à la fois dans O(f(n)) et en Omega(f(n)) .
Dans la terminologie des sets, (f(n)) es el intersection de O(f(n)) y Omega(f(n))

Par exemple, le tri de fusion est le pire des cas. O(n*log(n)) y Omega(n*log(n)) - et est donc aussi (n*log(n)) mais c'est aussi O(n^2) puisque n^2 est asymptotiquement "plus grande" qu'elle. Cependant, il est no (n^2) Puisque l'algorithme n'est pas Omega(n^2) .

Une explication mathématique un peu plus approfondie

O(n) est la limite supérieure asymptotique. Si T(n) es O(f(n)) cela signifie qu'à partir d'un certain n0 il existe une constante C tal que T(n) <= C * f(n) . D'autre part, big-Omega dit qu'il y a une constante C2 tal que T(n) >= C2 * f(n)) ).

Ne pas confondre !

À ne pas confondre avec l'analyse des cas les plus défavorables, les meilleurs et les moyens : les trois notations (Omega, O, Thêta) sont les suivantes no liés à l'analyse des meilleurs, pires et moyens cas des algorithmes. Chacune d'entre elles peut être appliquée à chaque analyse.

Nous l'utilisons généralement pour analyser la complexité des algorithmes. (comme l'exemple du tri par fusion ci-dessus). Lorsque nous disons "L'algorithme A est O(f(n)) Ce que nous voulons dire, c'est "La complexité des algorithmes dans le pire des cas". 1 l'analyse du cas est O(f(n)) " - c'est-à-dire qu'elle balance "similaire" (ou formellement, pas pire que) la fonction f(n) .

Pourquoi s'intéresser à la limite asymptotique d'un algorithme ?

Eh bien, il y a de nombreuses raisons à cela, mais je crois que les plus importantes d'entre elles sont :

1. Il est beaucoup plus difficile de déterminer le exact fonction de complexité, nous faisons donc un "compromis" sur les notations big-O/big-Theta, qui sont suffisamment informatives sur le plan théorique.
2. Le nombre exact d'opérations est également dépendant de la plate-forme . Par exemple, si nous avons un vecteur (liste) de 16 nombres. Combien d'opérations cela prendra-t-il ? La réponse est : cela dépend. Certains processeurs permettent les additions vectorielles, d'autres non. La réponse varie donc entre les différentes implémentations et les différentes machines, ce qui est une propriété indésirable. La notation big-O est cependant beaucoup plus constante entre les machines et les implémentations.

Pour illustrer ce problème, observez les graphiques suivants :

Il est clair que f(n) = 2*n est "pire" que f(n) = n . Mais la différence n'est pas aussi radicale qu'avec l'autre fonction. Nous pouvons constater que f(n)=logn devient rapidement beaucoup plus faible que les autres fonctions, et f(n) = n^2 devient rapidement beaucoup plus élevé que les autres.
Donc - pour les raisons ci-dessus, nous "ignorons" les facteurs constants (2* dans l'exemple des graphiques), et nous prenons uniquement la notation big-O.

Dans l'exemple ci-dessus, f(n)=n, f(n)=2*n seront tous deux dans O(n) et en Omega(n) - et sera donc également dans Theta(n) .
D'autre part - f(n)=logn sera dans O(n) (il est "meilleur" que f(n)=n ), mais ne sera PAS dans Omega(n) - et ne sera donc PAS non plus dans Theta(n) .
Symétriquement, f(n)=n^2 sera dans Omega(n) mais PAS dans O(n) et donc - n'est PAS non plus Theta(n) .

---

1 Généralement, mais pas toujours, lorsque la classe d'analyse (la plus mauvaise, la moyenne et la meilleure) est manquante, nous voulons vraiment dire le pire des cas.

Answer 2

Cela signifie que l'algorithme est à la fois big-O et big-Omega dans la fonction donnée.

Par exemple, si c'est (n) alors il existe une constante k de telle sorte que votre fonction (d'exécution, quelle qu'elle soit), est plus grande que n*k pour une valeur suffisamment grande n et une autre constante K de sorte que votre fonction soit plus petite que n*K pour une valeur suffisamment grande n .

En d'autres termes, pour une taille suffisamment grande n il est pris en sandwich entre deux fonctions linéaires :

Pour k < K y n suffisamment grande, n*k < f(n) < n*K

Answer 3

Thêta(n) : Une fonction f(n) appartient à Theta(g(n)) s'il existe des constantes positives c1 y c2 tal que f(n) peut être pris en sandwich entre c1(g(n)) y c2(g(n)) . c'est-à-dire qu'il donne à la fois la limite supérieure et la limite inférieure.

Thêta(g(n)) = { f(n) : il existe des constantes positives c1,c2 et n1 telles que 0<=c1(g(n))<=f(n)<=c2(g(n)) pour tout n>=n1 }

quand nous disons f(n)=c2(g(n)) o f(n)=c1(g(n)) il représente une limite asymptotiquement serrée.

O(n) : Il ne donne que la limite supérieure (qui peut être ou non serrée).

O(g(n)) = { f(n) : il existe des constantes positives c et n1 telles que 0<=f(n)<=cg(n) pour tout n>=n1}

ex : La borne 2*(n^2) = O(n^2) est asymptotiquement serrée, alors que la limite 2*n = O(n^2) n'est pas asymptotiquement serré.

o(n) : Il ne donne que la limite supérieure (jamais une limite étroite).

la différence notable entre O(n) & o(n) est que f(n) est inférieur à cg(n) pour tous les n>=n1 mais n'est pas égal comme dans O(n).

ex : 2*n = o(n^2) mais 2*(n^2) != o(n^2)

Answer 4

J'espère que c'est ce que vous voulez trouver dans les classiques. CLRS (page 66) :

Answer 5

La notation Big Theta :

Rien à foirer mon pote !

Si nous avons une fonction à valeur positive f(n) et que g(n) prend un argument à valeur positive n, alors (g(n)) est défini comme {f(n) : il existe des constantes c1, c2 et n1 pour tous les n>=n1}.

où c1 g(n)<=f(n)<=c2 g(n)

Prenons un exemple :

let f(n)=

g(n)=

c1=5 et c2=8 et n1=1

Parmi toutes les notations, la notation , donne la meilleure intuition du taux de croissance de la fonction car elle nous donne une limite serrée contrairement à big-oh et big -omega qui donnent respectivement les limites supérieure et inférieure.

nous dit que g(n) est aussi proche que f(n),le taux de croissance de g(n) est aussi proche que possible du taux de croissance de f(n).