IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Bibliothèques Discussion :

[containers de STL]la signification de o(1),o(n)


Sujet :

Bibliothèques

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Août 2006
    Messages
    106
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Août 2006
    Messages : 106
    Par défaut [containers de STL]la signification de o(1),o(n)
    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

  2. #2
    Membre éprouvé Avatar de amaury pouly
    Profil pro
    Inscrit en
    Décembre 2002
    Messages
    157
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France

    Informations forums :
    Inscription : Décembre 2002
    Messages : 157
    Par défaut
    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.

  3. #3
    Alp
    Alp est déconnecté
    Expert confirmé

    Avatar de Alp
    Homme Profil pro
    Inscrit en
    Juin 2005
    Messages
    8 575
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : Juin 2005
    Messages : 8 575
    Par défaut
    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).

  4. #4
    Membre confirmé
    Profil pro
    Inscrit en
    Août 2006
    Messages
    106
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Août 2006
    Messages : 106
    Par défaut
    merci infiniment amaury pouly et Alp, c est mplus clair maintenant dans ma tete.
    merci encore une fois

  5. #5
    Rédacteur
    Avatar de Laurent Gomila
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2003
    Messages
    10 651
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2003
    Messages : 10 651
    Par défaut
    ?

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. les containers STL et leur contenu
    Par le_ptit_lutin dans le forum C++
    Réponses: 2
    Dernier message: 31/12/2011, 17h00
  2. Réponses: 1
    Dernier message: 24/08/2011, 01h01
  3. visiteur sur elements d'un container STL
    Par donkeyquote dans le forum C++
    Réponses: 2
    Dernier message: 10/11/2007, 20h09
  4. replication d'objet dans un container STL
    Par istdasklar dans le forum SL & STL
    Réponses: 12
    Dernier message: 15/05/2007, 23h04
  5. [Kylix] [BCB] pb avec la STL
    Par pykoon dans le forum EDI
    Réponses: 1
    Dernier message: 29/12/2002, 12h56

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo