La différence entre la limite inférieure et serré lié?
Avec la référence de cette réponse , qu'est-ce que Thêta (serré)?
Omega est la limite inférieure, tout à fait compris, le temps minimum qu'un algorithme peut prendre. Et nous savons que le Big-O est pour la limite supérieure, ce qui signifie le temps maximum qu'un algorithme peut prendre. Mais je n'ai aucune idée à propos de la thêta.
7 réponses
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 il est appelé limite étroite (il doit être à la fois la limite 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 préférable puisqu'il faut au moins n log n Omega (n log n) et pas plus que n log n (Big O n log n).
Θ-notation (notation theta) est appelé "tight-bound" parce qu'il est plus précis que o-notation et Ω-notation (notation omega).
si j'étais paresseux, je pourrais dire que la recherche binaire sur un tableau trié est O(N 2 ), O(n 3 ), et O(2 n ), et je serais techniquement correct dans chaque cas. C'est parce que o-notation spécifie seulement une limite supérieure , et la recherche binaire est limitée sur le côté supérieur par toutes ces fonctions, juste pas très près. Ces estimations paresseuses seraient inutile .
Θ-notation résout ce problème en combinant o-notation et Ω-notation. Si je dis que la recherche binaire Est Θ (log n), cela vous donne des informations plus précises. Il vous dit que l'algorithme est limité sur à la fois côtés par la fonction donnée, de sorte qu'il ne sera jamais beaucoup plus rapide ou plus lent que prévu.
si vous avez quelque chose qui est O(f(n)) qui signifie qu'il y a k , g(n) tel que f(n) ≤ k g(n) .
si vous avez quelque chose qui est Ω(f(n)) qui signifie qu'il y a k , g(n) tel que f(n) ≥ k g(n) .
Et si vous avez quelque chose avec O(f(n)) et Ω(f(n)) , il est Θ(f(n) .
le article de Wikipedia est décent, si un peu dense.
limite supérieure asymptotique signifie qu'un algorithme donné s'exécute pendant le temps maximum, selon le nombre d'entrées.
prenons un algorithme de tri par exemple. Si tous les éléments d'un tableau sont en ordre décroissant, alors pour les trier, il faudra un temps d'exécution de O(n) , montrant la complexité limite supérieure. 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é.
asymptotically tight bound (c 1 G(n) ≤ f(n) ≤ C 2 g(n)) montre la complexité moyenne liée pour une fonction, ayant une valeur entre les limites liées (limite supérieure et limite inférieure), où c 1 et c 2 sont des constantes.
Les expressions un minimum de temps et temps maximum sont un peu trompeuses ici. Quand nous parlons de grandes opérations, ce n'est pas le temps réel qui nous intéresse, c'est la façon dont le temps augmente quand notre taille d'entrée devient plus grande. Et c'est habituellement le temps moyen ou le pire cas dont nous parlons, pas meilleur cas , qui n'est généralement pas significatif dans la résolution de nos problèmes.
utilisant le tableau rechercher dans la réponse acceptée à l'autre question comme 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 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. De plus, il n'augmente pas plus lentement que g(n) non plus. Par conséquent, g(n) est en fait à la fois une limite supérieure et une limite 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 dans la réponse acceptée à l'autre question n'est pas entièrement correcte, qui prétend que O(n) est limite supérieure parce que l'algorithme peut fonctionner en temps constant pour certaines entrées (c'est le meilleur cas j'ai mentionné ci-dessus, qui n'est pas vraiment ce que nous voulons savoir sur le temps 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 chaque cas.
nous pouvons utiliser la notation o ("little-oh") pour désigner une limite supérieure qui n'est pas asymptotiquement serrée. Big-oh et petit-oh sont similaires. Mais, grand-oh est probablement utilisé pour définir asymptotiquement serré limite supérieure.
la différence fondamentale entre
Blockquote
asymptotiquement limite supérieure et asymptotiquement serré Mous.upperbound signifie un algorithme donné qui peut exécuter avec le nombre maximum de temps en fonction du nombre d'entrées ,pour par exemple dans le tri algo si tous les éléments de tableau (n)sont en ordre décroissant puis pour les ascensionner il faudra un temps d'exécution de O(n) qui montre la complexité limite supérieure ,mais si elles sont déjà triés ensuite, il faudra ohm(1).nous avons donc généralement utilisés "O"notation pour la limite supérieure de la complexité.
Asym. tightbound bound montre la limite pour eg(c1g(n)<=f(n)<=c2g(n)) montre la limite étroite telle que la fonction ont la valeur entre deux bound (limite supérieure et limite inférieure),donnant le cas moyen.