Quelle est la différence entre la borne inférieure et la borne étroite?

Avec la référence de cette réponse , qu'est-ce que Theta (borne serrée)?

Omega est la limite inférieure, bien comprise, le temps minimum qu'un algorithme peut prendre. Et nous savons que Big-O est pour la borne supérieure, c'est-à-dire le temps maximum qu'un algorithme peut prendre. Mais je n'ai aucune idée de la Theta.

Big O est la limite supérieure, tandis que Omega est la limite inférieure. Theta nécessite à la fois Big O et Omega, c'est pourquoi on l'appelle une limite étroite (il doit s'agir à la fois de la limite supérieure et inférieure).

Par exemple, un algorithme Omega(n log n)prend au moins du n log ntemps, mais n'a pas de limite supérieure. Une prise d'algorithme Theta(n log n)est de loin préférentielle car elle prend au moins n log n (Omega n log n) et pas plus de n log n (Big O n log n).

Θ notation (thêta notation) est appelée lié serré , car il est plus précis que la notation O et Ω notation (oméga notation).

Si j'étais paresseux, je pourrais dire que la recherche binaire sur un tableau trié est O (n ² ), O (n ³ ) et O (2 ⁿ ), et je serais techniquement correct dans tous les cas. C'est parce que la notation O ne spécifie qu'une limite supérieure et que la recherche binaire est délimitée par toutes ces fonctions, mais pas très étroitement. Ces estimations paresseuses seraient inutiles .

La notation Θ résout ce problème en combinant la notation O et la notation Ω. Si je dis que la recherche binaire est Θ (log n), cela vous donne des informations plus précises. Il vous indique que l'algorithme est limité des deux côtés par la fonction donnée, donc il ne sera jamais beaucoup plus rapide ou plus lent que prévu.

Si vous avez quelque chose qui est O (f (n)), cela signifie qu'il y a k , g (n) tels que f (n) ≤ kg (n) .

Si vous avez quelque chose qui est Ω (f (n)), cela signifie qu'il y a k , g (n) tel que f (n) ≥ kg (n) .

Et si vous avez quelque chose avec O (f (n)) et Ω (f (n)) , alors c'est Θ (f (n) .

L' article Wikipédia est correct, même s'il est un peu dense.

La limite supérieure asymptotique signifie qu'un algorithme donné s'exécute pendant la durée maximale, en fonction du nombre d'entrées.

Prenons un algorithme de tri comme exemple. Si tous les éléments d'un tableau sont dans l'ordre décroissant, alors pour les trier, cela prendra un temps d'exécution de O(n), montrant la complexité de la limite supérieure. Si le tableau est déjà trié, la valeur sera O(1).

Généralement, O-notationest utilisé pour la complexité de la limite supérieure.

La borne asymptotiquement serrée (c ₁ g (n) ≤ f (n) ≤ c ₂ g (n)) montre la complexité moyenne de la borne pour une fonction, ayant une valeur entre les limites de la borne (borne supérieure et borne inférieure), où c ₁ et c ₂ sont des constantes.

Les expressions temps minimum et temps maximum sont ici un peu trompeuses. Lorsque nous parlons de grandes notations O, ce n'est pas le moment réel qui nous intéresse, c'est la façon dont le temps augmente lorsque la taille de notre entrée augmente. Et c'est généralement le temps moyen ou le pire des cas dont nous parlons, pas le meilleur des cas , ce qui n'est généralement pas significatif pour résoudre nos problèmes.

Utilisation de la recherche par tableau dans la réponse acceptée à l'autre question à titre d'exemple. Le temps nécessaire pour trouver un nombre particulier dans une liste de taille n est de n / 2 * some_constant en moyenne. Si vous le traitez comme une fonction f(n) = n/2*some_constant, il n'augmente pas plus vite que g(n) = n, dans le sens donné par Charlie. En outre, il n'augmente pas plus lentement que l'un g(n)ou l'autre. Par conséquent, g(n)est en fait à la fois une borne supérieure et une borne inférieure de f(n)en notation Big-O, de sorte que la complexité de la recherche linéaire est exactement n , ce qui signifie qu'il s'agit de Thêta (n).

À cet égard, l'explication de la réponse acceptée à l'autre question n'est pas tout à fait correcte, qui prétend que O (n) est la borne supérieure car l'algorithme peut fonctionner en temps constant pour certaines entrées (c'est le meilleur cas que j'ai mentionné ci-dessus, ce qui n'est pas vraiment ce que nous voulons savoir sur la durée de fonctionnement).

Si j'étais paresseux, je pourrais dire que la recherche binaire sur un tableau trié est O (n2), O (n3) et O (2n), et je serais techniquement correct dans tous les cas.

Nous pouvons utiliser la notation o ("little-oh") pour désigner une borne supérieure qui n'est pas asymptotiquement serrée. Le grand-oh et le petit-oh sont similaires. Mais, big-oh est probablement utilisé pour définir une limite supérieure asymptotiquement serrée.

Précisément la borne inférieure ou $ \ omega $ bfon f (n) signifie l'ensemble des fonctions qui sont asymptotiquement inférieures ou égales à f (n) soit U g (n) ≤ cf (n) $ \ pour tout $ `un≥ n 'Pour certains c, n' $ \ in $ $ \ Bbb {N} $

Et la borne supérieure ou $ \ mathit {O} $ sur f (n) signifie l'ensemble des fonctions qui sont assymptotiquement plus grandes ou égales à f (n) qui dit mathématiquement,

$ g (n) \ ge cf (n) \ pour tout n \ ge n '$, pour certains c, n' $ \ in $ $ \ Bbb {N} $.

Maintenant, le $ \ Theta $ est l'intersection des deux écrits ci-dessus

$\theta $

Comme si un algorithme est comme "exactement $ \ Omega \ left (f (n) \ right $", il vaut mieux dire que c'est $ \ Theta \ left (f (n) \ right) $.

Ou, nous pouvons dire aussi que cela nous donne la vitesse réelle où $ \omega $nous donne la limite la plus basse.

La différence fondamentale entre

Blockquote

Limite asymptotiquement supérieure et asymptotiquement serrée Asym.upperbound signifie un algorithme donné qui peut s'exécuter avec un temps maximum en fonction du nombre d'entrées, par exemple dans l'algo de tri si tous les éléments du tableau (n) sont dans l'ordre décroissant puis pour les monter prendra un temps d'exécution de O (n) qui montre la complexité de la limite supérieure, mais s'ils sont déjà triés, alors cela prendra ohm (1). Ainsi, nous avons généralement utilisé la notation «O» pour la complexité de la limite supérieure.

Asym. borne serrée montre le pour, par exemple (c1g (n) <= f (n) <= c2g (n)) montre la borne limite étroite telle que la fonction ait la valeur entre deux bornes (borne supérieure et borne inférieure), donnant le cas moyen.