Blog

Objectifs du cours

• pouvoir prévoir le temps d’exécution d’un algorithme
• pouvoir comparer deux algorithmes réalisant le même traitement
• Elaborer des algorithmes performants et efficaces

Théorie de la complexité

• Informatique théorique
• Problème algorithmique
• Réponse algorithmique
• Complexité d’un problème algorithmique

Une analyse

lPourquoi faire ?

Soit T un tableau de n entiers que l’on désire trier dans l’ordre croissant. On suppose que l’on dispose de deux algorithmes permettant de réaliser ce travail :

Analyse

l’algorithme 1 triant le tableau en n2 opérations,

– l’algorithme 2 triant le tableau en n log2 n opérations,

Pour exécuter nos deux algorithmes , on dispose de deux machines :

– M1 capable d’effectuer 229 opérations par seconde (Pentium III 450),

– M2 capable d’effectuer 225 opérations par seconde (486 DX 33),

L’algorithme 1 est exécuté sur M1 et l’algorithme 2 sur M2. Le tableau `a traiter comporte 220 entiers. Les temps d’execution sont les suivants :

. Algo 1 / M1 : (220)2/229 secs. = 211 secs. ≃ 34 minutes

. Algo 2 / M2 : (220 × 20)/225 secs. = 0.625 secondes !

Moralité : il ne suffit pas d’avoir une machine puissante, encore faut-il développer de bons algorithmes !

Efficacité

       C’est une mesure des ressources nécessaires à mettre en œuvre pour que le programme produise les résultats attendus

Complexité des algorithmes 

Mesure de l’efficacité d’un programme pour un type de ressources

• Complexité spatiale (Mémoire)
• Complexité temporelle ( CPU)

Complexité spatiale

Types de mesures

• La complexité au pire : notée par tmax(n) temps d‘exécution maximum, dans le cas le plus défavorable.
• La complexité au mieux : notée par tmin(n) temps d‘exécution minimum, dans le cas le plus favorable
• La complexité au moyenne: notée par tmoy(n) ) représentant  la complexité de l’algorithme dans le cas moyen en fonction du paramètre n

Recherche séquentielle

 fonction recherche(tab,C:entiers):entier
debut
   i:entier
   i <- 0
 tant que (i<n && tab[i] != C )
             i <- i+1
  if (i == n)
    returne(0)
  else returne(i)
finTantque

Types de mesures

        on ne considère souvent que la complexité au pire de cas  ????

• Pour ne retenir que les caractéristiques essentielles d’une complexité, et rendre ainsi son calcul simple (mais indicatif!), il est légitime d’ignorer  toute constante pouvant apparaître lors du décompte du nombre de fois qu’une instruction est exécutée et on a supposé aussi que les opérations d’affectation, de test et d’addition ont des temps constants.
• Le résultat obtenu à l’aide de ces simplifications représente  la complexité asymptotique de l’algorithme considéré.

      Ainsi, si      tmax(n) = (n+1)e + na + (2n+2)t

la complexité de cet algorithme est tout simplement en  n.

Notation grand-O()

Une notation mathématique, permettant de représenter cette façon de procéder, est dans ce qui suit: Notation grand-O()

ORDRES DE GRANDEUR : COMPARAISON D’ALGORITHMES

• Approximations des complexités
• Ordre de grandeur asymptotique

    Définition : Soient f et g deux fonctions de N dans  R+,

   f = O(g) si et seulement si il existe c   

   dans R+, il existe n0 dans N tel

   que quelque soit n > n0, f(n) £ c. g(n).

Quelques règles pour calculer la complexité d’un algorithme

1: la complexité d’un ensemble d’instructions est la somme des complexités de chacune d’elles.

2: Les opérations élémentaires telle que l’affectation, test, accès à un tableau, opérations logiques et arithmétiques, lecture ou écriture d’une variable simple … etc, sont en O(1)

3. la complexité de la boucle for est calculée par la complexité du corps de cette boucle multipliée par le nombre de fois qu’elle est répétée.

  4. En règle générale, pour déterminer la complexité d’une boucle while, il faudra avant tout déterminer le nombre de fois que cette boucle est répétée, ensuite le multiplier par la complexité du corps de  cette boucle.

Règle 5: Procédure et fonction: leur complexité est déterminée par celui de leur corps. L’appel à une fonction est supposé prendre un temps constant en  O(1)

Notons qu’on fait la distinction entre les fonctions récursive et celles qui ne le sont pas: lDans le cas de la récursivité, le temps de calcul est exprimé comme une relation de récurrence.

On peut alors classifier les complexités

• O(1) dite complexité constante
• O (log N) dite complexité logarithmique : recherche  dichotomique
• O (N) dite complexité linéaire fonction factorielle, passage par boucle
• O (n×log(n)) dite complexité quasi-linéaire: tri rapide
• O (N²) dite complexité quadratique: tri à bulles

 Recherche dichotomique

Fonction Factorielle

    factorielle2(entier n):entier
début
si (n = 1) alors
retourne 1;
sinon
retourne n*factorielle2(n-1);
Finsi
fin

L’équation récurrente s’exprime comme suit :

T(0) = 0
   T(n) = 1 + T(n-1), T(n) = k + T(n-k)
    Donc T(n)= ∑_(i=1)^(i=n)1 + T(0) = n + 0 = n
                                 O(n)=n

Exercice

     – Soient x un nombre réel et n un entier positif.

     – On veut calculer x^n=et l’on      s’interesse au nombre de multiplications

Algorithme

Fonction power(x, n : entiers) : entier
    Var i, r ,n: entiers;
    Debut
    r ← x;
    Pour i ß 0 jusqu’à n -1faire
    r ← r * x;
    FinPour
    Return(r);
    Fin

Correction

    L’algorithme se termine et calcul x^n 

    pour tout n≥1 et tout réel x. Il

    effectue n − 1 = O(n) multiplications.

Telecharger PDF