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

Question

Avec la référence de ceci répondre, qu'est-ce que Theta (liaison étroite) ?

Omega est la limite inférieure, bien entendu, le temps minimum qu'un algorithme peut prendre.Et nous savons que Big-O signifie limite supérieure, ce qui signifie le temps maximum qu'un algorithme peut prendre.Mais je n'ai aucune idée concernant le Theta.

Answer 1

Grand O est la limite supérieure, tandis que Oméga est la limite inférieure. Thêta nécessite à la fois Big O et Omega, c'est pourquoi on l'appelle un lié étroitement (il doit s'agir à la fois de la limite supérieure et de la limite inférieure).

Par exemple, un algorithme prenant Omega(n log n) prend au moins n log n temps, mais n’a pas de limite supérieure.Un algorithme prenant Theta(n log n) est de loin préférentiel puisqu'il faut au moins n log n (Oméga n log n) et pas plus que n log n (Big O n log n).

Answer 2

La

& # 920; -notation (notation thêta) est appelée lien étroit car elle est plus précise que la notation-O et la & # 937; -notation (notation oméga).

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

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

Answer 3

Si vous avez quelque chose qui est O (f (n)) , cela signifie qu'il existe k , g (n) tel que f (n) & # 8804; k g (n) .

Si vous avez quelque chose qui & # 937; (f (n)) signifie qu'il existe k , g (n) tels que f (n) & # 8805; k g (n) .

Et si vous avez quelque chose avec O (f (n)) et & # 937; (f (n)) , c’est alors & # 920; (f (n) .

Le article de Wikipedia est correct s'il est un peu dense.

Answer 4

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

Prenons l'exemple d'un algorithme de tri. Si tous les éléments d'un tableau sont dans l'ordre décroissant, leur tri requiert un temps d'exécution de O(n), ce qui indique la complexité de la limite supérieure. Si le tableau est déjà trié, la valeur sera O(1).

En général, O-notation est utilisé pour la complexité de la limite supérieure.

Lien asymptotiquement serré (c 1 g (n) & # 8804; f (n) & # 8804; c 2 g (n)) montre la complexité liée moyenne d'une fonction, ayant une valeur comprise entre les limites liées (limite supérieure et inférieure), où c ₁ et c ₂ sont des constantes.

Answer 5

Les expressions temps minimum et temps maximum sont un peu trompeuses ici. Lorsque nous parlons de grandes notations O, ce n’est pas le temps qui nous intéresse, c’est comment 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, et non pas le meilleur des cas , qui n’a généralement pas de sens pour résoudre nos problèmes.

En utilisant le tableau, recherchez 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 * en moyenne. Si vous la traitez comme une fonction f(n) = n/2*some_constant, elle n'augmente pas plus vite que g(n) = n, au sens donné par Charlie. En outre, il n’augmente pas plus lentement que g(n) non plus. Par conséquent, f(n) est en fait à la fois une limite supérieure et une limite inférieure de <=> en notation Big-O, la complexité de la recherche linéaire est donc exactement n , ce qui signifie que c'est Theta (n).

À cet égard, l’explication contenue dans la réponse acceptée à l’autre question n’est pas tout à fait correcte, affirmant que O (n) est la limite supérieure, car l’algorithme peut être exécuté en temps constant pour certaines entrées (il s’agit de la Dans le meilleur des cas , j’ai mentionné ci-dessus, ce qui n’est pas vraiment ce que nous voulons savoir sur la durée).

Answer 6

  

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

Nous pouvons utiliser la notation o (& "; little-oh &") pour désigner une borne supérieure qui n'est pas serrée de manière asymptotique. Big-oh et little-oh sont similaires. Mais big-oh est probablement utilisé pour définir une limite supérieure serrée de manière asymptotique.

Answer 7

Plus précisément, la limite inférieure ou $ \ omega $ bfon f (n) désigne l'ensemble des fonctions asymptotiquement inférieures ou égales à f (n), c.à.d. U      g (n) & # 8804; cf (n) $ \ pour tout $ `un & # 8805; n ' Pour certains c, n '$ \ in $ $ \ Bbb {N} $

Et la limite supérieure ou $ \ mathit {O} $ sur f (n) désigne l'ensemble des fonctions asymptotiquement supérieures ou égales à f (n) qui indique mathématiquement,

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

Maintenant, le $ \ Theta $ est l'intersection de ce qui est écrit ci-dessus deux

  

$\theta $

Comme si un algorithme ressemblait à " exactement $ \ Omega \ left (f (n) \ right $ & "; alors il vaut mieux dire que c'est $ \ Theta \ left (f (n) \ right) $.

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

Answer 8

La différence fondamentale entre

  

Blockquote

limite asymptotiquement supérieure et asymptotiquement serrée Asym.upperbound désigne un algorithme donné capable de s'exécuter avec un maximum de temps en fonction du nombre d'entrées. Par exemple, dans un ordre de tri, si tous les éléments du tableau (n) sont dans un ordre décroissant, leur durée d'exécution sera de O (n) qui montre la complexité de la borne supérieure, mais s’ils sont déjà triés, il faudra ohm (1). Nous avons donc généralement utilisé la notation & "O &" Pour la complexité de la borne supérieure.

Asym. «boundbound bound» montre par exemple le pour (c1g (n) < = f (n) < = c2g (n)) indique la limite étroite telle que la fonction ait la valeur entre deux bornes (supérieur lié et inférieur), donnant la moyenne des cas.