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

Algorithmes et structures de données Discussion :

Complexité algorithmique d'un tableau trié


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    ceo
    Inscrit en
    Août 2005
    Messages
    62
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : ceo

    Informations forums :
    Inscription : Août 2005
    Messages : 62
    Par défaut Complexité algorithmique d'un tableau trié
    Bonjour,

    j'aimerais comprendre pourquoi la complexité de l'algorithme de suppression d'un tableau trié (O(n)) n'est pas la même que pour l'algorithme de recherche (O(log n)) alors que pour un tableau non trié, la complexité est la même (O(n)).
    Merci d'avance à qui pourra m'éclairer

  2. #2
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Le problème n'est pas de trouver l'élément O(N), mais après l'avoir supprimé O(1) il faut décaler tout les éléments suivants O(N).
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Membre confirmé
    Profil pro
    ceo
    Inscrit en
    Août 2005
    Messages
    62
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : ceo

    Informations forums :
    Inscription : Août 2005
    Messages : 62
    Par défaut
    merci pour ta réponse, donc si je comprends bien quand on dit supprimer un élément c'est supprimer n'importe quel élément, le premier qui vient (et ensuite replacer les autres)?

  4. #4
    Membre Expert Avatar de DonQuiche
    Inscrit en
    Septembre 2010
    Messages
    2 741
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 2 741
    Par défaut
    Ce qu'il veut dire c'est que pour supprimer un élément d'un tableau il faut déplacer les éléments qui viennent après. Il y a donc entre 0 et N éléments à déplacer, soit N/2 en moyenne. Donc O(n).

    Si tu veux supprimer "toto" d'une liste de chaînes, d'abord tu fais une recherche, ensuite tu déplaces les éléments après toto. La recherche est en O(n.ln(n)) mais le déplacement est en O(n). La complexité totale est donc en O(n).

  5. #5
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Citation Envoyé par DonQuiche Voir le message
    Si tu veux supprimer "toto" d'une liste de chaînes, d'abord tu fais une recherche, ensuite tu déplaces les éléments après toto. La recherche est en O(n.ln(n)) mais le déplacement est en O(n). La complexité totale est donc en O(n).
    Dans une liste, la recherche est en O(N) et le suppression en O(1), donc O(N) au final.


    Citation Envoyé par simnitch Voir le message
    merci pour ta réponse, donc si je comprends bien quand on dit supprimer un élément c'est supprimer n'importe quel élément, le premier qui vient (et ensuite replacer les autres)?
    On prend toujours le cas le plus défavorable. Dans le cas d'un tableau, c'est supprimer le premier élément, car il faut ensuite déplacer TOUS les autres éléments.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  6. #6
    Membre Expert Avatar de DonQuiche
    Inscrit en
    Septembre 2010
    Messages
    2 741
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 2 741
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Dans une liste, la recherche est en O(N)
    Liste triée puisque c'était ce dont on parlait.

    Citation Envoyé par ToTo13 Voir le message
    On prend toujours le cas le plus défavorable. Dans le cas d'un tableau, c'est supprimer le premier élément, car il faut ensuite déplacer TOUS les autres éléments.
    Non, on ne prend pas toujours le cas le plus défavorable. En général le plus défavorable et le moyen ont le même comportement asymptotique, soit O(n) ici, donc on ne fait pas de distinction. S'ils ne sont pas identiques, la distinction doit être faîte explicitement.

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

Discussions similaires

  1. [Tableaux] Affichage valeur d'un tableau trié
    Par kcizth dans le forum Langage
    Réponses: 1
    Dernier message: 05/01/2006, 15h47
  2. Réponses: 6
    Dernier message: 05/01/2006, 14h23
  3. tableau trié
    Par devdébuto dans le forum C
    Réponses: 3
    Dernier message: 07/11/2005, 18h00
  4. [Tableau][TRI] Tri d'un String[]
    Par zakir dans le forum Collection et Stream
    Réponses: 2
    Dernier message: 17/03/2005, 17h31
  5. URGENt: recherche dans un tableau trié par ordre alphabetiqu
    Par JulPop dans le forum Général JavaScript
    Réponses: 4
    Dernier message: 12/02/2005, 17h21

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