Cours 1 : Complexité des algorithmes

Définition

La complexité d'un algorithme est la quantité de ressources nécessaire à son exécution.
En général, on étudie le temps d'exécution.

Analyser la complexité d'un algorithme, c'est estimer le nombre d'opérations élémentaires en fonction de la taille de l'instance, dans le pire des cas.

Exemple : problème du plus court chemin

Algorithme "Brute force" : génère tous les chemins → complexité \(O(2^n)\)
Algorithme de Dijkstra : très efficace → complexité \(O(n^2 \log(n))\)

Nombre de stations	\(2^n / 10^9\) (Brute Force)	\(n^2 \log(n) / 10^9\) (Dijkstra)
10	10⁻⁹	2.3·10⁻¹⁰
20	10⁻⁶	10⁻⁹
30	3·10⁻³	3·10⁻⁹
50	1.1·10³	9.7·10⁻⁹
100	1.3·10¹⁸	10⁻⁸

I. Taille de l'instance

La taille de l'instance désigne la quantité de mémoire nécessaire pour stocker les données en entrée de l'algorithme.


int maxTab(int tab[], int size){
  int indMax = 0;
  for(int i = 1; i < size; i++){
    if (tab[i] > tab[indMax]){
      indMax = i;
    }
  }
  return indMax;
}

L'algorithme maxTab effectue plus d'opérations lorsque le tableau est plus grand.
La complexité est donc exprimée en fonction de la taille de l'instance.
Un tableau de n éléments → taille = n
Un entier n → taille = n
Un arbre d'ordre n → taille = n
Un graphe → taille dépend du nombre de nœuds et arêtes/arcs

II. Nombre d'opérations élémentaires

Les opérations élémentaires sont les plus simples :

déclaration, affectation
opérateurs arithmétiques : +, -, *, /, %
opérateurs booléens : ==, <, >
opérateurs logiques : ||, &&
appel de fonction, return

Exemple 1


int algo1 (int a, int b){
  int num = 0;         // 1 déclaration, 1 affectation
  num = 2*a+b;         // 1 addition, 1 multiplication, 1 affectation
  return num+4*b;      // 1 addition, 1 multiplication, 1 return
}

Total : 7 opérations → Complexité : \(O(1)\) (constante)

Exemple 2


int algo2(int a, int b){
  int c = 10;           // 1 déclaration, 1 affectation
  if (a == 0){          // 1 test
    if (b >= 13){     // 1 test
      if (c-b == -3){   // 2 opérations, 1 test
        printf("un appel\n");  // 1 appel
      }else{
        printf("un appel\n");  // 1 appel
      }              
    }
  }
}

Total : 9 opérations max, avec la structure if/else → 8 opérations au maximum

III. Structures itératives/récursives et sommes finies

Exemple 3


void algo3(int n){
  for(int i=0; i < n; i++){  
    if(i%2 == 0){
      printf("%d est pair\n", i);
    }
  }
}

Boucle for de 0 à n-1 → par itération : 3 (boucle) + 2 (if) + 1 (printf) = 6 opérations → \(\sum_{i=0}^{n-1} 6 = 6n \implies O(n)\)

Exemple 4


void algo4(int n){
  for(int i=0; i < n; i++){
    for(int j=0; j < i; j++){
      printf("Un appel\n");
    }
  }
}

Boucle interne (j) : 3 opérations par itération + 1 pour printf = 4i

Boucle externe (i) : \(\sum_{i=0}^{n-1} (3 + 4i) = 3n + 2n(n-1) \implies O(n^2)\)

Exemple 5


int algo5(int n){
  int cpt=0;
  for(int i=0; i < n; i++){
    if(i%3==0){ 
      for(int j=0; j < n; j++){
        cpt++;
      }
    }
  }
  return cpt;  
}

Complexité : la boucle externe = n, la boucle interne = n (si i%3==0), donc \(\approx O(n^2)\)

IV. Complexité au pire cas

Le temps d’exécution dépend :

de la taille de l'instance
de la structure de l'instance


int searchTab(int tab[], int n, int elt){
  for(int i=0; i < n; i++){  
    if(tab[i]==elt){
      return 1;
    }
  }
  return 0;
}

Instance A : [1, 99, 127, 8, 6], 5, 1 → arrêt au début
Instance B : [2, 17, 86, 20, 3], 5, 27 → parcours complet

Exercice 1


int algo6 (int tab[], int size){
  for(int i=0; i < size-1; i++){
    if(tab[i] > tab[i+1]){
      return 0;
    }
  }
  return 1;
}

1. Que fait-il ?

Vérifie si un tableau est trié en ordre croissant.

2. Instances

Pire cas : [1,2,3,4,5], 5 (parcours complet)
Meilleur cas : [5,4,3,2,1], 5 (arrêt immédiat)

3. Analyse de complexité

Boucle for : de 0 à size-2, 5 opérations par itération → Total : \(5(n-1) + 3 = 5n - 2 \implies O(n)\)