{"id":399,"date":"2021-09-09T11:15:58","date_gmt":"2021-09-09T11:15:58","guid":{"rendered":"https:\/\/www.louismarchand.me\/?page_id=399"},"modified":"2021-09-09T11:15:58","modified_gmt":"2021-09-09T11:15:58","slug":"objet-2-la-complexite-algorithmique","status":"publish","type":"page","link":"https:\/\/www.louismarchand.me\/index.php\/objet-2-la-complexite-algorithmique\/","title":{"rendered":"La complexit\u00e9 algorithmique"},"content":{"rendered":"

Introduction<\/h2>\n

Avoir une bonne repr\u00e9sentation de la performance d’un algorithme est un \u00e9l\u00e9ment important pour un programmeur et, malheureusement, \u00e9valuer cette performance est g\u00e9n\u00e9ralement tr\u00e8s difficile et peu intuitif. Il ne suffit pas de diminuer le nombre de lignes de code pour augmenter la performance. En fait, il arrive souvent que des algorithmes plus performants soient \u00e9galement plus gros et plus complexes \u00e0 comprendre.<\/p>\n

Les bases<\/h2>\n

Par performance d’un algorithme, on entend la balance entre la rapidit\u00e9 d’ex\u00e9cution de l’algorithme par rapport \u00e0 l’espace m\u00e9moire utilis\u00e9.<\/p>\n

En effet, un algorithme bien con\u00e7u devra d\u00e9cider pourra stocker une grande quantit\u00e9 de valeurs en m\u00e9moire (ce que nous appelons une cache) afin d’\u00e9viter de traiter ces valeurs, ce qui fait un algorithme plus rapide. Inversement, au lieu de stocker des valeurs en m\u00e9moire, il est souvent possible de les recalculer au besoin, ce qui augmente la performance m\u00e9moire, mais diminue la vitesse.<\/p>\n

Par contre, avant de balancer la performance m\u00e9moire et la vitesse d’ex\u00e9cution d’un algorithme, il faut s’assurer que l’algorithme est optimal. Le calcul permettant de mesurer la performance (particuli\u00e8rement la vitesse) d’un algorithme est appel\u00e9 la complexit\u00e9 algorithmique.<\/p>\n

La complexit\u00e9 algorithmique<\/h2>\n

La complexit\u00e9 algorithmique permet le calcul et la notation de la performance d’un algorithme. En d’autres mots, \u00e7a nous permet d’avoir une mesure permettant de comparer la performance de diff\u00e9rents algorithmes.<\/p>\n

La complexit\u00e9 d’un probl\u00e8me<\/h3>\n

Un algorithme est une m\u00e9canique permettant de r\u00e9soudre un probl\u00e8me (peu importe le type de probl\u00e8me). Par exemple, il y a des algorithmes permettant de ressourdre les probl\u00e8mes: Trouver un \u00e9l\u00e9ment dans une structure (liste, arbre, etc.), calculer une moyenne, ressourdre un Rubiks cube, calculer le chemin le plus rapide pour partir de ma r\u00e9sidence jusqu’\u00e0 mon travail, etc.<\/p>\n

On dit que tous les probl\u00e8mes ont une complexit\u00e9. C’est-\u00e0-dire une performance optimale permettant de r\u00e9soudre le probl\u00e8me. Cette complexit\u00e9 est un id\u00e9al et n’est pas toujours connue. L’objectif d’un programmeur est de trouver un algorithme qui a une complexit\u00e9 qui se rapproche le plus de la complexit\u00e9 du probl\u00e8me.<\/p>\n

La complexit\u00e9 d’un algorithme<\/h3>\n

Il est important de comprendre que, de base, ce qui augmente la complexit\u00e9 d’un algorithme, c’est les boucles de cet algorithme. Par exemple, l’algorithme suivant (en Java):<\/p>\n

\n
public<\/span> int<\/span> addition<\/span>(<\/span>int<\/span> aValeur1<\/span>,<\/span> int<\/span> aValeur2<\/span>)<\/span> {<\/span>\r\n    return<\/span> aValeur1<\/span> +<\/span> aValeur2<\/span>;<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
est plus performant que l’algorithme suivant:<\/p>\n
\n
public<\/span> int<\/span> addition<\/span>(<\/span>int<\/span> aValeur1<\/span>,<\/span> int<\/span> aValeur2<\/span>)<\/span> {<\/span>\r\n    int<\/span> lRetour<\/span> =<\/span> aValeur1<\/span>;<\/span>\r\n    for<\/span> (<\/span>int<\/span> i<\/span> =<\/span> 0<\/span>;<\/span> i<\/span> <<\/span> aValeur2<\/span>;<\/span> i<\/span> =<\/span> i<\/span> +<\/span> 1<\/span>){<\/span>\r\n        lRetour<\/span> =<\/span> lRetour<\/span> +<\/span> 1<\/span>;<\/span>\r\n    }<\/span>\r\n    return<\/span> lRetour<\/span>;<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
La notation O<\/h3>\n
On note la complexit\u00e9 d’un algorithme avec la notation O(complexit\u00e9). Par exemple, un algorithme peut \u00eatre 0(1), O(n), O(log(n)), O(n^2), etc. Le \u00ab\u00a0n\u00a0\u00bb dans les notations repr\u00e9sente le nombre de valeurs \u00e0 traiter. Par exemple, dans les deux exemples pr\u00e9c\u00e9dents, le premier exemple (l\u2019addition avec une seule ligne de retour) est O(2) puisqu’il doit faire une addition et une assignation, et le second exemple (l’addition avec une boucle) est O(2*aValeur2 + 2), le \u00ab\u00a02*aValeur2\u00a0\u00bb correspondant \u00e0 l’addition et l’assignation dans la boucle et le \u00ab\u00a0+ 2\u00a0\u00bb correspondant aux 2 assignations \u00e0 l’ext\u00e9rieur de la boucle.<\/p>\n
Le principe d’ordre de grandeur<\/h3>\n
Il est important de comprendre que ce qui nous int\u00e9resse dans la complexit\u00e9 algorithmique, c’est l’ordre de grandeur de cette complexit\u00e9. L’ordre de grandeur se calcule toujours par rapport \u00e0 une variable. Ainsi, les multiplications de constante ne sont pas prises en compte. Par exemple, les ordres de complexit\u00e9 suivants sont tous \u00e9quivalents:<\/p>\n
O(2) = O(1000000) = O(-345) = O(1)<\/pre>\n
O(2*n) = O(1000000*n) = O(-543*n) = O(n)<\/pre>\n
O(2*n\u00b2) = O(1000000*n\u00b2) = O(-923*n\u00b2) = O(n\u00b2)<\/pre>\n
O(2*n\u00b3) = O(1000000*n\u00b3) = O(-923*n\u00b3) = O(n\u00b3)<\/pre>\n
O(2*log(n)) = O(log(2*n)) = O(log(1000000*n)) = O(log(n))<\/pre>\n
Il est important de voir que les derniers \u00e9l\u00e9ments de chaque ligne d’\u00e9galit\u00e9s est comment on note cet ordre de complexit\u00e9. Ainsi, dans les exemples pr\u00e9c\u00e9dents, le premier exemple (l\u2019addition avec une seule ligne de retour) doit \u00eatre not\u00e9 O(1) et non O(2) comme pr\u00e9cis\u00e9 plus haut.<\/p>\n
\u00c9galement, l’ordre de grandeur de complexit\u00e9 algorithmique ignore les additions de polyn\u00f4me contenant des ind\u00e9termin\u00e9s identiques. Seul l’ind\u00e9termin\u00e9 ayant le plus haut degr\u00e9 est gard\u00e9. Par exemple, voici des ordres de complexit\u00e9 qui sont \u00e9quivalents:<\/p>\n
O(3n + 5) = O(n)<\/pre>\n
O(3*n + 5*n\u00b2 + n + 1000) = O(n\u00b2 + log(n)) = O(n\u00b2)<\/pre>\n
O(n*log(n) + log(n) + log(log(n))) = O(n*log(n))<\/pre>\n
Encore une fois, le dernier \u00e9l\u00e9ment des \u00e9galit\u00e9s repr\u00e9sente comment nous devrions noter les ordres algorithmiques.<\/p>\n
Ainsi, dans les exemples pr\u00e9c\u00e9dents, le second exemple (le addition avec une boucle pour calculer le r\u00e9sultat), doit \u00eatre not\u00e9 O(aValeur2) et non O(2* aValeur2 + 2) comme pr\u00e9cis\u00e9 plus haut.<\/p>\n
Comment calculer l’ordre de complexit\u00e9 d’un algorithme<\/h3>\n
Les techniques de calcul d’ordre de complexit\u00e9 algorithmique sont hors des notions \u00e0 voir dans ce cours. N\u00e9anmoins, je crois qu’il est important d’avoir une bonne compr\u00e9hension de ce qui cause les ordres de complexit\u00e9 classique.<\/p>\n
L’ordre de complexit\u00e9 algorithmique correspond au nombre maximal de fois que seraient ex\u00e9cut\u00e9s des capteurs d’ex\u00e9cution qui seraient plac\u00e9s entre chaque instruction de l’algorithme. Par exemple, prenons l’algorithme suivant:<\/p>\n
\n
public<\/span> void<\/span> afficherInformations<\/span>()<\/span> {<\/span>\r\n    System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Prenom: Boba\"<\/span>);<\/span>\r\n    System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Nom: Fett\"<\/span>);<\/span>\r\n    System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Age: 12 ans\"<\/span>);<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
En pla\u00e7ant les capteurs entre chaque instruction, on obtiendrait:<\/p>\n
\n
public<\/span> void<\/span> afficherInformations<\/span>()<\/span> {<\/span>\r\n            Capteur1<\/span>\r\n    System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Prenom: Boba\"<\/span>);<\/span>\r\n            Capteur2<\/span>\r\n    System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Nom: Fett\"<\/span>);<\/span>\r\n            Capteur3<\/span>\r\n    System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Age: 12 ans\"<\/span>);<\/span>\r\n            Capteur4<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Si on ex\u00e9cutait cet algorithme, chaque capteur s’ex\u00e9cuterait une seule fois. On obtient donc que cet algorithme est d’ordre O(1).<\/p>\n
Voici un autre exemple:<\/p>\n
\n
public<\/span> int<\/span> calculerMoyenne<\/span>(<\/span>List<\/span><<\/span>Integer<\/span>><\/span> aValeurs<\/span>)<\/span> {<\/span>\r\n    int<\/span> lSomme<\/span> =<\/span> 0<\/span>;<\/span>\r\n    for<\/span> (<\/span>Integer<\/span> laValeur<\/span> :<\/span> aValeurs<\/span>)<\/span> {<\/span>\r\n        lSomme<\/span> =<\/span> lSomme<\/span> +<\/span> laValeur<\/span>.<\/span>intValue<\/span>();<\/span>\r\n    }<\/span>\r\n    return<\/span> lSomme<\/span> \/<\/span> aValeurs<\/span>.<\/span>size<\/span>();<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Si on ajoute les capteurs dans cet algorithme, on obtient:<\/p>\n
\n
public<\/span> int<\/span> calculerMoyenne<\/span>(<\/span>List<\/span><<\/span>Integer<\/span>><\/span> aValeurs<\/span>)<\/span> {<\/span>\r\n            Capteur1<\/span>\r\n    int<\/span> lSomme<\/span> =<\/span> 0<\/span>;<\/span>\r\n            Capteur2<\/span>\r\n    for<\/span> (<\/span>Integer<\/span> laValeur<\/span> :<\/span> aValeurs<\/span>)<\/span> {<\/span>\r\n                Capteur3<\/span>\r\n        lSomme<\/span> =<\/span> lSomme<\/span> +<\/span> laValeur<\/span>.<\/span>intValue<\/span>();<\/span>\r\n                Capteur4<\/span>\r\n    }<\/span>\r\n            Capteur5<\/span>\r\n    return<\/span> lSomme<\/span> \/<\/span> aValeurs<\/span>.<\/span>size<\/span>();<\/span>\r\n            Capteur6<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Ici, si on ex\u00e9cute cet algorithme avec des listes diff\u00e9rentes, nous remarquons rapidement que les capteurs ayant les plus d’ex\u00e9cution sont les capteurs 3 et 4 et que leurs nombres d’ex\u00e9cutions correspondent \u00e0 la taille de la liste re\u00e7ue en entr\u00e9e. On obtient donc la complexit\u00e9 algorithmique O(n) ou n=aValeurs.size().<\/p>\n
Voici un autre exemple:<\/p>\n
\n
public<\/span> int<\/span> valeurMaximale<\/span>(<\/span>List<\/span><<\/span>List<\/span><<\/span>Integer<\/span>>><\/span> aMatrice<\/span>)<\/span> {<\/span>\r\n    int<\/span> lResultat<\/span> =<\/span> aMatrice<\/span>.<\/span>get<\/span>(<\/span>0<\/span>).<\/span>get<\/span>(<\/span>0<\/span>).<\/span>intValue<\/span>();<\/span>\r\n    for<\/span> (<\/span>List<\/span><<\/span>Integer<\/span>><\/span> laLigne<\/span> :<\/span> aMatrice<\/span>)<\/span> {<\/span>\r\n        for<\/span> (<\/span>Integer<\/span> laValeur<\/span> :<\/span> laLigne<\/span>)<\/span> {<\/span>\r\n            if<\/span> (<\/span>lResultat<\/span> <<\/span> laValeur<\/span>.<\/span>intValue<\/span>())<\/span> {<\/span>\r\n                lResultat<\/span> =<\/span> laValeur<\/span>.<\/span>intValue<\/span>();<\/span>\r\n            }<\/span>\r\n        }<\/span>\r\n    }<\/span>\r\n    return<\/span> lResultat<\/span>;<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Si on ajoute nos capteurs, on obtient:<\/p>\n
\n
public<\/span> int<\/span> valeurMaximale<\/span>(<\/span>List<\/span><<\/span>List<\/span><<\/span>Integer<\/span>>><\/span> aMatrice<\/span>)<\/span> {<\/span>\r\n            Capteur1<\/span>\r\n    int<\/span> lResultat<\/span> =<\/span> aMatrice<\/span>.<\/span>get<\/span>(<\/span>0<\/span>).<\/span>get<\/span>(<\/span>0<\/span>).<\/span>intValue<\/span>();<\/span>\r\n            Capteur2<\/span>\r\n    for<\/span> (<\/span>List<\/span><<\/span>Integer<\/span>><\/span> laLigne<\/span> :<\/span> aMatrice<\/span>)<\/span> {<\/span>\r\n                Capteur3<\/span>\r\n        for<\/span> (<\/span>Integer<\/span> laValeur<\/span> :<\/span> laLigne<\/span>)<\/span> {<\/span>\r\n                    Capteur4<\/span>\r\n            if<\/span> (<\/span>lResultat<\/span> <<\/span> laValeur<\/span>.<\/span>intValue<\/span>())<\/span> {<\/span>\r\n                        Capteur5<\/span>\r\n                lResultat<\/span> =<\/span> laValeur<\/span>.<\/span>intValue<\/span>();<\/span>\r\n                        Capteur6<\/span>\r\n            }<\/span>\r\n                    Capteur7<\/span>\r\n        }<\/span>\r\n                Capteur8<\/span>\r\n    }<\/span>\r\n            Capteur9<\/span>\r\n    return<\/span> lResultat<\/span>;<\/span>\r\n            Capteur10<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Si on ex\u00e9cute cet algorithme, on obtient que les capteurs les plus ex\u00e9cut\u00e9s soient les capteurs 4 \u00e0 7. Leurs nombres d’ex\u00e9cutions est de O(m*n) ou m=nombre de ligne de la matrice et n=nombre de colonne de la matrice.<\/p>\n
Ce r\u00e9sultat est un peu emb\u00eatant parce qu’il correspond \u00e0 un ordre de complexit\u00e9 quadratique(ou O(n\u00b2)), mais il est difficile de s’en rendre compte seulement en regardant la notation O(n*m). Par contre, puisque c’est simplement l’ordre de complexit\u00e9 du pire cas qui nous importe et non la complexit\u00e9 r\u00e9elle, nous pouvons indiquer quelque chose comme O(n\u00b2) ou n=Max(Ligne et colonne de la matrice).<\/p>\n
R\u00e9sumons<\/h4>\n
On voit qu’on peut, instinctivement (sans placer de capteur), d\u00e9duire l’ordre de complexit\u00e9 d’un algorithme en regardant la profondeur des boucles. Bien entendu, il y a des subtilit\u00e9s, mais g\u00e9n\u00e9ralement, un algorithme sans boucle est O(1), un algorithme avec une boucle (ou plusieurs boucles s\u00e9cancielles) sont O(n), un algorithme avec une boucle imbriqu\u00e9e dans une autre est O(n\u00b2), un algorithme avec une boucle imbriqu\u00e9e dans une autre qui est \u00e0 son tour imbriqu\u00e9e dans une autre est O(n\u00b3), etc.<\/p>\n
Vous devez faire attention parce que parfois, les boucles peuvent \u00eatre cach\u00e9es dans des sous-routines. Elles doivent \u00e9galement \u00eatre prises en compte dans le calcul d’ordre de complexit\u00e9 algorithmique.<\/p>\n
Le pire cas<\/h3>\n
Lorsque nous cherchons la complexit\u00e9 d’un algorithme, nous nous int\u00e9ressons au pire cas possible dans cet algorithme. Par exemple, si nous faisons un algorithme effectuant une recherche dans une liste, il est inutile de continuer l’algorithme si l’\u00e9l\u00e9ment a \u00e9t\u00e9 trouv\u00e9. Il serait donc possible de sortir de l’algorithme bien avant d’avoir termin\u00e9 la recherche et de cette mani\u00e8re, rendre l’algorithme plus performant. Par contre, lorsqu’on calcule l’ordre de complexit\u00e9 algorithmique, on \u00e9value le pire cas. Dans l’exemple de la recherche dans une liste, le pire cas correspond au fait que l’\u00e9l\u00e9ment est trouv\u00e9 \u00e0 la derni\u00e8re cellule de la liste qui est v\u00e9rifi\u00e9e (ou encore pire, l’\u00e9l\u00e9ment n’est pas trouv\u00e9).<\/p>\n
Pour aller plus loin<\/h3>\n
Il est \u00e0 noter qu’il existe des algorithmes d’ordre logarithmique (avec ou sans multiplicateur variable). Par exemple, il y a des algorithmes d’ordre O(log(n)), d’autres d’ordre O(n*log(n)), d’autre d’ordre O(n\u00b2*log(n)), O(log(log(n))), etc. Il s’agit g\u00e9n\u00e9ralement d’algorithme r\u00e9cursif de type diviser pour r\u00e9gner si vous voulez voir \u00e0 quoi \u00e7a ressemble (voir par exemple le tri fusion qui est O(n*log(n))). Savoir ordonner ces ordres de grandeur est important. Donc, voici une liste comparative non exhaustive qui pourrait vous \u00eatre utile:<\/p>\n
\n
O(p^n) > O(n\u00b3*log(n)) > O(n\u00b3*log(log(n))) > O(n\u00b3) > O(n\u00b2*log(n)) > \r\nO(n\u00b2*log(log(n))) > O(n\u00b2) > O(n*log(n)) > O(n*log(log(n))) > O(n) > \r\nO(log(n)) > O(log(log(n))) > O(1)<\/pre>\n<\/div>\n
Le \u00ab\u00a0p\u00a0\u00bb indiqu\u00e9 dans O(p^n) repr\u00e9sente une constante enti\u00e8re p > 1.<\/p>\n
Retour<\/a><\/p>\n
\n
Auteur: Louis Marchand
\n\"Creative<\/a>
\nSauf pour les sections sp\u00e9cifi\u00e9es autrement, ce travail est sous licence Creative Commons Attribution 4.0 International<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Introduction Avoir une bonne repr\u00e9sentation de la performance d’un algorithme est un \u00e9l\u00e9ment important pour un programmeur et, malheureusement, \u00e9valuer cette performance est g\u00e9n\u00e9ralement tr\u00e8s difficile et peu intuitif. Il ne suffit pas de diminuer le nombre de lignes de code pour augmenter la performance. En fait, il arrive souvent que des algorithmes plus performants… Continue reading La complexit\u00e9 algorithmique<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-399","page","type-page","status-publish","hentry","entry"],"_links":{"self":[{"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/pages\/399","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/comments?post=399"}],"version-history":[{"count":3,"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/pages\/399\/revisions"}],"predecessor-version":[{"id":403,"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/pages\/399\/revisions\/403"}],"wp:attachment":[{"href":"https:\/\/www.louismarchand.me\/index.php\/wp-json\/wp\/v2\/media?parent=399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}