Analyse de la complexité d’un algorithme

Plan de la séquence

  • Introduction
  • Définitions
  • La complexité asymptotique
  • Notation grand O
    • Définition
    • Exemple
    • Règles de simplification
  • règles pour calculer la complexité
  • Les classes de calcule
  • Un Exemple réel (tri)
    • Algorithme Rapide VS Algorithme lent

 Problème !

Nous avons : Un enfant, un étudiant, un professeur

Leurs Objectif : trouver un mot dans un dictionnaire !

Leurs ressources

Introduction

  • C’est quoi un algorithme ?
    • Une succession d’instructions qui renvoie un résultat, afin de résoudre un problème.
  • Quel est l’environnement d’un algorithme ?
C'est quoi un algorithme ?
Une succession d’instructions qui renvoie un résultat, afin de résoudre un problème.
  • Comment juger un algorithmes ? Quel critères ?
    • Usage des ressources
      • En informatique (Mémoire, CPU, Temps )
  • C’est quoi une complexité ?
    • La complexité = une mesure (exemple : mètre, Litre, hectare, …)
      • Pour  comparer les algorithmes
        • Pour dire quelle algorithme est la moins complexe
          • Pour  dire que cette algorithmes est la plus efficace

Definitions

  • C’est quoi l’analyse de la complexité d’un algorithme?
    • Etudier formellement la quantité de ressources en temps (complexité temporelle) et en espace (complexité spatiale) nécessaires pour l’exécution d’un algorithme donnée.
    • Le nombre d’opérations élémentaires (affectation, comparaison, …) affectées par un algorithme. (retenez « n »)
  • C’est quoi la l’efficacité d’un algorithme ?
    • C’est l’usage du minimum des ressources
      • Le Meilleur  algorithme = le plus  efficace = le moins complexe l
  • Comment évaluer l’efficacité d’un algorithme ?
    • Approche dépendante des facteurs matériaux
    • Approche indépendante des facteurs matériaux

La complexité asymptotique

  • La complexité exacte d’un algorithme est plus difficile à déterminer. On ne s’intéresse qu’à la complexité dite asymptotique.
  • La complexité asymptotique d’un algorithme décrit le comportement de celui-ci quand la taille n des données du problème traité devient de plus en plus grande, plutôt qu’une mesure exacte du temps d’exécution.
  • Une notation mathématique, permettant de représenter cette complexité asymptotique c’est la notation grand O.

Notation grand O

Notation grand O - Analyse de la complexité d'un algorithme

Signification: Pour toutes les grandes entrées  (i.e., n >= n0), on est assuré que l’algorithme ne prend pas plus de Cg(n) étapes.

−Exemple

  f(n) = 3n2 +2n + 1.                                      => On a : f(n) = O(g(n)).

  g(n) = n2.

Grand-O: Exemple

Exemple 1: Initialiser un tableau d’entiers

  for (int i=0; i<n; i++) Tab[i]=0;

Supposons que chaque itération nécessite un temps <= c,

 où c est une constante (accès au tableau + une affectation).

Il y a n itérations

Le temps est donc T(n) <= cn

Donc T(n) = O(n)

Grand-O: Règles de simplification

  • Si f(n) = O(g(n)) et g(n) = O(h(n)),         

       alors f(n) = O(h(n)).

  • Si f(n) = O(kg(n)) où k > 0 est une constante,

        alors f(n) =O(g(n)).

  • Si f1(n) = O(g1(n)) et f2(n) = O(g2(n)),

          alors (f1 + f2)(n) = O(max(g1(n), g2(n))).

  • Si f1(n) = O(g1(n)) et f2(n) = O(g2(n)),  alors f1(n)f2(n) = O(g1(n) g2(n)).

Règles pour calculer la complexité d’un algorithme

  • Règle 1: 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).
  • Règle 2: Instruction if:

maximum entre le then et le else.

Règle 3: Instructions de répétition: 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.

Règles de calcule : Exemples

Exemple 1: a = b; => Temps constant: O(1).

Exemple 2:

somme = 0; 
for (i=1; i<=n; i++)                   => Temps: O(n)
   somme += n;

Exemple 3:

somme = 0;
for (j=1; j<=n; j++)
  for (i=1; i<=n; i++)
  somme++;                          => Temps: O(1) + O(n²) + O(n) = O(n²)
for (k=0; k<n; k++)
  A[k] = k;

Les principals classes de complexité

Exemple de classe de complexité

Complexité : O(1) - (Exemple  fonction de permutation)

Fonction  permutation (S, i, j)
var ← tab[i] ;  coût C1 =1
tab[i] ← tab[j] ;  coût C2 = 1
tab[j] ← var ;  coût C3 = 1
Retourner S

Complexité :
T(n)=C1+C2+C3
T(n)=1+1+1=O(1)
complexité :  O(n) - (Exemple fonction de Recherche)

Fonction Rechercher(x, S, n)
I <-- 1 ; C   coût c1=1
Tant que ((I<=n) et (S[I] = ! x)) faire
{
  I=I+1 ;     coût c2=1
}
Retourner S ;    coût c3 =1

Complexité :
T(n)=C1+ ∑1_(i=1)^n▒〖C2+C3〗
T(n)=1+ ∑1_(i=1)^n▒〖1+1)〗
 T(n)=1+n+1=O(n)
complexité :  O(n2) - (Exemple fonction de tri)

Fonction tri (S, n)
Pour i=n à 2 faire   (n-1 fois)
Pour j=1 à i-1 faire    (i-1 fois) 
Si(S[j] > S[j+1]) alors
Permuter S[j] et  S[j+1] dans S     C_perm  (Cout de permutation)
Complexité :
 T(n)=C_perm∗ ∑1_(i=0)^(n-1)▒i
         =C_(perm )∗(n∗(n-1))/2
         =C_(perm )∗(n^2-n)/2
          =C_(perm )∗n^2/2  -C_(perm )∗n/2

        =C_(perm )∗n^2/2  -C_(perm )∗n/2
         =O(n^2)
Rappel :
∑1_(i=0)^(n-1)▒〖i =(n∗(n-1))/2=O(n^2)〗
classe de complexité algorithme

/* Exemple */
Un algorithme
VS Un algorithme
Tri par fusion VS Tri par sélection

Tri par fusion (rappel)

Objectif:

  trier les valeurs d’un tableau

Principe de l’algorithme :

  « diviser pour régner »

Démarche:

1.diviser (virtuellement) le tableau de départ en deux sous-tableaux, et ainsi de suite, jusqu’à n’avoir qu’un seul élément.

2.fusionne chaque deux éléments en un tableau trié

L’algorithme de tri par fusion

L’algorithme de tri par fusion

Rappels – règles

Démonstration

Démonstration la complexité de notre algorithme de tri par fusion

Tri par sélection (rappel)

Sur un tableau de n éléments (numérotés de 1 à n), le principe du tri par sélection est le suivant :

  • rechercher le plus petit élément du tableau, et l’échanger avec l’élément d’indice 1 ;
  • rechercher le second plus petit élément du tableau, et l’échanger avec l’élément d’indice 2 ;
  • continuer de cette façon jusqu’à ce que le tableau soit entièrement trié.

L’algorithme de tri par sélection

PRODECURE Tri_Selection (Tableau a[1:n])
 VARIABLE indice_max : ENTIER;
      POUR i VARIANT DE 1 A n-1 FAIRE
            indice_max <- i;
            POUR j VARIANT DE i+1 A N FAIRE
                    SI a[j]<max ALORS indice_max <- j;
            FIN POUR
            echanger a[i] et a[indice_max];
      FIN POUR
FIN PROCEDURE

Telecharger PDF