Quest-ce que O dans Big O?

Eh bien, je suppose que ce serait lordre, qui coïncide avec wikipedia .

Modifier: (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 le théoricien allemand des nombres Paul Bachman dans le deuxième numéro de son livre sur la théorie analytique des nombres parut en 1894. La notation gagna en popularité grâce aux travaux dEdmund Landau, un autre théoricien allemand des nombres, auquel cette nomenclature est largement associée aujourdhui, en particulier dans le Terminologie allemande.

Commentaires

• Bien que cela puisse être le cas auquel de nombreux mathématiciens se sont référés en tant que tel, il ne l’était pas à l’origine. Si vous lisez des livres de théorie des nombres du début du 20e siècle, vous ne trouverez pas une telle explication. Cest ce que cest et je ne peux ‘ lire lallemand pour comprendre ce quil pensait de la notation.
• @Jonathan: Message mis à jour.
• Très bien! Jai regardé dans tous mes livres de théorie des nombres et je ne pouvais ‘ trouver une explication du O nulle part. +1
• Je ‘ lai toujours prononcé comme ordre de car le simple fait de dire O ne signifie pas grand-chose.
• Très instructif! mais quand même – Pourquoi O prononcé comme ‘ oh ‘ par les programmeurs?

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

Pour une compréhension de lanalyse de complexité, je pense que le lien publié par topgun_ivard est un Cest un bon point de départ. Un bon manuel dintroduction couvrant les structures de données ou les algorithmes pourrait également aider.

Commentaires

• I ‘ je suis désolé, mais la notation Bachmann-Landau a été inventée par un mathématicien allemand, donc je ne pense pas quil laurait nommée daprès un mot anglais. En fait, même si elle avait été inventée par mathématicien américain, il aurait probablement encore été nommé daprès un mot allemand, car quand il a été inventé (vers 1920, je pense), la langue internationale des mathématiques était lallemand. De plus, il ne le fait pas ‘ t même à distance nont rien à voir avec la complexité.
• @J ö rg: Oui, mais ‘ t ce nest que Ordnung , dont larticle du wiki allemand prétend être lorigine: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel pourriez-vous apporter une modification mineure à votre article afin que je puisse voter pour vous? Vous avez en effet raison. Vous devez modifier avant que je puisse voter.
• @Jonathan, je ‘ ne sais pas exactement quel changement mineur vous voulez. Pouvez-vous simplement continuer et apporter les modifications souhaitées? Ou, nous pourrions simplement laisser back2dos ‘ répondre, il semble quil aurait pu se retrouver avec la meilleure réponse de toute façon grâce à dexcellentes recherches 🙂
• Hm , intéressant. En Suède, Big Oh est généralement appelé  » ordo  » (en latin pour, enfin, ordre) plutôt que  » ordning  » (le mot suédois pour ordre).

O signifie 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 dabord 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 indiquer une grandeur dont lordre en référence à n ne dépasse pas lordre de n (…)

Contrairement à ce que dautres ont dit, rien dans son texte nindique quil sagit en fait dun omikron en majuscule grecque. Il utilise beaucoup de caractères grecs et latins, donc il ny a pas vraiment de moyen de le dire. Étant donné son utilisation continue de « Ordnung n log n  » etc. dans le texte, il est clair que cest signifie « Ordnung » (en allemand pour « ordre » sil y avait un doute) dans tous les cas, mais cela pourrait encore laisser ouverte lutilisation dun O grec sophistiqué.

Cependant, lorigine de lomikron est plus vraisemblablement 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 éventuellement Hardy et Littlewood qui ont introduit un symbole oméga plus tôt.

Commentaires

• Intéressant. Je suppose que tu as raison. Je viens de chercher les définitions dans les deux livres de Landau ‘ et Bachmann ‘, et ils ont en effet a) utilisent un latin Oh, pas un grec Omikron, b) les deux utilisent le mot  » Ordnung « , et c) Landau explicitement déclare que cela signifie  » Ordnung « . Je suis corrigé.
• Quel meilleur mot pourrait-on trouver? Je veux dire, dun Allemand? Ordnung ist das halbe Leben!
• Je pense que la première phrase de votre réponse (correcte, positive, géniale) devrait se lire: ‘ O signifie  » Ordnung  » (sens allemand  » Ordre « ) . ‘ Cela aiderait cette réponse à attirer lattention des autres lecteurs.

Jaime cet article , en espérant que vous le trouverez également utile!

Citant une section de larticle:
Big Greek Letters

Big O est souvent mal utilisé. Big O ou Big Oh est en fait labré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 quil existe deux constantes c1 et c2 telles que c1n log n < f (n) < c2n log n.

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

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

Quest-ce que Big O?

La notation Big O cherche à décrire la complexité relative dun algorithme en réduisant le taux de croissance à la clé facteurs lorsque le facteur clé tend vers linfini. Pour cette raison, vous entendrez souvent lexpression complexité asymptotique. Ce faisant, tous les autres facteurs sont ignorés. Cest une représentation relative de la complexité.

Quest-ce qui nest pas Big O?

Big O nest pas un test de performance dun algorithme. Il est également théorique ou abstrait en ce quil a tendance à ignorer dautres facteurs. La complexité de lalgorithme de tri est généralement réduite au nombre déléments triés comme étant le facteur clé. Cest bien, mais cela ne prend pas en compte les problèmes tels que:

Utilisation de la mémoire: un algorithme peut utiliser beaucoup plus de mémoire quun autre. Selon la situation, cela peut être quelque chose de complètement hors de propos à critique; Coût de la comparaison: il se peut que la comparaison déléments soit vraiment coûteuse, ce qui modifiera potentiellement toute comparaison réelle entre les algorithmes; Coût du déplacement des éléments: la copie d’éléments est généralement bon marché, mais ce n’est pas nécessairement le cas; etc.

Commentaires

• Le simple fait de lier un article nest ‘ trop utile. Il ‘ est généralement une bonne idée de paraphraser ou de citer la section que vous trouvez particulièrement pertinente pour le fil de discussion.
• Les votes négatifs sont-ils vraiment nécessaires? Larticle quil a lié est très pertinent et à mon humble avis très utile.Pendant ce temps, la réponse la plus votée est un lien vers un article de Wikipédia. +1 pour compenser lhypocrisie de lesprit-ruche.
• -1, parce que lartice, tout en étant un article très agréable et bien écrit, ne ‘ Je nai rien à voir avec la question.
• @Jorg, je nai jamais dit que larticle résoudrait le problème, mais jai partagé parce que je lavais trouvé utile lorsque je regardais ces concepts.
• @topgun_ivard: Que se passe-t-il donc sil se transforme en lien mort? La paraphrase permet 1) à laudience de ce fil dobtenir une version Coles notes de votre lien (le temps, cest de largent), et 2) garantit que votre message nest pas rendu inutile sur un lien mort.

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

En fait, ce nest pas la lettre latine Oh , cest la lettre grecque Omicron . Malheureusement, ces deux-là ont exactement le même glyphe, donc, avec le temps, la version originale a été corrompue, et maintenant cest juste Oh .

Le choix du symbole na en fait aucune signification particulière, il a été choisi comme dispositif mnémonique :

• Omicron contient les lettres MICRO, et la sémantique du symbole Omicron signifie à peu près «plus petit que»
• Omega contient les lettres MEGA , et la sémantique du symbole Omega signifie à peu près « plus grand que »
• Thêta (Θ) ressemble un peu à un signe égal , et la sémantique du symbole Thêta signifie à peu près «égal à»

Cest tout. Il ny a pas de sens réel, cest juste un jeu de mots, si vous Will, pour vous aider à vous rappeler la sémantique plus e Asily.

Commentaires

• Bien que jadorerais croire votre proposition mnémotechnique (cest une idée vraiment cool), je vais avoir besoin de voir une preuve que telle est la véritable intention originale de Bachmann. Fournissez-le, et je ‘ vous +1.
• @Jonathan Henson: Apparemment, jai été induit en erreur par le professeur Knuth 🙂

« f (x) est grand-oh de g (x) »

Cest une manière mathématique de prédire la croissance des fonctions.

Soit f et g des fonctions de lensemble des entiers ou de lensemble ou des nombres réels à lensemble des nombres réels. On dit que f (x) est O (g (x)) sil existe des constantes C et k telles que | f (x) | < = C | g (x) | où x> k.

Vous liriez ceci comme « f (x) est le grand-oh de g (x) »

Le grand-O est parfois appelé un symbole de Landau après le mathématicien allemand Edmund Landau. Je ne pense pas que cela représente quoi que ce soit au-delà de cela. Vous avez également les notations Big-Omega et Big-Theta similaires. Les symboles sont aussi arbitraires que lutilisation de thêta pour désigner les angles dans vos triangles était dans votre lycée Planar Geometry class.

Correction @ back2dos a fourni une explication satisfaisante de lO comme faisant référence à la commande. Excellent Job. Voir sa réponse.

Donald Knuth la 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

UPDATE: 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 signifie ordre (le premier ordre étant n le deuxième ordre étant n-carré, etc.) Et si je ne suis pas erroné, ce serait le pire des cas pour une méthode dexécution (ou de stockage) à N éléments. Plus lordre est grand, plus la méthode est mauvaise.
Par exemple, la recherche dun enregistrement dans un tableau est O (1) (je crois en une implémentation de tables de hachage qui est également le cas). Ajouter une valeur à la fin dune liste de liens serait O (N) car vous devez arriver à 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 🙂

Commentaires

• -1 parce que cest tout simplement incorrect et répond à une question distincte de celle qui a été posée. La question était de savoir pourquoi la lettre  » O  » utilisée, et non  » comment Big La notation O fonctionne-t-elle? « . Vous ‘ vous êtes incorrect sur le fonctionnement de Big-oh, bien que … boucler un tableau est O (n) où n est la taille du tableau, pas O (1) . La notation na rien à voir avec les  » cycles  » dun algorithme … il ‘ est une mesure de la limite supérieure du temps dexécution dun algorithme.
• Je ne veux pas discuter avec vous ici, mais cest le genre de ‘ que je voulais dire. Que signifie le temps dexécution?Eh bien, le temps dexécution est déterminé par ce qui doit être traité sur la machine. Je suppose que jutilise généreusement le cycle ici. Par cycle, je suppose que jaurais dû dire itérer ou quelque chose comme ça. Vous avez raison sur la limite supérieure, cela ne détermine pas la moyenne. Par conséquent, jaccepte le déclassement.