Les règles de calculs de la complexité d'un algorithme:

Pour calculer la complexité, Il faut examiner chaque ligne de l'algorithme  et l'y attribuer un coût en temps.

1.Les actions élémentaires:

Une action ( opération) élémentaire est une opération dont le temps d’exécution est indépendant de la taille n des données tel que l’affectation, la lecture, l’écriture, la comparaison ...etc.

Le coût ainsi obtenu n'aura pas d'unité, il s'agit d'un nombre d'opérations dont chacune aurait le même temps d'exécution Les opérations qui vont devoir être comptabilisées auront les coûts suivant :

  • Les affectations comptent pour 1 unité de temps :

                     a←2

  • Les comparaisons (comme les tests) comptent pour 1 unité de temps :

                     2<3

  • L'accès aux mémoires comptent pour une 1 unité de temps :

                   Lire(x)

  • Affichage des données

                écrire(x)

  • Chaque opération élémentaire comptent pour une 1 unité de temps :

                  a+b ; c*d ;

La complexité d'une action élémentaire est dite constant. 

On notera ce type de coût constant : 

Exemple :
Déterminons le coût  des actions suivantes :

a←1 ;
b←2 ;
a←a+b ;
Le coût, notée est : (pour a←1) + 1 (pour b←2) + 1 ( pour a+b) +1 (pour a←) = 4

on note la complexité de cette suite : 

2. La multiplication par une constante :

O(c f (n)) = O(f (n)

Exemple :

O( 5/2 n2 )= O(n2)

3. Les actions de contrôle :
Supposons que l’on ait un bloc de la forme : 
si condition alors
                      actions1 
                    sinon 
                      actions2 
La complexité de ce bloc est :
est le maximum entre les complexités de l’évaluation de <Condition>, actions1  et actions2

                   O(O(condition))+max(O(actions1),O(actions2)

   

La complexité de la conditionnelle est : Max {O(h(n)), O(f (n)), O(g(n))}

4. Les actions de répétition ( les boucles) :

Dans les boucles ,La difficulté est d’estimer le nombre d’itérations. On cherche uniquement un majorant du nombre d’itérations.
Elle est égale à la somme sur toutes les itérations de la complexité du corps de la boucle.

La complexité de la boucle est : m * Max(g(n),f (n)) où m est le nombre d’itérations exécutées par la boucle

5. Actions de plusieurs modules :
La complexité d’une  séquence de  deux  modules  M1  de  complexité  O(f (n))  et  M2 de complexité O(g(n)) est égale à la plus grande des complexité des deux modules : O(max(f (n),  g(n))).
O(f (n)) + O(g(n)) = O(max(f (n), (g(n))
6- Complexité des algorithmes récursifs
 La complexité d’un algorithme récursif se fait par la résolution d’une équation de récurrence en éliminant la récurrence par substitution de proche en proche.
Exemple :
Soit la fonction suivante :

Posons T (n) le temps d’exécution nécessaire pour un appel à Fact(n), T (n) est le maximum entre :
–    la complexité du test n<=1 qui est en O(1),
–    la complexité de : retourner 1 qui est aussi en O(1),
–    la complexité de : retourner  n*Fact(n - 1) dont le temps d’exécution dépend de T (n-1)
 Alors la fonction de temps peut être écrite comme suit:
T(n)= 2 si ( n<=0)                              2    1 pour le test  et 1 pour retourner 1
T(n)= a + T(n-1)                   a : temps d'execution de test et de * entre n et fact(n-1)
le calcul de T(n-1) revient à calculer T(n-1)
T(n)=a+T(n-1)
      =a + a +T(n-2) = 2a+T(n-2)
      =a+a+a+T(n-3) = 3a+T(n-3)
..........
    =a+a+....+a + T(n-(n-1))= (n-1)a+T(1) = (n-1)a+2 = an-a+2  donc la fonction Fact a une complexité d'ordre O(n)


Modifié le: mercredi 16 novembre 2022, 20:48