Licence Info Licence Info
Algorithmique Avancée
TD 8 : novembre 2006
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;
    
    
  11. i:=0;j:=0;
    tant que j<n faire
       i:=i+1;
       j:=j+i;
    fintantque;
    
    
    
  12. pour i de 1 a n faire T[i]:=0 finpour;
    j:=0;
    tant que j<n faire
       j:=1;
       tantque T[j]=9 et j<n faire
          T[j]=0;
          j:=j+1;
       fintantque;
       T[j]:=T[j]+1
    fintantque;
    
    
    




File translated from TEX by TTH, version 3.05.
On 28 Nov 2006, 10:26.