Niveau Master

Complexité

Posté par
minou2000 19-01-17 à 22:08

Bonjour,

Je voudrais calculer la complexité (le nombre de fois l'algorithme calcule la ligne 7 )

On commence par CALCUL1 (T,1,n)

$Fonction CALCUL1 (T,n1,n2)\\ 1. Pour ~~i = n1+1 ~~~à ~~ n2-1 faire\\ 2. T[i]:=T[i-1]+T[i+1];\\ 3. n := n2-n1+1;\\ 4. si ~~ n \ge 2 faire\\ 5. u := CALCUL1 (T,n1,n2-1);\\ 6. v := CALCUL1 (T, n1+ , n2)\\ 7. retourner~~ la valeur ~~u+v;\\ 8. sinon ~~retourner~~ la ~~valeur 1;\\$

Je trouve

$f(n)= 2 f(\frac{n}{\frac{n}{n-1}})-cn^0 donc~~ f(n) \in \theta (n^{\log_{\frac{n}{n-1}} 2})$

Je ne sais pas si c'est juste ou pas

Posté par re : Complexité 20-01-17 à 00:58

Bonsoir.

Comme les modifications de T ne semblent pas t'intéresser dans le calcul de la complexité, on peut réécrire ta fonction sous la forme


CALCUL2(n1,n2)
1  Si n2-n1>=1
2      alors
3        u:=CALCUL2(n1,n2-1)
4        v:=CALCUL2(n1+1,n2)
5        retourne u+v
6      sinon
7        retourne 1

On peut compter le nombre d'appels de la fonction CALCUL2 assez facilement.
Quand on passe de CALCUL2(1,n) à CALCUL2(1,n+1) on multiplie par deux le nombre d'appels.
Et on a évidement un seul appel à cette fonction pour CALCUL2(1,1).

On a donc 2^n-1 calculs de ma ligne 5 ou, ce qui revient au même, de ta ligne 7.