Pourquoi Big O est enseigné au lieu de Big Theta?

21

La notation Big O fournit une limite supérieure à une fonction tandis que Big Theta fournit une limite stricte. Cependant, je trouve que la notation Big O est généralement (et informellement) enseignée et utilisée quand elle signifie vraiment Big Theta.

Par exemple, "Quicksort is O (N ^ 2)" peut se transformer en énoncé beaucoup plus fort "Quicksort is Θ (N ^ 2)"

Bien que l'utilisation de Big O soit techniquement correcte, une utilisation plus répandue de Big Theta ne serait-elle pas plus expressive et conduirait à moins de confusion? Y a-t-il une raison historique pour laquelle ce Big O est plus couramment utilisé?

Wikipédia note:

De manière informelle, en particulier en informatique, la notation Big O est souvent autorisée à ê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 les faits dans un contexte donné.

notation big-o big-theta tskuzzy
la source
3
Je sais que cela ne concerne pas vraiment la question, mais le tri rapide n'est pas thêta (N ^ 2). C'est O (N ^ 2).
jsternberg
Big O est ce que les débutants / non-CS doivent savoir. Big Theta est ce qui est couvert dans une introduction aux algorithmes, qui ne sera pas prise par tous les grands. Ceux qui ont eu une classe d'algorithmes peuvent approfondir la notation Big O s'ils le souhaitent. Je ne sais pas à quoi fait référence la citation de Wikipédia. Avec les publications académiques, vous vous ferez la gorge lors d'une conférence si vous confondez Big O et Big Theta. Certaines personnes passent toute leur vie à chasser le Thêta et ce sont des problèmes DIFFICILES.
Job
@jsternberg Techniquement, vous avez raison. Cela est également vrai, mais sans signification: "Quicksort dans tous les cas (pire, meilleur, ...) est O (n ^ 100). Mais je suis d'accord avec OP, il devrait être plus précis: QuickSort le pire des cas est Theta (N ^ 2), le meilleur cas QuickSort est Theta (NlogN), car dans chaque cas, nous aurons une fonction différente.
Eldar

Réponses:

26

Parce que vous êtes généralement intéressé par le pire des cas lors de l'analyse des performances. Ainsi, connaître la limite supérieure est suffisant.

Lorsqu'il s'exécute plus rapidement que prévu pour une entrée donnée - ce n'est pas grave, ce n'est pas le point critique. Ce sont surtout des informations négligeables.

Comme l'a noté @Peter Taylor, certains algorithmes n'ont pas de limite stricte. Voir quicksort par exemple qui est O (n ^ 2) et Omega (n).

De plus, les limites strictes sont souvent plus difficiles à calculer.

Voir également:

Faucon
la source
6
Mais Big O ne correspond pas nécessairement aux performances les plus défavorables. Je pourrais dire que le tri rapide fonctionne en O (2 ^ n) et être 100% correct. Ce serait beaucoup plus significatif si je dis que l'algorithme X s'exécute en Thêta (N ^ 2) plutôt qu'en O (N ^ 2).
tskuzzy
En outre, les limites étroites sont presque toujours calculées lors de l'analyse des algorithmes plutôt que simplement une limite supérieure. Je demande pourquoi les gens n'utilisent pas seulement la notation thêta beaucoup plus expressive quand ils le peuvent.
tskuzzy
9
Je vous ai expliqué pourquoi la plupart des programmeurs ne l'utilisent pas. Nous sommes paresseux et n'avons pas besoin d'autant de précision. Personne ne vous empêche d'utiliser de gros thêta si vous le souhaitez. Allez-y, faites-le. Votre choix d'algorithme n'en tirera probablement pas grand-chose. Je n'ai jamais entendu parler d'un programmeur confus par la grande notation O. Moi aussi, je ne trouve pas cela déroutant du tout.
Falcon
9

L'une des raisons est qu'il existe de nombreux cas où Θ n'est tout simplement pas connu. Par exemple, la multiplication matricielle est O (n ^ 2,376) mais il n'y a pas de limite étroite connue. Bien sûr, pour autant que je sache , il existe une limite stricte pour la multiplication matricielle, mais nous ne connaissons pas sa valeur.

MSalters
la source
Mais ce serait la limite du temps d'exécution d'un problème, pas un algorithme particulier. Alors que la multiplication matricielle en général peut être résolue plus rapidement que le temps cubique, l'algorithme naïf est Θ (n ^ 3) quoi qu'il arrive.
tskuzzy
5
@tskuzzy, prenez quicksort. Il n'a pas de liaison thêta, car c'est O (n ^ 2) et Omega (n).
Peter Taylor