Inscription / Connexion Nouveau Sujet
Niveau Master
Partager :

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
verdurin
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 2n-1 calculs de ma ligne 5 ou, ce qui revient au même, de ta ligne 7.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1694 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !