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é d'un algo


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Inscrit en
    Juillet 2006
    Messages
    14
    Détails du profil
    Informations forums :
    Inscription : Juillet 2006
    Messages : 14
    Par défaut complexité d'un algo
    bonjour,

    j'ai lu dans mon cours que la complexité dans le cas le plus défavorable de l'algo en dessous est de l'ordre de 2^n mais je n'arrive pas à comprendre pourquoi??

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      int valmax(int i)
      {
        if (i==0) return T[0];
        else {
          if (T[i]>valmax(i-1))
             return T[i];
          else return valmax(i-1); 
       }
     
      }
    avec T est un tableau d'entiers et la fonction valmax est appelée avec le dernier indice du tableau.

    P.S: le cas le plus défavorable correspond à un tableau trié en ordre décroissant.

    merci d'avance de vos aides.

  2. #2
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Ben tu comptes : dans le cas le plus défavorable, à chaque valmax(i) correspondent 2 valmax(i-1), donc à valmax(n) correspondent 2 valmax(n-1), soit 4 valmax(n-2), 2^3 valmax(n-3), et finalement 2^n valmax(0)...
    Algorithme complètement débile illustrant bien les dangers des appels inutiles ! En mémorisant la valeur de valmax(i-1) et donc en ne faisant qu'un appel au lieu de deux, on retombe en complexité linéaire O(n)... alors qu'en étant un peu parresseux on se retrouve avec de l'exponentiel, comme ici.

    --
    Jedaï

  3. #3
    Membre expérimenté
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    194
    Détails du profil
    Informations personnelles :
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations forums :
    Inscription : Juin 2006
    Messages : 194
    Par défaut
    Salut,

    Je n'y connais pas grand chose en algo mais je pense que mes questions pourront aussi éclairer dell__k.

    Partons du code :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    1: int valmax(int i)
    2:    {
    3:       if (i==0) return T[0];
    4:       else {
    5:          if (T[i]>valmax(i-1))
    6:          return T[i];
    7:       else return valmax(i-1); 
    8:    }
    9: }
    Et de cette déclaration :

    Citation Envoyé par Jedai
    Ben tu comptes : dans le cas le plus défavorable, à chaque valmax(i) correspondent 2 valmax(i-1)
    Est-ce que je me trompe en disant que tu conclus ceci en disant que l'instruction ligne 5 implique une récursion, et que si cette récursion retourne une valeur inférieure à T[i], cela impliquera une deuxième récursion ligne 7 ?

    Je devine intuitivement que ça doit être ça, mais je voudrais savoir si mon raisonnement est correcte et si il existe une méthode plus rigoureuse de déterminer la complexité d'un algo.

  4. #4
    Membre averti
    Inscrit en
    Juillet 2006
    Messages
    14
    Détails du profil
    Informations forums :
    Inscription : Juillet 2006
    Messages : 14
    Par défaut
    merci infiniment jedai, had35 j'ai bien compris

    amicalement

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

Discussions similaires

  1. Aide sur complexité de cet algo
    Par laureat dans le forum Débuter
    Réponses: 4
    Dernier message: 18/09/2009, 13h33
  2. complexité de l'algo QuickSort
    Par t-student dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 17/03/2008, 18h24
  3. [Complexité] Résolution d'une équation de récurrence (algo d'arbre)
    Par sjrd dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 01/12/2007, 11h59
  4. [complexité algo] recurrence avec changement de variable
    Par rvfranck dans le forum Algorithmes et structures de données
    Réponses: 26
    Dernier message: 13/10/2007, 19h15
  5. Complexité pire-cas et meilleur-cas de mon algo
    Par sorry60 dans le forum Algorithmes et structures de données
    Réponses: 14
    Dernier message: 16/10/2006, 16h45

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