Bonjour à tous , voila je commence la complexité et je voudrais comprendre la méthode pour réussir cette exercice:
Considérons le morceau M de code suivant.
i = n;
while (i > 1){
if (a[i] > 0)
P;
else
Q;
i = i/2;}
(a) Calculer une borne supérieure du temps d'exécution TM(n) de M en fonction de n, en supposant que P soit O(f(n)) et Q soit Q(g(n)) pour deux fonctions positive croissantes f(n) et g(n).
(b) Calculer la borne supérieure dans le cas particulier où f(n) = n et g(n) = n².
Ici je pense qu'il faut faire :
1) O( max( f(n),g(n)) et que donc f(n) = n et g(n) = n² ainsi TM(n) = O(n²) .
2) je ne sait pas trop.
Merci pour votre aide .
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :