Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Compléxités, Borne supérieur.

Posté par
titi12
05-11-19 à 19:36

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 .

Posté par
carpediem
re : Compléxités, Borne supérieur. 05-11-19 à 19:52

salut

tu as une boucle implicite :

i = n
while
   ...
   i = n/2

imagine que n = 2^p ...

Posté par
titi12
re : Compléxités, Borne supérieur. 05-11-19 à 20:26

Ah d'accord ducoup si n = 2^p on obtient une compléxité n log(n) ?

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


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

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 !