Big-oh vs big-theta

Duplication possible:
Quelle est la différence entre Θ (n) et O (n)?

Il me semble que lorsque les gens parlent de la complexité des algorithmes de manière informelle, ils parlent de big-oh. Mais dans les situations formelles, je vois souvent des big-theta avec parfois des big-oh jetés à terre. Je sais mathématiquement quelle est la différence entre les deux, mais en anglais, dans quelle situation utiliser big-oh incorrect, ou vice versa (un exemple d’algorithme serait apprécié)?

Bonus: pourquoi les gens utilisent-ils toujours le big-oh quand ils parlent de manière informelle?

Big-O est une limite supérieure.

Big-Theta est une limite étroite, c’est-à-dire supérieure et inférieure.

Lorsque les gens ne s’inquiètent que du pire, Big-O suffit. c’est à dire qu’il dit que “ça ne peut pas être bien pire que ça”. Plus la limite est serrée, mieux c’est, mais une limite étroite n’est pas toujours facile à calculer.

Voir également

  • Wikipedia / Notation Big O

Questions connexes

  • Quelle est la différence entre Θ (n) et O (n)?

La citation suivante de Wikipedia nous éclaire également:

De manière informelle, en particulier en informatique, la notation Big O peut souvent être quelque peu abusée pour décrire une limite étroite asymptotique où l’utilisation de la notation Big Theta pourrait être plus appropriée dans un contexte donné.

Par exemple, quand on considère une fonction T(n) = 73n 3 + 22n 2 + 58 , toutes les conditions suivantes sont généralement acceptables, mais l’étroitesse de la limite (les puces 2 et 3 ci-dessous) est généralement préférable à c’est-à-dire, puce 1 ci-dessous).

  1. T(n) = O(n 100 ) , qui est identique à T(n) ∈ O(n 100 )
  2. T(n) = O(n 3 ) , qui est identique à T(n) ∈ O(n 3 )
  3. T(n) = Θ(n 3 ) , qui est identique à T(n) ∈ Θ(n 3 )

Les déclarations anglaises équivalentes sont respectivement:

  1. T(n) croît asymptotiquement pas plus vite que n 100
  2. T(n) croît asymptotiquement pas plus vite que n 3
  3. T(n) croît de manière asymptotique aussi rapidement que n 3 .

Ainsi, alors que les trois énoncés sont vrais, chacun contient progressivement plus d’informations. Dans certains domaines, cependant, la notation Big O (puces numéro 2 dans les listes ci-dessus) serait plus utilisée que la notation Big Theta (puces numéro 3 dans les listes ci-dessus) car les fonctions qui se développent plus lentement sont plus souhaitables.

Je suis un mathématicien et j’ai toujours vu et besoin de notations big-O, big-theta et big-Omega, et pas seulement pour la complexité des algorithmes. Comme les gens l’ont dit, le big-theta est un jeu à deux faces. Ssortingctement parlant, vous devriez l’utiliser lorsque vous voulez expliquer que c’est un algorithme qui fonctionne bien et que cet algorithme ne peut pas faire mieux ou qu’aucun algorithme ne peut faire mieux. Par exemple, si vous dites “Le sorting nécessite des comparaisons Θ (n (log n)) pour les entrées les plus défavorables”, vous expliquez qu’il existe un algorithme de sorting utilisant des comparaisons O (n (log n)) ; et que pour chaque algorithme de sorting, il existe une entrée qui le force à faire des comparaisons Ω (n (log n)).

Maintenant, une raison étroite pour laquelle les gens utilisent O au lieu de Ω est de supprimer les avertissements concernant les cas les plus défavorables ou les cas moyens. Si vous dites “le sorting nécessite des comparaisons O (n (log n))”, alors la déclaration rest vraie pour une entrée favorable. Une autre raison étroite est que même si un algorithme pour faire X prend du temps f (f (n)), un autre algorithme pourrait mieux faire, vous pouvez donc seulement dire que la complexité de X elle-même est O (f (n)).

Cependant, il existe une raison plus large pour laquelle les gens utilisent de manière informelle O. Au niveau humain, il est pénible de toujours faire des déclarations bilatérales lorsque le contraire est “évident” par rapport au contexte. Comme je suis mathématicien, je ferais idéalement toujours attention à dire “je prendrai un parapluie si et seulement si il pleut” ou “je peux jongler 4 balles mais pas 5”, au lieu de “je prendrai un parapluie si pluies “ou” je peux jongler 4 balles “. Mais les autres moitiés de ces déclarations sont souvent manifestement destinées ou manifestement non intentionnelles. C’est juste la nature humaine d’être négligente sur l’évidence. C’est déroutant de séparer les cheveux.

Malheureusement, dans un domaine aussi rigoureux que les mathématiques ou la théorie des algorithmes, il est également déroutant de ne pas diviser les cheveux. Les gens vont inévitablement dire O quand ils devraient avoir dit Ω ou Θ. Sauter des détails parce qu’ils sont “évidents” conduit toujours à des malentendus. Il n’y a pas de solution pour cela.

Parce que mon clavier a une touche O
Il ne possède pas de touche Θ ou Ω.

Je soupçonne que la plupart des gens sont pareillement paresseux et utilisent O quand ils veulent dire Θ parce que c’est plus facile à taper.

Une des raisons pour lesquelles Big O est tellement utilisé, c’est parce qu’il est tellement utilisé. Beaucoup de gens voient la notation et pensent qu’ils savent ce que cela signifie, puis l’utilisent (à tort) eux-mêmes. Cela se produit souvent avec les programmeurs dont l’éducation formelle n’est allée que jusqu’à présent – j’étais une fois coupable moi-même.

Une autre est parce qu’il est plus facile de taper un grand O sur la plupart des claviers non-grecs qu’un gros thêta.

Mais je pense que beaucoup est dû à une sorte de paranoïa. J’ai un peu travaillé sur la programmation liée à la défense (et connaissais très peu l’parsing d’algorithmes à l’époque). Dans ce scénario, la performance la plus défavorable est toujours celle qui intéresse les gens, car le pire des cas pourrait se produire au mauvais moment. Peu importe si la probabilité réelle que cela se produise est bien inférieure à la probabilité que tous les membres d’un équipage subissent une crise cardiaque subite au même moment, cela pourrait toujours se produire.

Bien sûr, beaucoup d’algorithmes ont leur pire cas dans des circonstances très courantes – l’exemple classique étant l’insertion dans l’ordre dans un arbre binary pour obtenir effectivement une liste à lien unique. Une évaluation “réelle” de la performance moyenne doit prendre en compte la fréquence relative des différents types d’intrants.

Bonus: pourquoi les gens utilisent-ils toujours le big-oh quand ils parlent de manière informelle?

Car en big-oh, cette boucle:

 for i = 1 to n do something in O(1) that doesn't change n and i and isn't a jump 

est O(n), O(n^2), O(n^3), O(n^1423424) . big-oh est juste une limite supérieure, ce qui le rend plus facile à calculer parce que vous n’avez pas à trouver de limite.

La boucle ci-dessus est seulement big-theta(n) .

Quelle est la complexité du tamis des eratosthenes ? Si vous avez dit O(n log n) vous ne vous tromperiez pas, mais ce ne serait pas non plus la meilleure réponse. Si vous avez dit big-theta(n log n) , vous auriez tort.

Parce qu’il y a des algorithmes dont le meilleur cas est rapide, et donc techniquement un grand O, pas un gros Theta.

Big O est une limite supérieure , big Theta est une relation d’équivalence .

Il y a beaucoup de bonnes réponses ici, mais j’ai remarqué que quelque chose manquait. La plupart des réponses semblent impliquer que la raison pour laquelle les gens utilisent Big O plutôt que Big Theta est un problème et, dans certains cas, cela peut être vrai. Souvent, une preuve qui conduit à un résultat Big Theta est beaucoup plus complexe que celle qui aboutit à Big O. Cela est généralement vrai, mais je ne crois pas que cela ait un rapport important avec l’utilisation d’une parsing par rapport à l’autre.

Quand on parle de complexité, on peut dire beaucoup de choses. La complexité de Big O time nous indique simplement ce qu’un algorithme est garanti pour fonctionner dans une limite supérieure. Big Omega est beaucoup moins souvent discuté et nous indique le temps minimum requirejs pour exécuter un algorithme, une limite inférieure. Maintenant, Big Theta nous dit que ces deux nombres sont en fait les mêmes pour une parsing donnée. Cela nous indique que l’application a un temps d’exécution très ssortingct, qui ne peut s’écarter que d’une valeur asymptotique inférieure à notre complexité. De nombreux algorithmes ne comportent tout simplement pas de limites supérieure et inférieure asymptotiquement équivalentes.

Donc, votre question d’utiliser Big O à la place de Big Theta serait toujours valable, tandis que l’utilisation de Big Theta à la place de Big O ne serait valide que si Big O et Big Omega étaient égaux. Par exemple, le sorting par insertion a une complexité temporelle de Big О à n ^ 2, mais son meilleur scénario place son Big Omega à n. Dans ce cas, il ne serait pas correct de dire que sa complexité temporelle est Big Theta de n ou n ^ 2 car ils sont deux bornes différentes et doivent être traités comme tels.

J’ai vu Big Theta et je suis sûr que j’ai appris la différence à l’école. Je devais le regarder cependant. Voici ce que dit Wikipedia:

Big O est la notation asymptotique la plus utilisée pour comparer des fonctions, bien que dans de nombreux cas, Big O puisse être remplacé par Big Theta Θ pour des limites asymptotiquement plus ssortingctes.

Source: Notation Big O # Notation asymptotique associée

Je ne sais pas pourquoi les gens utilisent Big-O lorsqu’ils parlent formellement. Peut-être que c’est parce que la plupart des gens sont plus familiers avec Big-O que Big-Theta? J’avais oublié que Big-Theta existait même jusqu’à ce que vous me rappeliez. Bien que ma mémoire soit maintenant rafraîchie, je pourrais finir par l’utiliser dans une conversation. 🙂