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:

---

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.

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ï

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:

---

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.

merci infiniment jedai, had35 j'ai bien compris

amicalement