Discussion :

[del__k]

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.

[Jedai]

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ï

[had35]

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 :

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.

[del__k]

merci infiniment jedai, had35 j'ai bien compris

amicalement