Complexité algorithmique [Le fonctionnement d'un ordinateur]

Complexité algorithmique

Objectif

Découvrir la notion de complexité algorithmique.

Mise en situation

Lorsqu'un développeur écrit un programme, il lui est nécessaire d'estimer si ce programme est coûteux. Coûteux cela signifie par exemple qu'il nécessite beaucoup de calculs de la part du processeur. Cela peut aussi signifier qu'il nécessite beaucoup d'espace mémoire.

Savoir calculer ce coût permet de comparer plusieurs solutions alternatives entre elles. Cela permet aussi de savoir si un programme peut « passer à l'échelle » c'est à dire continuer de fonctionner correctement si on le confronte à la réalité.

Par exemple si un développeur a écrit un programme permettant de vérifier une empreinte de carte de paiement, mais que cette vérification prend plusieurs minutes ou nécessite un ordinateur doté d'une mémoire très importante, il ne sera pas possible de l'utiliser pour du paiement en ligne.

Exemple : Compter le nombre d'opérations pour résoudre un problème

Pour créer la table de 2 des n premiers entiers, il faut réaliser n calculs de type multiplication.

De manière générale, on cherche à estimer de manière théorique le nombre d'opérations à effectuer pour résoudre un problème : c'est ici que l'on parle de complexité d'un problème.

Définition : Complexité algorithmique

La complexité algorithmique est une estimation du nombre d'opérations élémentaires pour résoudre un problème en fonction de la taille des données d'entrée, notée n.

Syntaxe : O()

On note O() l'ordre de grandeur de la complexité d'un algorithme.

O(n) signifie que le nombre d'opérations est de l'ordre de n (si on a 1000 données en entrée, on s'attend à environ 1000 opérations).
O(n²) signifie que le nombre d'opérations est de l'ordre de n au carré (si on a 1000 données en entrée, on s'attend à environ 1 000 000 d'opérations).

Exemple : Exemple simple

Ce code fait la somme d'une liste d'entiers.

function somme(number_list) {
  let res = 0;
  for (var i = 0; i < number_list.length; i++) {
      res += number_list[i];
  }
  return res;
}

function somme(number_list) {
  let res = 0;
  for (var i = 0; i < number_list.length; i++) {
      res += number_list[i];
  }
  return res;
}

Étant donné n la taille de la liste, il serait nécessaire d'effectuer n opérations d'addition pour obtenir la somme finale. Ici, on dira que la complexité de l'algorithme est de l'ordre de n et on la notera O(n).

Remarque : Pourquoi utiliser la complexité algorithmique ?

La complexité algorithmique peut se voir comme l'estimation du "temps d'exécution" d'un algorithme en fonction de la taille des données d'entrée.

On suppose pour ce faire que les opérations de base (affectation, addition, etc.) ont le même temps d'exécution : estimer le temps d'exécution revient alors à estimer le nombre d'opérations de base.

Attention : L'exécution reste proportionnelle à la taille des données

La complexité ne change pas en fonction de la taille des données. En revanche, l’exécution sera évidemment plus longue si la taille des données augmente. Ainsi, pour 100 données, un algorithme en O(n) effectuera de l'ordre de 100 opérations. Pour 1000 données il en effectuera de l'ordre de 1000.

Méthode : Estimer rapidement la complexité

La complexité permet d'avoir une idée grossière de la durée d'un algorithme. Par exemple, si on détermine que pour une liste de n éléments, il faut effectuer 2×n opérations, on simplifiera en disant que la complexité est de l'ordre de O(n).

La raison principale est que les constantes ne changent pas fondamentalement l'ordre de grandeur de la complexité. Par exemple, O(n²) et O(2×n²) sont très proches, et c'est surtout la valeur de n qui influencera la durée finale.

Fondamental : Complexités usuelles des algorithmes

On retrouve très régulièrement les complexités suivantes :

O(1) : si le nombre d'opérations ne dépend pas de la taille des données. Par exemple, afficher le premier élément d'une liste.
O(n) : cette complexité se retrouve souvent quand on a besoin de parcourir les éléments d'une liste, par exemple pour calculer la somme des éléments.
O(n²) : par exemple, l'algorithme naïf pour trier une liste de nombre nécessite, pour chaque élément de la liste, de parcourir l'ensemble de la liste.
O(n×m) : par exemple, pour trouver les nombres communs de deux listes de taille n et m, il faut pour chaque nombre de la première liste parcourir l'ensemble de la deuxième liste pour vérifier s'il existe.

Complément :

La complexité algorithmique permet de dire, qu'à tailles de données égales, un algorithme en O(n) terminera bien avant un second algorithme dont la complexité est O(n²).

Ainsi, pour 100 données, le premier algorithme effectuera environ 100 opérations de bases et le second 10 000 opérations. On comprend que, si la taille des données se compte en millions (ou même en milliards), le second algorithme sera beaucoup plus coûteux que le premier.

Comparaison des complexités
n	O(n)	O(n²)
10	10	100
100	100	10 000
1 000	1 000	1 000 000
10 000	10 000	100 000 000

Complément : Complexité algorithmique en espace

Le temps de calcul est important mais l'espace nécessaire au calcul l'est aussi. La mémoire d'un ordinateur n'est pas infinie : il est utile d'estimer l'espace mémoire nécessaire pour exécuter un algorithme.

La complexité décrite jusqu'ici se nomme complexité en temps. Ici, on parle complexité algorithmique en espace. La notation sera toujours la même : O(1), O(n), O(n²), etc.

Complément : Complexité et machine de Turing

Le concept de complexité algorithmique est étroitement lié aux machines de Turing, une des bases théorique des ordinateurs. Elles ont introduit une nouvelle définition de la notion de calcul qui permet également de théoriser sa complexité. Ainsi, aujourd'hui, on peut classer les problèmes de calcul selon la complexité des algorithmes pouvant les résoudre.

On peut distinguer, très schématiquement, trois grands types de problèmes :

Problème dont l'algorithme finira en un temps polynomial : O(n), O(n²), etc.
Problème dont l'algorithme finira en un temps exponentiel : O(2ⁿ), O(n!), etc. On évite que ce type d'algorithme car il suffit que n augmente un tout petit peu pour que le temps d’exécution se compte en mois, en années voire en siècles.
Problème dont il n'existe pas de solution (dits indécidables).

À retenir

Il est possible d'attribuer une complexité à un algorithme.
Estimer la complexité d'un programme permet d'avoir un ordre de grandeur de son temps d’exécution.
Comparer la complexité de deux algorithmes permet de déterminer lequel est le plus optimisé pour répondre à un problème donné.