• 4 heures
  • Facile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 30/09/2019

Comprenez la complexité algorithmique

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Un problème vraiment complexe ?

La complexité algorithmique est un concept très important qui permet de comparer les algorithmes afin de trouver celui qui est le plus efficace. 

Avant d’entrer dans le détail de son calcul, laissez-moi vous conter une petite histoire.

Complexité exponentielle

Nous sommes dans le Midi, au cœur d’une belle forêt composée d’arbustes aromatiques et de pins. Il s’agit d’une douce matinée d’été éclairée par un soleil enthousiaste et nous nous promenons sur un chemin serpentant entre les collines. Soudain, un éclat de lumière attire votre regard entre les branchages. Vous vous approchez. Quelle n’est pas votre surprise lorsque vous apercevez, entre deux bruyères, un coffre qui semble être sorti tout droit d’un bateau pirate !

Oh gloire, la fortune serait-elle enfin à votre portée ? Vous soulevez le coffre et tombez nez à nez avec un cadenas à trois chiffres, en fonte, bien décidé à ne pas vous laisser accéder au trésor tant escompté. Quand bien même ! Nous décidons de relever le défi et de tester rapidement, une à une, toutes les combinaisons.

Plutôt que de les tester dans le désordre, car il serait impossible de se souvenir de toutes les tentatives, nous réfléchissons à différentes stratégies. L’une d’elles consiste à essayer le nombre le plus petit (000) puis le nombre suivant (001) et ainsi de suite jusqu’à atteindre 999. En effet, nous calculons que cette stratégie nous prendra, dans le pire des cas, 30 minutes. 

Effectivement, quelques minutes plus tard, le cadenas s’ouvre. Hourra ! Le code était 123. Facile ! Notre stratégie était efficace et nous nous félicitons d’être si intelligents.

Nous ouvrons le coffre... pour en découvrir un second, plus petit, comportant un cadenas à 4 chiffres. Tristesse.

Forts de notre premier succès, nous nous basons sur le même algorithme pour trouver le code. Au bout d’une heure et demie, las, nous abandonnons l’idée. C’est le plus raisonnable : tester toutes les combinaisons possibles aurait pris plus de 5 heures.

Nous reprenons notre marche, le petit coffre sous le bras, et partons dans un grand débat : comment en est-on arrivés là ? Comment le temps de calcul peut-il passer de 30 minutes à 5 heures en ajoutant un simple chiffre ? Le secret, c’est la complexité de notre algorithme

Au risque de ne pas vous surprendre, plus il y a de chiffres dans le code, plus il sera long à trouver. Mais plus long comment ?

Si le code a 3 chiffres, il faut tester 1000 combinaisons (eh oui, tous les nombres entre 000 et 999). En revanche, s’il en a 4, il faut en tester 10 000. S’il en avait eu 5, il aurait fallu en tester 100 000, et ainsi de suite. Nous nous apercevons donc que notre algorithme d’ouverture de coffre dépend du nombre de chiffres du code.

On dit alors que la complexité est exponentielle. Très vite, nous nous sommes rendu compte que notre algorithme était impossible à réaliser, car il devenait trop long.

Complexité linéaire

Après avoir disserté sur ce sujet, nous avons soudain une idée : et si nous arrêtions de calculer et faisions appel à Bill, notre cousin, celui qui trempe dans des affaires louches ? Il nous a raconté un jour qu’il savait "écouter les cadenas". Sa technique est simple : il tourne la molette du premier chiffre jusqu’à entendre un "clic". Il sait alors que le chiffre est bon et passe au suivant. Il peut donc trouver les bons chiffres un par un, sans avoir à se soucier des autres. 

Évidemment, le jour où il vous a exposé sa théorie vous avez bien ri. À présent, vous êtes dubitatif : vous avez passé deux heures à essayer d’ouvrir des coffres de pirates, alors bon, pourquoi ne pas tenter ?

Au bout de deux minutes, le cadenas à 4 chiffres est ouvert. Youpi ! Le code était 7339. ET L’ON A UTILISÉ UNE TECHNIQUE DE GANGSTER !! Nous hurlons si fort que même les cigales se taisent.

À présent, nous ouvrons le coffre et en découvrons le contenu. Il est à la hauteur de nos efforts !

Mais comment peut-on aller si vite, alors que nous avons exactement le même nombre de chiffres sur le cadenas ? 

C’est très simple ! Afin de trouver le premier chiffre du code, Bill tente 10 combinaisons. Quand il l’a trouvé, il passe au suivant et teste de nouveau 10 combinaisons. Et ainsi de suite pour chaque chiffre !

Il n’aura donc à tester que 40 combinaisons (10 + 10 + 10 + 10, soit 10 x 4) pour ce cadenas à quatre chiffres (ce qui est mieux que les 10 000 combinaisons que nous nous apprêtions à essayer…).

Si l’on y regarde de plus près, Bill teste 10 nouvelles combinaisons pour chaque nouveau chiffre du cadenas. Autrement dit, si $\(n\)$ est le nombre de chiffres, il teste 10 x $\(n\)$ combinaisons. Vous l’avez dans le mille, la "complexité" de son algorithme était bien meilleure que la nôtre.

Nous appelons cela une complexité linéaire. Pourquoi ? Car elle augmente proportionnellement au nombre de chiffres.

Complexité en temps constant

Tout contents, nous allons rendre visite à Bill pour lui montrer le cadenas (nous avons bien pris soin de cacher le contenu du coffre... on ne sait jamais !) et crâner un peu. Pour sûr, il sera impressionné !

Bill vous adresse un regard circonspect. "Vous voulez vous amuser ? Voilà de quoi faire !", vous dit-il, sortant d’un placard un cadenas à 500 chiffres qui manque de faire écrouler la table de la salle à manger. "Il faut tester 5000 combinaisons, ce qui prendra environ 3 heures. Enfin... Si vous êtes rapides."

Mince, nous nous retrouvons dans le même problème que tout à l’heure. Aussi efficace que soit sa technique, le nombre de chiffres du cadenas est trop important. Autrement dit, la taille des données du problème excède la capacité de son algorithme.

C’est là que passe Jack, votre neveu. Il rigole, prend une pierre et tape sur le cadenas. Paf ! Ce dernier s’ouvre d’un coup sec. Effectivement... Cela paraît si simple, maintenant que l’on y pense… 

Si l’on s’y attarde de plus près, son algorithme est sacrément efficace ! Quel que soit le nombre de chiffres, il prend toujours le même temps. Balèze !

Nous parlons alors de complexité en temps constant

Le temps et l’espace

La complexité temporelle

Si nous comparons nos différents algorithmes, nous nous rendons compte que nous avons surtout pris en compte le facteur temps : notre première solution nous a pris 30 minutes quand celle de Jack ne demande qu’une seconde (bon, deux si le cadenas est vraiment récalcitrant). 

Il en sera de même pour chaque algorithme, que ce soit le tri d’une liste, la décomposition en facteur premier ou encore la recherche du cours le plus suivi sur OpenClassrooms. Nous parlons alors de complexité temporelle

Quel est l’intérêt, me direz-vous ? Cela nous permet de savoir à l’avance si un algorithme ne se terminera jamais. Bien pratique !

Internet nous offre une autre application très importante de ce concept. Imaginons un site de restauration à emporter. Que se passe-t-il lorsque vous cherchez tous les restaurants asiatiques à 1 km de chez vous, ouverts jusqu’à 23 heures et qui livrent à domicile ? L’algorithme va tout faire pour trouver le résultat de votre recherche. Malgré cela, vous n’avez pas envie d’attendre 3 heures. Vous souhaitez que le site affiche la page de résultats en une seconde ou deux, pas plus. Il est donc primordial de trouver l’algorithme le plus efficace qui soit.

La complexité spatiale

Le dernier point à connaître concerne le stockage des données. Lorsque nous réalisons un algorithme en informatique, les informations sont stockées sur la mémoire de l’ordinateur. Or, vous l’aurez deviné, cette mémoire n’est pas infinie. Si nous ne faisons pas attention, un algorithme peut vite occuper tout l’espace libre d’un ordinateur et le faire planter.

On parle ici de complexité spatiale (en espace). Les notations sont exactement les mêmes que pour la complexité temporelle. 

Épilogue

Alors que nous nous promenons de nouveau dans la forêt, je me tourne vers vous et vous demande : "D’ailleurs, si Jack n’était pas entré et que l’on avait essayé toutes les combinaisons sur le cadenas à 500 chiffres, combien de temps cela nous aurait-il pris ?" Avez-vous une idée ?

Vous souhaitez en savoir plus sur l’ouverture des cadenas ? Ulysse, avec qui j’ai coécrit ce chapitre, vous offre ce lien bonus

Exemple de certificat de réussite
Exemple de certificat de réussite