Licence Info
Algorithmique Avancée
TD 8 : novembre 2005
Analyse du temps de calcul

Déterminer (en fonction de n à O( ) près) le temps de calcul de chaque boucle :
(P() est une procédure dont le temps de calcul est constant ; et deux(i) calcule la i-ème puissance de 2 en temps constant.)

  1. pour i allant de 1 a n par pas de 1 faire P() finpour;

  2. pour i allant de 1 a n par pas de 1 faire 
    pour j allant de 1 a i par pas de 1 faire P() finpour
    finpour;

  3. i:=1;
    tant que i<n faire i:=i*2
    fintantque;

  4. pour i allant de 1 a n par pas de 1 faire 
    j:=1;
    tant que j<n faire j:=j*2
    fintantque
    finpour;

  5. i:=1;
    tant que i<n faire
    i:=i*2;
    pour j allant de 1 a i par pas de 1 faire P() finpour
    fintantque;

  6. i:=1;
    pour j allant de 1 a n par pas de 1 faire i:=i*2 finpour;
    pour j allant de 1 a i par pas de 1 faire P() finpour;

  7. i:=1;
    pour k allant de 1 a n par pas de 1 faire
    i:=i*2;
    pour l allant de 1 a i par pas de 1 faire
    pour m allant de 1 a k faire P() finpour
    finpour
    finpour;

  8. pour k allant de 1 a n par pas de 1 faire
    i:=1;
    pour j allant de 1 a k par pas de 1 faire i:=i*2 finpour;
    pour j allant de 1 a i par pas de 1 faire P() finpour
    finpour;

  9. i:=2;
    tant que i<n faire i:=i*i
    fintantque;

  10. i:=1;
    tant que i<n faire i:=deux(i)
    fintantque;




File translated from TEX by TTH, version 3.05.
On 22 Nov 2005, 10:19.

symboles bricolés pour netscape par sed