Quelqu'un pourrait-il expliquer Big O contre Big Omega contre Big Theta? [dupliquer]
possibilité de dupliquer:
Notation Big Theta - qu'est-ce que big Theta représente exactement?
je le comprends en théorie, je suppose, mais ce que j'ai du mal à saisir c'est l'application des trois.
à l'école, nous avons toujours utilisé Big O pour indiquer la complexité d'un algorithme. Le tri des bulles était O (N^2) par exemple.
maintenant, après avoir lu une autre théorie, je comprends que le Grand Oh n'est pas la seule mesure, il y en a au moins deux autres intéressantes.
Mais voici ma question:
Big O est la limite supérieure, Big Omega est la limite inférieure, et Big Theta est un mélange des deux. Mais ce que cela signifie sur le plan conceptuel? Je comprends ce que cela signifie sur un graphique; j'en ai vu des millions d'exemples. Mais que signifie, pour la complexité de l'algorithme? Comment une "limite supérieure" ou un "limite inférieure" avec ça?
je suppose que je ne comprends pas son application. Je comprends que si multiplié par une certaine constante c que si après une certaine valeur n_0 f(x) est plus grand que g(x), f(x) est considéré O(G(x)). Mais qu'est-ce que cela signifie pratiquement? Pourquoi multiplier f (x) par une valeur c? Bon sang, je pensais qu'avec la notation Big O, les multiples n'avaient pas d'importance.
1 réponses
la notation du grand O, et ses parents, Le Grand thêta, le grand Oméga, le petit o et le petit oméga sont des façons de dire quelque chose au sujet de la façon dont une fonction se comporte à un point limite (par exemple, à l'approche de l'infini, mais aussi à l'approche de 0, etc.) sans dire grand-chose d'autre à propos de la fonction. Ils sont généralement utilisés pour décrire l'espace et le temps de fonctionnement des algorithmes, mais peut également être vu dans d'autres domaines des mathématiques concernant le comportement asymptotique.
le la définition semi-intuitive est la suivante:
Une fonction g(x) est O(f(x)) si "d'un certain point sur", g(x) est inférieure à c*f(x), où c est une constante.
les autres définitions sont similaires, Theta exigeant que g(x) soit entre deux multiples constants de f(x), Omega exigeant g(x)>c*f(x), et les petites versions exigent que cela soit vrai pour toutes ces constantes.
mais pourquoi est-il intéressant de dire, par exemple, qu'un l'algorithme a-t-il une durée de O(N^2)?
c'est intéressant surtout parce que, en informatique théorique, nous sommes plus intéressés par la façon dont les algorithmes se comportent pour les entrées importantes. Ceci est vrai parce que sur de petites entrées les temps d'exécution d'algorithme peuvent varier considérablement en fonction de l'implémentation, de la compilation, du matériel, et d'autres choses qui ne sont pas vraiment intéressantes lors de l'analyse théorique d'un algorithme.
Le taux de croissance, cependant, dépend généralement de la nature de l'algorithme, et pour l'améliorer, vous avez besoin d'un éclairage plus profond sur le problème que vous essayez de résoudre. C'est le cas, par exemple, avec les algorithmes de tri, où vous pouvez obtenir un algorithme simple (type bulle) à exécuter en O(N^2), mais pour améliorer ceci à O(N log n) Vous avez besoin d'une idée vraiment nouvelle, comme celle introduite dans le type de fusion ou de tas.
, d'autre part, si vous avez un algorithme qui s'exécute dans exactement 5 secondes, et une autre qui s'exécute dans 1000n secondes (ce qui est la différence entre un long bâillement et une pause de lancement pour n=3, par exemple), quand on arrive à n=10000000000, la différence d'échelle semble moins importante. Si vous avez un algorithme qui prend O(log n), cependant, vous auriez à attendre log(10000000000)=12 secondes, peut-être multiplié par une constante, au lieu de la presque 317,098 années, qui, peu importe la taille de la constante est une échelle complètement différente.
j'espère que cela rend les choses un peu plus claires. Bonne chance avec votre les études!