Discussion :

[dalhia]

bonjour
j'ai besoin de comprendre la signification de o(1) et o(n).
en effet je dois faire un exposé sur la bibliothéque STL, pour cela je suis en train de lire des documents sur les conteneurs de STL, notamment le vector mais je n'arrive pas à comprendre la signification de ces symboles(o(1) et o(n)) et voila le contexte où je trouve probléme:

Leurs principales caractéristiques de vector sont les suivantes :
- Accès indexé aux éléments en O(1)
- Ajout ou suppression d’un élément à la fin du vecteur sans
redimensionnement en O(1)
- Ajout ou suppression d’un élément à la fin du vecteur avec
redimensionnement en O(n)
Ajout ou suppression d’un élément à la fin du vecteur en O(1) amorti
-Ajout ou suppression d’un élément au milieu du vecteur en O(n) où n est la
taille du vecteur

merci d'avance

[amaury pouly]

La notation O (lire 'grand O' et qui est différente de la notation o) indique une borne asymptotique pour l'exécution de la fonction.
En termes plus clair cela veut dire que:
-O(1): quelque soit le nombre d'élément du conteneur, la fonction prend un temps constant pour s'exécuter
-O(n): si le conteneur contient n élement, la fonction prend un temps proportionnel à n pour s'écuter mais ce facteur de proportionnalité de dépend pas de n !
-O(1) amorti: là c'est plus compliqué, cela veut dire que si tu exécute cette fonction un très grand nombre de fois, la moyenne des temps d'exécution de la fonction est constante même si son temps d'execution peut en réalité varier d'un appel à un autre.

J'espère que ma réponse est claire.

[Alp]

Petit commentaire sur le O(n) :
Si tu fais la boucle for suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
for(int i = 0; i < n; i++)
{
cout << 2*n << endl;
// ou printf en C
}

La durée d'exécution dépend entièrement de n, proportionnellement. C'est un exemple de code de complexité O(n).

[dalhia]

merci infiniment amaury pouly et Alp, c est mplus clair maintenant dans ma tete.
merci encore une fois

[Laurent Gomila]

?