Différence entre la limite inférieure et la limite étroite?

Question

Avec la référence de cette réponse , qu’est-ce que Theta (lien étroit)?

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, signifie le temps maximum qu'un algorithme peut prendre. Mais je n'ai aucune idée en ce qui concerne la Thêta.

Answer 1

Big O est la limite supérieure, alors que Omega est la limite inférieure. Theta nécessite à la fois Big O et Omega, c'est pourquoi on l'appelle un lien étroit (il doit s'agir à la fois des limites supérieure et 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 nettement préférentiel puisqu'il prend AU MOINS n log n (Journal n Omega) et AUCUN NO log n (Grand journal n).

Answer 2

Θ-la notation est appelée serré liés car il est plus précis que O-notation et Ω-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 voudrais être techniquement correct dans tous les cas. C'est parce que O-notation ne spécifie une limite supérieure, et la recherche binaire est délimité sur le côté élevé par l'ensemble de ces fonctions, tout simplement pas de très près. Ces paresseux estimations serait inutile.

Θ-notation résout ce problème en combinant O-notation et Ω-notation. Si je dis que le binaire de recherche est en Θ(n lg n), qui vous donne des renseignements plus précis. Il vous dit que l'algorithme est bordée sur deux côtés par la fonction donnée, de sorte qu'il ne sera jamais nettement plus rapide ou plus lent que l'a déclaré.

Answer 3

Si vous avez quelque chose de grand O(f(n)) qui signifie qu'il y a sont k, g(n) telle que f(n) ≤ k g(n).

Si vous avez quelque chose qui Ω(f(n)) qui signifie qu'il y a sont k, g(n) telle que f(n) ≥ k g(n).

Et si vous avez une fonction avec O(f(n)) et Ω(f(n)), alors il est Θ(f(n).

L' article de Wikipedia est décent, même si un peu dense.

Answer 4

Asymptotique de la limite supérieure et asymptotiquement serré lié:

Asymptotique de la limite supérieure de l' signifie que l'algorithme s'exécute au cours de la période de temps maximale, en fonction du nombre d'entrées. Prenons un algorithme de tri par exemple.Si tous les array (n) des éléments sont dans l'ordre décroissant, croissant eux, il va prendre un temps d'exécution de l' O(n), montrant la limite supérieure de la complexité. Si le tableau est déjà trié, la valeur sera O(1). Généralement, "O"notation est utilisé pour la limite supérieure de la complexité.

Asymptotiquement serré lié (c1g(n)<=f(n)<=c2g(n)) affiche la moyenne liée à la complexité d'une fonction, d'une valeur entre liée limites (limite supérieure et de limite inférieure).

Answer 5

Les expressions de temps minimum et maximum de temps sont un peu trompeuses ici. Lorsque nous parlons de grand O de notations, c'est ne pas le temps réel qui nous intéresse, c'est comment le temps augmente lors de notre entrée taille devient plus grande. Et c'est généralement à la moyenne ou au pire des cas le temps dont nous parlons, pas dans le meilleur des cas, qui n'est généralement pas significatif dans la résolution de nos problèmes.

À l'aide de la matrice de la recherche dans la accepté de répondre à l'autre question, à titre d'exemple. Le temps qu'il faut pour trouver un numéro dans la liste de taille n est n/2 * some_constant en moyenne. Si vous le traiter comme une fonction f(n) = n/2*some_constant, il augmente pas plus vite que g(n) = n, dans le sens donné par Charlie. Aussi, il augmente non plus lent que g(n) . Par conséquent, g(n) est en fait à la fois une limite supérieure et une limite inférieure de l' f(n) en Grande-O notation, de sorte que la complexité de la recherche linéaire est exactement n, c'est-à-Theta(n).

À cet égard, l'explication de la accepté de répondre à l'autre question, c'est pas tout à fait correct, qui prétend que O(n) est la limite supérieure, car l'algorithme peut s'exécuter en temps constant pour certains intrants (c'est le meilleur des cas que j'ai mentionné ci-dessus, ce qui n'est pas vraiment ce que nous voulons savoir sur le temps d'exécution).