Découvrez le fonctionnement des algorithmes

Vous avez pu voir qu’un algorithme peut être créé de mille et une façons. Mais comment pouvez-vous savoir si votre algorithme est plus efficace qu’un autre, ou même savoir s’il est performant ?

Pour cela, vous allez devoir analyser la complexité de votre algorithme. Ainsi, vous pourrez conclure que cette complexité est convenable, ou la comparer avec d'autres algorithmes.

La complexité algorithmique est un concept très important qui permet de comparer les algorithmes afin de trouver celui qui est le plus efficace. Il existe une notation standard qui s’appelle big O et qui permet de mesurer la performance d’un algorithme. Vous verrez, au fur et à mesure des explications, la méthode de calcul.

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

La complexité exponentielle

Nous sommes dans le Midi, au cœur d’une belle forêt, et nous nous promenons paisiblement. Soudain, un éclat de lumière attire votre regard. Vous vous approchez. Quelle n’est pas votre surprise lorsque vous apercevez un coffre qui semble être sorti tout droit d’un bateau pirate !

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.

Voyons maintenant comment décrire ce problème avec le pseudo-code :

Algorithme cadenas_3_chiffres
Début
    Pour i allant de 0 jusqu’à 9 :
        Pour j allant de 0 jusqu’à 9 :
            Pour k allant de 0 jusqu’à 9 :
                Si code == combinaison :
                    Arrêter les boucles
                Fin Si
            Fin Pour
        Fin Pour
    Fin Pour
Fin

Nous avons dans cet algorithme 3 boucles allant de 0 à 9 donc 10 x 10 x 10 itérations, soit 10^3 itérations. Avec la notation Big O, on dira que la complexité temporelle de cet algorithme est de  $\$\backslash (O(10^3)\backslash )\$$ .

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 1 000 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.

Si l’on note  n   le nombre de chiffres de notre cadenas, le temps de calcul est donc  $\$\backslash (10^n\backslash )\$$  ; ainsi, à l’aide de la notion big O, nous pouvons noter que la complexité temporelle de notre algorithme est de O( $\$\backslash (10^n\backslash )\$$).

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.

La 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 ! À présent, nous ouvrons le coffre et en découvrons le contenu. Il est à la hauteur de nos efforts !

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…).

Voyons maintenant comment décrire cette nouvelle solution avec le pseudo-code :

Algorithme cadenas_4_chiffres
Variable
    chiffre_1 ← 0 : ENTIER
    chiffre_2 ← 0 : ENTIER
    chiffre_3 ← 0 : ENTIER
    chiffre_4 ← 0 : ENTIER
Début
    Pour i allant de 0 jusqu’à 9 :
        Si entendre un “clic” :
            chiffre_1 ← i
        Fin Si
    Fin Pour
    
    Pour j allant de 0 jusqu’à 9 :
        Si entendre un “clic” :
            chiffre_2 ← j
        Fin Si
    Fin Pour
    
    Pour k allant de 0 jusqu’à 9 :
        Si entendre un “clic” :
            chiffre_3 ← k
        Fin Si
    Fin Pour

    Pour m allant de 0 jusqu’à 9 :
        Si entendre un “clic” :
            chiffre_4 ← m
        Fin Si
    Fin Pour
Fin

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. Ainsi avec la notation big O, nous pouvons dire que cet algorithme a une complexité de  $\$\backslash (O(10\; x\; n)\backslash )\$$ . 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.

La complexité en temps constant

Tout contents, nous allons rendre visite à Bill pour lui montrer le cadenas 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 5 000 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. On note ce type de complexité avec la notation big O,  $\$\backslash (O(1)\backslash )\$$ . 

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. 

Il en sera de même pour chaque algorithme, que ce soit le tri d’une liste, la décomposition en facteurs premiers 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 big O sont exactement les mêmes que pour la complexité temporelle.

Imaginez un algorithme où l’utilisateur doive entrer n éléments et les enregistrer dans un tableau. Dans ce cas, la complexité spatiale se notera avec la notation big O,  $\$\backslash (O(n)\backslash )\$$ . Car le tableau contiendra finalement n éléments. Et si à l’aide des mêmes n éléments, l’algorithme construit deux tableaux de n éléments, cette fois la complexité spatiale sera de  $\$\backslash (O(2n)\backslash )\$$ , car l’algorithme crée 2 tableaux de n cases.

À vous de jouer

Contexte

Tout au long de ce cours, vous avez pu créer des algorithmes pour le labyrinthe. Nous allons en prendre quelques-uns et calculer la complexité temporelle et spatiale de ceux-ci.

Consigne

Nous allons calculé la complexité temporelle et spatiale de 3 algorithmes.

• Nous avons tout d’abord l’algorithme de déplacement suivant : 

Algorithme déplacement(position_x , position_y)
Variable
    sens ← “” : CHAÎNE DE CARACTÈRES
Début
    sens ← entrer()
    Si sens == “Haut” OU sens == “Bas” OU sens == “Droite” OU sens == “Gauche” :
        Si sens == “Haut” :
            position_y = position_y + 1
        Fin Si
        Si sens == “Bas” :
            position_y = position_y - 1
        Fin Si
        Si sens == “Droite” :
            position_x = position_x + 1
        Fin Si
        Si sens == “Gauche” :
            position_x = position_x - 1
        Fin Si
    Sinon
        afficher “L’entrée n’est pas correcte”
    Fin Si
Fin

• Nous avons ensuite l’algorithme suivant qui permet de ramasser un nombre n de clés dans le labyrinthe : 

Algorithme ramasser
Variable
    joueur_position_x ← 0 : ENTIER
    joueur_position_y ← 0 : ENTIER
    arrivée_position_x ← 5 : ENTIER
    arrivée_position_y ← 5 : ENTIER
    clés[n] : TABLEAU CHAÎNE DE CARACTÈRES
    déplacement ← 0 : ENTIER
    max_déplacement ← 30n : ENTIER
Début
    Tant Que joueur_position_x != arrivée_position_x ET joueur_position_y != arrivée_position_y ET clés.taille() != n ET déplacement < max_déplacement :
        déplacement(joueur_position_x, joueur_position_y)
        ramasser(clés, joueur_position_x, joueur_position_y)
    Fin Tant Que
Fin

• Pour terminer, nous avons l’algorithme de tri suivant :

Algorithme Tri(tableau)
    taille ← Taille du tableau
    Pour i allant de 0 jusqu’à taille - 1 :
        Pour j allant de 0 jusqu’à taille - 1 - 1 :
            Si tableau[j+1] < tableau[j] :
                echanger(tableau[j+1], tableau[j])
            Fin Si
        Fin Pour
    Fin Pour
Fin

Votre objectif :

• Mesurer la complexité temporelle et spatiale des 3 algorithmes :

  • déplacement ;

  • ramassage ;

  • tri.

Vérifiez votre travail

Voici le résultat à obtenir à l'issue de l'exercice :

• La fonction  déplacement  : 

  • complexité temporelle : $\$\backslash (O(1)\backslash )\$$ .
    La complexité est constante, il n’y a aucune boucle ni aucune fonction récursive.

  • complexité spatiale : $\$\backslash (O(1)\backslash )\$$ .
    La mémoire n’est pas affectée par cet algorithme.

• La fonction  ramasser  : 

  • complexité temporelle : $\$\backslash (O(30n)\backslash )\$$ .
    Au pire des cas, la boucle va itérer 30 x n fois.

  • complexité spatiale : $\$\backslash (O(n)\backslash )\$$ .
    La complexité est linéaire, le tableau aura au maximum n cases.

• La fonction  tri  : 

  • complexité temporelle : $\$\backslash (O(n2)\backslash )\$$ .
    Il y a deux boucles imbriquées qui itèrent n fois, donc nous avons au maximum n x n itérations.  

  • complexité spatiale : $\$\backslash (O(1)\backslash )\$$ .
    La mémoire n’est pas affectée par cet algorithme, car la taille du tableau ne change pas.

En résumé

• La complexité d'un algorithme est une mesure de la quantité de temps et/ou d'espace requise par un algorithme.

• La complexité temporelle est le temps nécessaire à l'exécution d'un algorithme, en fonction de la longueur des données en entrée.

• La complexité spatiale mesure la quantité totale de mémoire dont un algorithme ou une opération a besoin pour s'exécuter en fonction de la longueur de données en entrée.

• La notation big O est une notation standard pour décrire la complexité d’un algorithme.

C’est bientôt terminé, il ne reste plus qu’un chapitre. Je vous propose de voir un concept assez avancé de l’informatique, qu’on appelle la récursivité. Je vous attends avec impatience dans ce dernier chapitre.