Qu'est-ce que O dans Big O?

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 ?

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.

"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.

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.

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.

"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

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.

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 :)