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;

    Réponse O(n)
  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;

    Réponse O(n2)
  3. i:=1;
    tant que i<n faire i:=i*2
    fintantque;

    Réponse O(log(n))
  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;

    Réponse O(nlog(n))
  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;

    Réponse O(n)
  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;

    Réponse O(2n)
  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;

    Réponse O(n2n)
  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;

    Réponse O(2n)
  9. i:=2;
    tant que i<n faire i:=i*i
    fintantque;

    Réponse O(loglog(n))
  10. i:=1;
    tant que i<n faire i:=deux(i)
    fintantque;

    Réponse O(log*(n))




File translated from TEX by TTH, version 3.05.
On 1 Dec 2005, 11:11.

symboles bricolés pour netscape par sed