Qu'est-ce que O dans Big O?

23

Qu'est-ce que Big et O en notation Big O? J'ai lu les définitions et cela ne dit pas ce que O se prononce comme «oh». Par exemple - je comprends que O (n) est la complexité d'un algorithme linéaire où n pourrait être le nombre d'opérations. mais qu'est-ce qu'un O ?

Karen15
la source
13
C'est la 15e lettre de l'alphabet anglais. C'est aussi la 15e lettre de l'alphabet grec.
Joel Etherton
1
Juste pour clarifier: vous cherchez la raison pour laquelle O est le symbole utilisé (au lieu de Q ou E ou autre chose), et quel sens, le cas échéant, O a sur les autres symboles?
FrustratedWithFormsDesigner
6
@ Joel: En fait, c'est Omicron, et c'est la raison pour laquelle cette lettre a été choisie.
Jörg W Mittag
cette réponse réfute (correctement, je pense) la théorie d'Omicron.
Hawkeye Parker

Réponses:

31

Eh bien, je suppose que ce serait l'ordre, qui coïncide avec wikipedia .

Edit: (ma propre (toute amélioration appréciée)) traduction de l' article de wikipedia allemand

La lettre majuscule O (en fait un omicron majuscule à l'époque) comme symbole de l' ordre de (allemand: "Ordnung von") a été utilisée pour la première fois par le théoricien des nombres allemand Paul Bachman dans le deuxième numéro de son livre sur la théorie analytique des nombres. en 1894. La notation gagna en popularité grâce aux travaux d'Edmund Landau, un autre théoricien allemand des nombres, auquel cette nomenclature est largement associée aujourd'hui, en particulier dans la terminologie allemande.

back2dos
la source
5
S'il est possible que de nombreux mathématiciens s'y réfèrent comme tel, il n'en était pas ainsi à l'origine. Si vous lisez des livres sur la théorie des nombres du début du 20e siècle, vous ne trouverez aucune explication de ce genre. C'est ce que c'est et je ne peux pas lire l'allemand pour comprendre ce qu'il pensait de la notation.
Jonathan Henson
1
@Jonathan: Post mis à jour.
back2dos
Très agréable! J'ai regardé dans tous mes livres de théorie des nombres et je n'ai trouvé aucune explication du O nulle part. +1
Jonathan Henson
2
Je l'ai toujours prononcé comme ordre de simplement dire que O ne veut pas dire grand-chose.
Newtopian
16

"Big" signifie "capital" et "O" signifie ordre, comme dans "ordre de complexité". Ainsi nommé en raison de la convention d'écrire «ordre de complexité» comme O (f (x)), par exemple, avec une majuscule «O» ou un «Big O». Personne n'en parle beaucoup car «tout le monde» comprend ce que cela signifie, et le comprendre ne vous aide pas vraiment à comprendre l'analyse de complexité.

Pour comprendre l'analyse de la complexité, je pense que le lien publié par topgun_ivard est un bon point de départ. Un bon manuel d'introduction couvrant les structures de données ou les algorithmes pourrait également aider.

Ethel Evans
la source
5
Je suis désolé, mais la notation Bachmann-Landau a été inventée par un mathématicien allemand, donc je pense à peine qu'il l'aurait nommée d'après un mot anglais. En fait, même s'il avait été inventé par un mathématicien américain, il aurait probablement encore été nommé d'après un mot allemand, car quand il a été inventé (vers 1920, je pense), la langue internationale des mathématiques était l'allemand. De plus, il n'a même pas à distance ont rien à voir avec la complexité.
Jörg W Mittag
1
@ Jörg: Oui, mais ne serait-ce pas simplement Ordnung , dont l'article wiki allemand prétend être à l'origine: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
back2dos
1
@Ethel pourriez-vous apporter une modification mineure à votre article afin que je puisse vous voter? Vous avez bien raison. Vous devez modifier avant de pouvoir voter.
Jonathan Henson
1
@Jonathan, je ne sais pas exactement quel changement mineur vous voulez. Pouvez-vous simplement aller de l'avant et faire la modification que vous souhaitez? Ou, nous pourrions simplement laisser la réponse de back2dos se tenir, il semble qu'il aurait pu finir avec la meilleure réponse de toute façon en raison d'excellentes recherches :)
Ethel Evans
1
Hm, intéressant. En Suède, Big Oh est généralement appelé "ordo" (latin pour, eh bien, ordre) plutôt que "ordning" (le mot suédois pour l'ordre).
Vatine
11

O représente l'ordre.

Il a été initialement introduit par le mathématicien allemand Paul Bachmann dans le deuxième volume de ses livres sur la théorie des nombres Die Analytische Zahlentheorie , publié en 1894 (p. 401) . Il note, après une formule où il utilise d'abord la notation:

(...) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (...)

Ma traduction:

(...) où avec la notation O (n) nous indiquons une grandeur dont l'ordre par rapport à n ne dépasse pas l'ordre de n (...)

Contrairement à ce que d'autres ont dit, rien dans son texte n'indique qu'il s'agit en fait d'une omikron capitale grecque. Il utilise beaucoup de caractères grecs et latins, il n'y a donc vraiment aucun moyen de le dire. Étant donné son utilisation continue de "Ordnung n log n " etc. dans le texte, il est clair qu'il signifie "Ordnung" (en allemand pour "ordre" s'il y avait un doute) dans tous les cas, mais cela pourrait encore laisser ouverte l'utilisation de un O grec raffiné.

Cependant, l'origine de l'omikron est plus probablement un rétronyme dû à Donald Knuth qui a introduit les symboles oméga (Ω) et thêta (Θ) pour des concepts connexes dans son article Big Omicron et Big Omega et Big Theta , ou peut-être Hardy et Littlewood qui introduit un symbole oméga plus tôt.


la source
2
Intéressant. Je suppose que tu as raison. Je viens de chercher les définitions dans les livres de Landau et de Bachmann, et ils en effet a) utilisent un latin Oh, pas un grec Omikron, b) utilisent tous deux le mot "Ordnung", et c) Landau déclare explicitement que cela signifie "Ordnung" . Je me suis trompé.
Jörg W Mittag
Quel meilleur mot pourrait être trouvé? Je veux dire, d'un Allemand? Ordnung ist das halbe Leben!
JensG
Je pense que la première phrase de votre réponse (correcte, positive, impressionnante) devrait se lire: "O signifie" Ordnung "(en allemand signifiant" Ordre ")." Cela aiderait cette réponse à attirer l'attention des autres lecteurs.
Hawkeye Parker
5

J'aime cet article , en espérant que vous le trouverez utile aussi!

Citant une section de l'article:
Big Greek Letters

Big O est souvent mal utilisé. Big O ou Big Oh est en fait l'abréviation de Big Omicron. Il représente la limite supérieure de la complexité asymptotique. Donc, si un algorithme est O (n log n), il existe une constante c telle que la borne supérieure est cn log n.

Θ (n log n) (Big Theta) est plus étroitement lié que cela. Un tel algorithme signifie qu'il existe deux constantes c1 et c2 telles que c1n log n <f (n) <c2n log n.

Ω (n log n) (Big Omega) dit que l'algorithme a une borne inférieure de cn log n.

Il y en a d'autres mais ce sont les plus communs et Big O est le plus commun de tous. Une telle distinction est généralement sans importance, mais elle mérite d'être notée. La notation correcte est la notation correcte, après tout.

Qu'est-ce que Big O?

La notation Big O cherche à décrire la complexité relative d'un algorithme en réduisant le taux de croissance aux facteurs clés lorsque le facteur clé tend vers l'infini. Pour cette raison, vous entendrez souvent l'expression complexité asymptotique. Ce faisant, tous les autres facteurs sont ignorés. C'est une représentation relative de la complexité.

Qu'est-ce qui n'est pas Big O?

Big O n'est pas un test de performance d'un algorithme. Il est également théorique ou abstrait en ce qu'il tend à ignorer d'autres facteurs. La complexité de l'algorithme de tri est généralement réduite au nombre d'éléments triés comme étant le facteur clé. C'est bien, mais cela ne prend pas en compte des problèmes tels que:

Utilisation de la mémoire: un algorithme peut utiliser beaucoup plus de mémoire qu'un autre. Selon la situation, cela pourrait être tout à fait non pertinent à critique; Coût de la comparaison: Il se peut que la comparaison des éléments soit très coûteuse, ce qui changera potentiellement toute comparaison réelle entre les algorithmes; Coût des éléments en mouvement: la copie d'éléments est généralement bon marché mais ce n'est pas nécessairement le cas; etc.

topgun_ivard
la source
5
Le simple fait de lier un article n'est pas trop utile. C'est généralement une bonne idée de paraphraser ou de citer la section que vous trouvez particulièrement pertinente pour le sujet.
Demian Brecht
3
Les votes négatifs sont-ils vraiment nécessaires? L'article qu'il a lié est très pertinent et à mon humble avis assez utile. Pendant ce temps, la réponse la plus votée est un lien vers un article Wikipedia. +1 pour compenser l'hypocrisie de l'esprit de ruche.
Brandon Moretz
1
-1, parce que l'artice, tout en étant un article très agréable et bien écrit, n'a rien à voir avec la question.
Jörg W Mittag
@Jorg, je n'ai jamais dit que l'article résoudrait le problème, mais j'ai partagé parce que je l'avais trouvé utile lorsque je regardais ces concepts.
topgun_ivard
3
@topgun_ivard: Que se passe-t-il si cela se transforme en lien mort? La paraphrase permet 1) à l'audience de ce fil d'obtenir une version Notes de Coles de votre lien (le temps c'est de l'argent), et 2) garantit que votre message n'est pas rendu hors de propos sur un lien mort.
Demian Brecht
2

"f (x) est grand-oh de g (x)"

C'est une manière mathématique de prédire la croissance des fonctions.

Soit f et g des fonctions de l'ensemble des entiers ou de l'ensemble ou des nombres réels à l'ensemble des nombres réels. On dit que f (x) est O (g (x)) s'il y a des constantes C et k telles que | f (x) | <= C | g (x) | partout où x> k.

Vous liriez ceci comme "f (x) est grand-oh de g (x)"

Le big-O est parfois appelé symbole Landau d'après le mathématicien allemand Edmund Landau. Je ne pense pas que cela représente autre chose que cela. Vous avez également les notations big-Omega et big-Theta similaires. Les symboles sont aussi arbitraires que toujours en utilisant thêta pour désigner les angles dans vos triangles dans votre classe de géométrie planaire du lycée.

Correction @ back2dos a fourni une explication satisfaisante pour le O comme se référant à la commande. Bon travail. Voir sa réponse.

Donald Knuth l'a appliqué à l'étude de la complexité des programmes informatiques.

Si vous voulez trouver la raison pour laquelle la notation a été utilisée, vous devriez lire

"Analytische Zahlentheorie" de Paul Bachmann de 1892

Jonathan Henson
la source
2

EDIT: Il s'avère que je me trompe. Néanmoins, cela aide peut-être quelqu'un à garder ses symboles droits, donc je ne vais pas le supprimer.


En fait, ce n'est pas la lettre latine Oh , c'est la lettre grecque Omicron . Malheureusement, ces deux-là ont exactement le même glyphe, donc, au fil du temps, la version originale a été corrompue, et maintenant c'est juste Oh .

Le choix du symbole n'a en fait pas de signification particulière, il a été choisi comme mnémonique dispositif :

  • Omicron contient les lettres MICRO, et la sémantique du symbole Omicron signifie à peu près "plus petit que"
  • Oméga contient les lettres MEGA, et la sémantique du symbole Omega signifie à peu près "plus grand que"
  • Theta (Θ) ressemble un peu à un signe égal, et la sémantique du symbole Theta signifie à peu près "égal à"

C'est ça. Il n'y a pas vraiment de sens, c'est juste un jeu de mots, si vous voulez, pour vous aider à vous souvenir plus facilement de la sémantique.

Jörg W Mittag
la source
2
Bien que j'aimerais croire votre proposition mnémonique (c'est une idée vraiment cool), je vais avoir besoin de voir des preuves que c'est l'intention originale de Bachmann. Fournissez-le et je vous attribuerai +1.
Jonathan Henson
2
@Jonathan Henson: Apparemment, j'ai été induit en erreur par le professeur Knuth :-)
Jörg W Mittag
-5

MISE À JOUR: Tenter de nettoyer ma réponse et d'être plus précis

La notation Big O est un moyen de caractériser les fonctions en fonction de leur taux de croissance. Le O représente l'ordre (le premier ordre étant n le deuxième ordre étant n-carré, etc.). Et si je ne me trompe pas, ce serait le pire des cas pour une exécution des méthodes (ou stockage) avec N éléments. Plus l'ordre est grand, plus la méthode est mauvaise.
Par exemple, rechercher un enregistrement dans un tableau est O (1) (je crois que dans certaines implémentations de tables de hachage, c'est également le cas). Ajouter une valeur à la fin d'une liste de liens serait O (N) car vous devez atteindre la fin de la liste avant de pouvoir ajouter l'élément, etc.

Cette réponse devrait être légèrement plus correcte que ma première tentative :)

LogicielSavant
la source
2
-1 parce que c'est tout simplement vieux incorrect ET a répondu à une question distincte de celle qui a été posée. La question était de savoir pourquoi la lettre "O" est utilisée, et non "comment fonctionne la notation Big O?". Vous avez également tort sur le fonctionnement de Big-oh ... le bouclage à travers un tableau est O (n) où n est la taille du tableau, pas O (1). La notation n'a rien à voir avec les "cycles" d'un algorithme ... c'est une mesure de la limite supérieure du temps d'exécution d'un algorithme.
Casey Patton,
Je ne veux pas discuter avec vous ici, mais c'est un peu ce que je voulais dire. Que signifie le temps d'exécution correctement? Eh bien, le temps d'exécution est déterminé par ce qui doit être traité sur la machine. Je suppose que je sorte de cycle d'utilisation généreusement ici. Par cycle, je suppose que j'aurais dû dire itérer à travers ou quelque chose comme ça. Vous avez raison sur la limite supérieure, cela ne détermine pas la moyenne. Par conséquent, j'accepte la rétrogradation.
SoftwareSavant