Introduction à la complexité algorithmique – 2/2

Dans l’épisode précédent, j’ai expliqué deux manières de trier des livres et j’ai tenté de justifier combien de temps, en nombre d’opérations élémentaires, ça me prenait de faire ça, et j’ai évalué le nombre maximum d’opérations en fonction du nombre de livres que j’avais à trier.

Je suis arrivée aux conclusions suivantes :

  • pour le « premier » tri, celui où je regarde à chaque étape où je dois mettre le livre suivant en parcourant tous les livres que j’ai mis jusqu’ici, j’ai, dans le meilleur des cas, 2n – 1 opérations, dans le pire des cas (n² + n)/2 opérations, et dans le cas moyen (n²+9n)/4 opérations.
  • pour le « deuxième » tri, celui où je combine mes ensembles de livres deux par deux, j’ai, dans tous les cas, 2*n*log(n) opérations.

Je vais me permettre une petite courbe ici parce que les courbes c’est joli.

complexities

Au cas où j’aurais des daltoniens parmi mes lecteurs, les courbes sont, de haut en bas, dans l’ordre de la légende.

Cette histoire de « meilleur cas, pire cas, cas moyen » est très utilisée pour parler de la complexité des algorithmes. On ne s’intéresse en général que peu au « meilleur cas », parce qu’en général, Murphy aidant, c’est rarement le cas qui arrive. (Même si on peut éventuellement se poser la question de « comment faire pour avoir le meilleur cas plus souvent ? » si ça peut faire une différence pour l’algorithme.) En général, on s’intéresse plutôt au cas moyen et au pire cas.

L’avantage de s’intéresser au pire cas, c’est que c’est le seul qui fournit des garanties. Si je dis que mon algorithme, dans le pire cas, s’exécute en tant de temps, je garantis qu’il ne sera jamais plus long que ça, même s’il lui arrive d’être plus rapide. Dans certains cas, on a besoin de ce genre de garanties. En particulier, on s’intéresse parfois (dans le domaine de la cryptographie en particulier) à ce qu’il se passe si un « adversaire » me fournit les données comme il veut, et de préférence de manière à compliquer ma vie le plus possible. Et on veut des garanties sur le fait que ce qu’on fait fonctionne comme on veut que ça fonctionne, même quand on a un adversaire en face qui fait tout pour nous pourrir la vie. L’inconvénient, c’est qu’on surestime souvent le temps d’exécution « usuel » si on prend en compte le pire cas, et qu’on peut se retrouver à le surestimer de beaucoup.

L’avantage de s’intéresser au cas moyen, c’est justement qu’on a une idée de ce qui se passe « normalement ». (Je fais beaucoup de raccourcis et je dis probablement des choses qui ne sont pas vraies dans le cas général, mais dans l’idée c’est pas si délirant que ça). Ça donne aussi une idée de ce qui se passe si on répète l’algorithme plusieurs fois sur des données indépendantes ; le temps moyen d’une exécution sera quelque part entre le meilleur cas et le pire cas. L’autre avantage de s’intéresser au cas moyen, c’est qu’il y a parfois des manières « simples » d’éviter au maximum le pire cas. Par exemple, si j’ai un adversaire qui me donne les livres dans un ordre qui me pourrit mon algorithme, je peux « compenser » ça par le fait de mélanger moi-même les livres au début pour que la probabilité d’être dans un « mauvais » cas soit faible (et ne dépende pas de ce que me fournit mon adversaire). L’inconvénient, c’est évidemment qu’on n’a aucune garantie sur le temps « maximum » que prend un algorithme.

Évidemment, ce qu’on fait au final dépend de ce qu’on veut faire (fou, non ?).

Ceci étant posé, les complexités, en nombre d’opérations, que j’ai données précédemment (2n-1, (n²+n)/2, (n²+9n)/4, 2n log(n)) ne sont pas celles qu’on utilise en général. Si on me demande les résultats précédents, je réponds que les complexités sont, respectivement, « n » (ou « linéaire »), « n² » (ou « quadratique »), « n² » et « n log n ». Ça peut paraître extrêmement approximatif et peu précis et tout ce genre de choses, et je dois dire que les premières fois que j’ai vu ce genre d’approximations, ça m’a agacée au plus haut point. Bon, le fait que c’était en cours de physique avait probablement un rapport avec ça, mais, bon. Depuis, je trouve que c’est drôlement pratique et même que ça a du sens. Il faut savoir, déjà, que le fait que « ça a du sens » a une justification mathématique solide. Je ne vais pas la donner ici, parce que c’est très nettement au-dessus du niveau du billet que je suis en train de vouloir écrire. Pour les gens intéressés, qui lisent l’anglais, et qui ont pas peur des trucs du genre « limite en plus l’infini de blah », il y a http://en.wikipedia.org/wiki/Big_O_notation (ou son pendant en français, http://fr.wikipedia.org/wiki/Comparaison_asymptotique, mais je trouve la version anglaise plus claire).

Bon, sinon, j’ai au moins deux trucs à tenter de justifier ici. Attention, ce que je vais faire ici est très, très peu rigoureux. La première question est celle de ce qui arrive aux « petits » termes. L’idée, c’est que je ne garde que ce qui « compte » dans le fait que mon nombre d’opérations augmente avec le nombre d’éléments à trier. Par exemple, si j’ai 750 livres à trier, et que je veux faire ça avec mon premier algorithme, dans le cas « moyen », j’ai (n²+9n)/4 opérations, c’est à dire n²/4 + 9n/4. Pour 750 livres, ces deux « morceaux » valent, respectivement, 140625 et… 1687. Si j’ai 1000 livres à trier, je monte à 250000 et 2250. Le premier « morceau » de l’expression est beaucoup plus gros, et il grandit beaucoup plus vite. Si je veux estimer le temps que ça me prend, sans avoir besoin de trop de précision, je peux prendre le n²/4 et laisser tomber le 9n/4 – déjà pour 1000 livres, le nombre d’opérations du 9n/4 correspond à moins de 1% du total.

La deuxième question est plus compliqué (à mon sens) : pourquoi est-ce que je considère identiques « n² » et « n²/4 », « 2 n log n » et « n log n » ? Encore une fois, il y a une justification mathématique derrière tout ça, que je vais tenter d’éviter de vous infliger. Mais on peut tenter de le justifier aussi en faisant de grands moulinets. (Je ne suis pas très satisfaite de mes explications ici, mais je ne trouve pas mieux. Si un Gentil Lecteur a mieux, qu’il n’hésite pas à expliquer dans les commentaires 🙂 ).

L’idée, c’est qu’on ne s’intéresse pas nécessairement à un algorithme « tout seul », mais à comparer différents algorithmes. Et, en particulier, on s’intéresse à la comparaison dite « asymptotique », c’est à dire à ce qu’il se passe quand on a un très grand nombre d’éléments en entrée de l’algorithme (par exemple un très grand nombre de livres à trier). Et si j’ai un très grand nombre de livres à trier, j’aimerais autant que ça me prenne le moins de temps possible, et donc je cherche le « meilleur » algorithme, celui qui va le plus vite.

Pour que ça me prenne le moins de temps possible, j’ai deux solutions. Ou bien je réduis le temps que chaque opération prend, ou bien je réduis le nombre d’opérations lui-même. Je prends mon algorithme 1, qui fait n²/4 opérations, et mon algorithme 2, qui fait 2 n log n opérations pour n éléments. Supposons que j’aie un ordinateur qui fait une opération en une seconde, et que je veuille trier 100 éléments. Avec le premier algorithme, ça lui prendra environ 2500 secondes. Avec le deuxième algorithme, ça lui prendra environ 1328 secondes (parce que 2*100*log(100) est environ égal à 1328).  Maintenant, supposons que j’aie un ordinateur vachement plus rapide sur lequel faire fonctionner mon premier algorithme. Au lieu de prendre une seconde, cet ordinateur est cinq fois plus rapide et il peut effectuer une opération en un cinquième de seconde (0.2 seconde). Du coup, je peux trier mes 100 éléments en 0.2*100²/4 = 500 secondes, ce qui est plus rapide que ce que je peux faire avec l’autre ordinateur. Youpi. Mais il y a évidemment deux bémols à ça. Le premier bémol, c’est que si je mets mon deuxième algorithme sur le deuxième ordinateur aussi, je peux trier mes éléments en 0.2*2*100*log(100) = 265 secondes. Bon, supposons que pour une raison bizarre le deuxième algorithme ne fonctionne pas sur le deuxième ordinateur et qu’il faille que je le garde sur le premier ordinateur. Mais le deuxième bémol, c’est que si j’ai maintenant 1000 éléments à trier et non plus 100, ça va me prendre, avec le premier algorithme sur l’ordinateur vachement plus rapide, 0.2*1000²/4 = 50000 secondes, et avec le deuxième algorithme sur l’ordinateur vachement plus lent, 2*1000*log(1000) = 19931 secondes.

Et c’est un peu l’idée qu’il y a derrière la suppression des « nombres multiplicateurs » dans mon évaluation de complexité. Si j’ai un algorithme qui s’exécute avec une complexité « dans les n² » et un algorithme qui s’exécute avec une complexité « dans les n log n », je peux mettre l’ordinateur le plus puissant que je veux derrière le premier algorithme, il y aura toujours un nombre d’éléments pour lequel mon deuxième algorithme, même sur une machine très lente, ira plus vite que le premier. Le nombre d’éléments peut être très grand si la première machine est très rapide et la deuxième très lente, mais, comme je m’intéresse à ce qu’il se passe avec de très grands nombres d’éléments, c’est pas très grave.

Donc, quand je parle de comparer deux algorithmes, il est beaucoup plus intéressant de voir que j’en ai un dont le temps d’exécution est en n log n et un en n², que de pinailler sur la constante (le nombre) qui va devant le n log n ou le n².

Évidemment, pour deux algorithmes en n², on peut se poser la question de la constante qui va devant. En pratique, ça se fait assez peu, parce qu’à moins d’avoir des choses extrêmement simples et carrées (et encore), suivant la manière dont on implémente les choses (avec un langage de programmation), déterminer ladite constante devient très difficile. Il faut aussi se poser la question, exactement, de ce qu’est une opération. Il y a des modèles « classiques » qui permettent de définir tout ça, mais relier ces modèles aux langages de programmation actuels doit tenir à peu près de l’utopie.

Bon, et en tant que « gens qui font de l’algorithme », qu’est-ce qui nous plaît bien, qu’est-ce qui commence à nous faire grimacer, et qu’est-ce qui nous fait courir à toute vitesse dans l’autre sens ? Je donne tout ça en fonction de la « taille » de l’entrée, n ; pour mon exemple de tri, c’est le nombre d’éléments à trier. Si je fais des opérations sur des graphes, la taille de l’entrée va typiquement être le nombre de sommets du graphe, parfois le nombre d’arcs.

Les algorithmes « en temps constant » et « logarithmiques » (donc avec soit un nombre d’opérations constant, soit un nombre d’opération de type log n) sont relativement rares, parce qu’avec log n opérations (ou un nombre constant d’opérations), on n’a même pas le temps de regarder tout ce qu’on a en entrée. Donc, quand on trouve un algorithme de ce type, on est très très content. Un exemple « classique » d’algorithme qui fonctionne en temps logarithmique, c’est celui de chercher un élément dans une liste triée. Quand la liste est triée, on n’a pas besoin de lire toute la liste pour trouver l’élément qu’on cherche. On peut commencer par regarder s’il est avant ou après le milieu, regarder s’il est avant ou après le milieu de l’intervalle qu’on vient de redéfinir, et ainsi de suite. Je pourrais refaire une belle explication avec un arbre si ça vous intéresse, mais je vais pas faire ça maintenant.

On est aussi en général très content quand on trouve un algorithme linéaire (« n »). Ça veut dire, quelque part, qu’on lit tout ce qu’on a en entrée, on fait quelques opérations par élément, et paf c’est fini. n log n est aussi généralement considéré comme « acceptable ». C’est une borne importante, parce qu’on peut prouver que, dans les modèles algorithmiques courants (qui reviennent plus ou moins à compter des opérations « basiques »), on ne peut pas trier n éléments plus rapidement qu’en n log n opérations dans le cas général, c’est-à-dire sans rien savoir sur les éléments en question (Parce que si je sais qu’ils sont triés, ou dans l’ordre inverse, je peux les trier en temps linéaire). Du coup, il y a un certain nombre d’algorithmes qui s’appuient, à un moment ou un autre, sur un tri ; si on ne peut pas se débarrasser du tri, on ne peut pas non plus descendre en-dessous de n log n.

On commence à grommeler un peu à partir de n², n³, et à grommeler beaucoup sur les puissances supérieures de n. Les algorithmes qui peuvent s’exécuter en un temps n^k, pour une valeur quelconque de k (y compris 1000000) sont appelés « polynomiaux ». L’idée, c’est que, de la même manière qu’un algorithme en n log n finira par être plus efficace qu’un algorithme en n², en prenant un entrée suffisamment grande, un algorithme polynomial, quel que soit k, finira par être plus efficace qu’un algorithme en 2^n. Ou même en 1.308^n. Ou même en 1.01^n.

Évidemment, en pratique, ce genre de raisonnement a ses limites aussi. J’ai un exemple qui m’amuse personnellement beaucoup, et j’espère qu’il vous amusera aussi. Considérons le problème de la multiplication de deux matrices entre elles. (Pour les gens qui n’ont pas jamais vu de matrices, on peut voir une matrice comme un tableau de nombres – et il se trouve qu’on peut multiplier ces tableaux de nombres. C’est un peu plus compliqué que de multiplier les nombres un par un, mais guère.) (Dit la fille qui savait pas comment multiplier deux matrices avant la 3e année d’école d’ingénieur, mais c’est une autre histoire.)

L’algorithme qu’on apprend à l’école permet de multiplier deux matrices en un temps n³, où on considère des matrices de taille n*n (pour les gens pas familiers des matrices : on trace un tableau de n lignes et n colonnes, et on met des nombres dedans). En se forçant un peu, on peut trouver un algorithme (algorithme de Strassen, de son petit nom), pas trop compliqué, qui fonctionne en un temps n^{2.807} (ce qui est meilleur que le n³). Et en se forçant beaucoup, il existe un algorithme qui fonctionne en temps n^{2.3727} (Coppersmith–Winograd et ses dérivés). C’est, je crois, le seul algorithme pour lequel j’ai entendu PLUSIEURS personnes faisant de la théorie dire que « oui, mais vraiment, la constante est vraiment dégueulasse » - en parlant du nombre par lequel on multiplie ce n^{2.3727} pour avoir le temps d’exécution « réel ». Pour les raisons données précédemment, on ne connaît pas vraiment la constante en question, on sait juste qu’elle est dégueulasse. En pratique, de ce que je sais (peut-être que certains de mes lecteurs ont des avis plus tranchés sur la question), les algorithmes « rapides » de multiplication de matrice utilisent celui de Strassen (ou une variante), parce qu’à cause de la constante en question, les tailles de matrices pour lesquelles Coppersmith-Winograd serait « rentable » sont énormes, et peu utiles en pratique.

Voilà, sur cette anecdote amusante, je vais arrêter là pour ce billet. J’espère que c’était approximativement compréhensible, ce dont je ne suis pas vraiment sûre. N’hésitez pas à poser des questions, faire des remarques et tout ce genre de choses 🙂

Introduction à la complexité algorithmique – 1/2

Bon, ça y est, j’ai fini les deux billets qui savaient à peu près où ils allaient (un billet général sur l’informatique théorique, et un billet pour expliquer ce qu’est un logarithme parce que c’est toujours utile). Et après on a fait une petite pause, parce que bon. Donc maintenant je vais rentrer dans les choses un peu plus compliquées, et qui me sont plus difficiles à expliquer aussi. Donc j’écris, et puis on verra bien ce que ça donne à la fin. Ajoutons à cela que je veux essayer d’expliquer les choses en évitant au maximum le formalisme mathématique qui m’est maintenant « naturel » (mais croyez-moi, il a fallu me le rentrer dans le crâne à coups de marteau) : je sais vraiment pas ce que ça va donner. J’ai aussi décidé de couper ce billet en deux, parce qu’il est déjà fort long comme ça. Je pense que le deuxième sera plus court.

J’ai déjà défini un algorithme comme étant une suite bien définie d’opérations qui permettent d’arriver à un résultat. Je ne vais pas aller beaucoup plus loin dans la définition formelle, parce que je pense que ce n’est pas utile - du moins pas pour le moment. Et je vais définir, également de façon très peu formelle, la complexité algorithmique comme la quantité de ressources qu’il me faut pour exécuter mon algorithme. Par ressources, j’entendrai le plus souvent « le temps », c’est-à-dire le temps qu’il me faut pour exécuter un algorithme, parfois « l’espace », c’est à dire la quantité de mémoire (pensez-y comme à de la mémoire vive ou du disque dur) qu’il me faut pour exécuter mon algorithme.

Je vais prendre un exemple très classique pour illustrer mon propos, qui est celui du tri. Et pour donner un exemple concret de cet exemple classique, supposons que j’aie une bibliothèque pleine de livres. (Une supposition absolument et complètement folle.) Et qu’il me vienne l’idée sotte et complètement grenue de vouloir les trier, disons par ordre alphabétique de nom d’auteur (et de titre à nom d’auteur égal). Je dis qu’un livre A est « plus petit » qu’un autre livre B s’il doit être rangé avant dans la bibliothèque, et qu’il est « plus grand » s’il doit être rangé après. Avec cette définition, les bouquins d’Asimov sont plus petits que les bouquins de Clarke qui sont plus petits que les bouquins de Pratchett. Je vais garder cet exemple pendant tout le billet et je vais faire le parallèle avec les notions algorithmiques correspondantes.

Je commence donc par définir ce dont je parle. L’algorithme que j’étudie, c’est l’algorithme de tri ; c’est celui qui me permet de passer d’une bibliothèque en bordel à une bibliothèque rangée dans l’ordre alphabétique. En « entrée » de mon algorithme, c’est-à-dire les données que je donne à traiter à mon algorithme, j’ai une bibliothèque en bordel. En « sortie » de mon algorithme, j’ai les données traitées par mon algorithme, c’est-à-dire une bibliothèque rangée.

La première chose qu’on peut remarquer, c’est que plus on a de livres, plus c’est long à trier. Ça vient de deux choses. La première, c’est que si on considère une opération « élémentaire » du tri (par exemple, mettre le livre dans la bibliothèque), c’est plus long de faire ça 100 fois que 10 fois. La deuxième, c’est que si on considère tout ce qu’on fait pour chaque livre, plus il y a de livres, plus c’est long à faire. C’est plus long de chercher quel est le bon emplacement pour un livre parmi 100 que parmi 10.

Et voilà ce à quoi on s’intéresse ici : la manière dont le temps nécessaire à obtenir une bibliothèque rangée évolue en fonction du nombre de livres ou, de façon plus générale, la manière dont le temps nécessaire à obtenir une séquence triée d’éléments dépend du nombre d’éléments à trier.

Ce temps dépend de la méthode de tri qu’on utilise. Par exemple, on peut choisir une méthode de tri très très longue : tant que la bibliothèque n’est pas triée, on remet tout par terre et on met les livres dans un ordre aléatoire dans la bibliothèque. Pas trié ? On recommence. Ça, typiquement, ça va être très long. À l’autre bout du spectre, on a Mary Poppins : un Supercalifragilistic, et paf, la bibliothèque est rangée. La méthode Mary Poppins a d’ailleurs une particularité : elle ne dépend pas du nombre de livres à ranger. On dit que Mary Poppins s’exécute en « temps constant » : quel que soit le nombre de livres à ranger, ils seront rangés dans la seconde. En pratique, il y a bien une raison pour laquelle la méthode Mary Poppins fait rêver, c’est bien que c’est magique et difficilement réalisable en réalité.

Revenons, donc, à la réalité, et aux algorithmes de tri autres que Mary Poppins. Pour analyser la manière dont mon tri marche, je considère trois opérations élémentaires dont je peux avoir besoin pendant que je range :

  • comparer deux livres pour savoir si l’un se range avant ou après l’autre
  • mettre le livre dans la bibliothèque
  • et, en supposant que mes livres en bordel soient en bordel sur une table, le déplacement d’un livre sur la table.

Et je vais supposer aussi que ces trois opérations prennent le même temps, disons une seconde. Ça ne serait pas très efficace pour un ordinateur, mais je pense que c’est plutôt efficace pour un humain, et ça donne une idée. Je vais aussi supposer que ma bibliothèque est un peu magique, c’est-à-dire que ses rayonnages s’adaptent tous seuls et que les livres s’y placent sans avoir de problème de « rha, j’ai plus de place sur cette étagère, il faut que je descende des bouquins sur celle d’en-dessous, qui est pleine aussi, et là c’est le drame ». Pareil, ma table est magique, et déplacer un livre où je veux ne pose pas de problème. En pratique, il faudrait se poser ce genre de questions, y compris d’un point de vue algorithmique (quelle est la pénalité d’avoir à faire ça, est-ce que je peux l’éviter en étant malin). Mais comme je ne suis pas en train d’écrire un billet sur les tris mais sur la complexité algorithmique, je simplifie. (Et pour ceux qui savent de quoi je parle, oui, je sais que mon modèle est discutable. C’est un modèle, c’est mon modèle, je fais ce que je veux avec, et les explications restent valides dans mon modèle même s’il est discutable).

Un premier tri

Voici maintenant une première manière de trier. Je suppose que j’ai vidé ma bibliothèque en bordel sur ma table, et que je veux ranger les bouquins un par un. Le scénario suivant est assez peu réaliste pour un humain qui, probablement, se souviendrait approximativement de l’endroit où mettre le livre, mais essayez d’imaginer la situation suivante.

  1. Je prends mon premier bouquin, je le mets dans la bibliothèque.
  2. Je prends un deuxième bouquin, je compare avec le premier : s’il doit être rangé avant, je le mets devant, s’il doit être rangé après, je le mets après.
  3. Je prends le troisième bouquin, je compare avec le premier. S’il doit être rangé avant, je le mets en première position. S’il doit être rangé après, je compare avec le deuxième bouquin que j’ai rangé. S’il doit être rangé avant, je le mets entre le bouquin 1 et le bouquin 2. S’il doit être rangé après, je le mets en dernière position.
  4. Et ainsi de suite, jusqu’à ce que ma bibliothèque soit rangée. À chaque livre que j’insère, je compare, dans l’ordre, avec les livres déjà en place, et je l’insère entre le dernier livre qui est « plus petit » et le dernier livre qui est « plus grand ». 

Et maintenant, je me demande combien de temps ça prend si j’ai, mettons, 100 livres, ou un nombre quelconque de livres. Je vais donner la réponse dans les deux cas : pour 100 livres et pour un nombre n de livres. Le temps pour n livres sera une fonction du nombre de livres, et c’est ce qui m’intéresse vraiment ici, ou plutôt ce qui m’intéressera vraiment dans le deuxième billet de cette introduction.

La réponse est que ça dépend de l’ordre dans lequel mes livres étaient au début quand ils étaient sur ma table. Il peut arriver, pourquoi pas, qu’ils étaient déjà triés. J’aurais peut-être dû vérifier ça avant de tout poser sur la table, ça aurait été plus malin, mais je n’y ai pas pensé avant. Il se trouve que c’est la pire chose qui puisse m’arriver avec cet algorithme, parce qu’à chaque fois que je veux ranger un livre, comme il est plus grand que tous ceux que j’ai rangés avant, il faut que je compare avec tous les livres que j’ai rangés avant. Comptons :

  1. Je mets le premier livre dans la bibliothèque. Nombre d’opérations : 1.
  2. Je compare le deuxième livre avec le premier livre. Je le mets dans la bibliothèque. Nombre d’opérations : 2.
  3. Je compare le troisième livre avec le premier livre. Je compare le troisième livre avec le deuxième livre. Je le mets dans la bibliothèque. Nombre d’opérations : 3.
  4. Je compare le quatrième livre avec le premier livre. Je compare le quatrième livre avec le deuxième livre. Je compare le quatrième livre avec le troisième livre. Je le mets dans la bibliothèque. Nombre d’opérations : 4.
  5. Et ainsi de suite. À chaque fois que j’insère un livre, je le compare avec tous les livres qui l’ont précédé ; quand j’insère le 50e livre je fais donc 49 comparaisons, plus l’ajout du livre dans la bibliothèque, 50 opérations.

Donc pour insérer mes 100 livres, s’ils sont dans l’ordre au début, il me faut 1+2+3+4+5+…+99+100 opérations. Il se trouve, et je vais vous demander de me croire sur parole ici (c’est facile à démontrer, mais c’est pas l’objet) que 1+2+3+4+5+…+99+100, ça fait exactement (100*101)/2 = 5050 opérations. Et que, si je n’ai plus 100 livres, mais n livres qui se trouvent être dans l’ordre, il me faut n*(n+1)/2 = (n² + n)/2 opérations.

Supposons maintenant que mes livres étaient exactement dans l’ordre inverse duquel ils doivent être rangés. Ben cette fois ci, c’est la meilleure chose qui puisse m’arriver avec cet algorithme, parce que le livre que j’ajoute est toujours plus petit que tous ceux que j’ai rangés avant, donc il suffit de comparer avec le premier livre.

  1. Je mets le premier livre dans la bibliothèque. Nombre d’opérations : 1.
  2. Je compare le deuxième livre avec le premier livre. Je le mets dans la bibliothèque. Nombre d’opérations : 2.
  3. Je compare le troisième livre avec le premier livre. Je le mets dans la bibliothèque. Nombre d’opérations : 2.
  4. Et ainsi de suite : je compare toujours avec le premier livre, il est toujours plus petit, et j’ai toujours 2 opérations.

Donc si mes 100 livres sont exactement dans l’ordre inverse, je fais 1+2+2+2+…+2 = 1 + 99*2 opérations = 199 opérations. Et, si j’ai n livres dans l’ordre inverse, il me faut 1+2*(n-1) = 2n – 1 opérations.

C’est à partir d’ici que ça se corse un peu, parce que la situation devient moins bien définie, et que je vais commencer à faire des approximations dans tous les sens. J’essaie de justifier à chaque fois les approximations que je fais et pourquoi elles sont valides ; il est possible, cependant, que je zappe quelques étapes. N’hésitez pas à râler dans les commentaires si je suis complètement partie en sucette, parce que j’ai un peu de mal à me rendre compte :-/

Je vais maintenant supposer que mes livres en bordel sont dans un état qui fait que, à chaque fois que j’ajoute un livre, il est inséré à peu près au milieu de ce qui a déjà été trié. (Je dis à peu près parce que si j’ai trié 5 livres, je vais typiquement ranger le 6e après le 2e ou après le 3e livre – les emplacements sont entiers, je vais pas le ranger après le 2.5e livre). Supposons que j’insère le livre numéro i ; j’estime le nombre de comparaisons que je fais à i/2 + 1, qui est supérieur ou égal au nombre de comparaisons que je fais effectivement. Pour voir ça, je distingue sur le fait que i soit pair ou impair. On peut montrer que ça marche pour tous les nombres ; je vais juste donner deux exemples pour expliquer qu’effectivement ça a de bonnes chances de marcher.

Si j’insère le 6e livre, j’ai 5 livres déjà rangés ; supposons que je veuille le ranger après le 3e livre (au « presque milieu »), je fais 4 comparaisons (parce qu’il est plus grand que le premier, deuxième, troisième livre, mais plus petit que le 4e) ; on a i/2 + 1 = 6/2+1 = 4.

Si j’insère le 7e livre, j’ai 6 livres déjà rangés, je veux le ranger après le 3e livre aussi (exactement au milieu), je fais également 4 comparaisons, et j’ai i/2+1 = 7/2 + 1 = 4.5.

Donc, je vais estimer le nombre d’opérations qu’il me faut pour ranger 100 livres, en comptant « large », et en me permettant des « demis-opérations ». Le but du jeu n’est pas ici de dénombrer exactement, mais d’avoir un ordre de grandeur, qui se trouvera être supérieur au nombre exact d’opérations.

  • Livre 1 : 1/2+1 = 1.5, plus le rangement, 2.5 opérations (je n’ai pas besoin de comparer, en fait, ici ; je le fais quand même parce que ça me facilite les calculs à la fin)
  • Livre 2 : 2/2 + 1 = 2, plus le rangement, 3 opérations (pareil ici, j’ai une comparaison de trop, parce que je n’ai qu’un seul bouquin de rangé, mais encore une fois je ne suis pas à un près).
  • Livre 3 : 3/2 + 1 = 2.5, plus le rangement, 3.5 opérations
  • Livre 4 : 4/2 + 1 = 3, plus le rangement, 4 opérations

Si je continue comme ça et que je range un peu mes calculs, j’ai, pour 100 livres, au plus

(1+2+3+4+…+99+100)/2 + 100 + 100 = (100*101/2)/4 + 200 = 2725 opérations.

Le premier élément de ma somme vient du « i/2 » que j’ai dans tous mes calculs de nombre de comparaisons. Le premier 100 vient du « 1 » que j’ajoute chaque fois que je compte les comparaisons (et je fais ça 100 fois), le deuxième 100 vient du « 1 » que j’ajoute à chaque fois que je compte le rangement des livres, et que je fais également 100 fois.

Ce 2725 est un peu surestimé, mais « de peu » : pour les deux premiers livres, j’ai exactement 2.5 comparaisons de trop ; pour les autres, j’ai au pire 0.5 comparaisons de trop. Sur 100 livres, ça fait donc au plus 98*0.5 + 2.5 = 51.5 opérations comptées en trop ; mon nombre exact d’opérations est donc compris entre 2673 et 2725. Il y aurait moyen de faire les choses un peu plus précisément, mais on verra par la suite (dans le prochain billet) pourquoi ça n’a pas grand intérêt.

Si je compte pour n livres, j’arrive à une estimation de (n*(n+1)/2)/2 + 2*n = (n²+9n)/4 opérations.

On peut montrer (mais pour le coup ça prendrait vraiment des proportions ici) que ce comportement est à peu près celui qu’on a quand on a des livres dans un ordre aléatoire. L’idée, c’est que si mes livres sont dans un ordre aléatoire, je vais en insérer certains plutôt au début, d’autres plutôt à la fin, et donc, « en moyenne », à peu près au milieu.

Une autre méthode de tri

Je vais maintenant expliquer une autre méthode de tri, qui est probablement moins facile à conceptualiser, mais qui je pense est la méthode la plus simple qui me permet de continuer mon argument.

Je vais supposer, cette fois, que je n’ai pas 100 livres à trier, mais 128. Parce que c’est une puissance de 2 et que ça me facilite la vie pour mon exemple concret. Et parce que j’y ai pas pensé avant et que j’ai la flemme de remonter dans mon exemple pour repartir sur 128 plutôt que 100.

Je suppose que tous mes livres sont sur la table, directement posés dessus, et je vais faire des « ensembles » avant de ranger mes bouquins dans la bibliothèque. Et je vais faire ces ensembles d’une façon un peu bizarroïde, mais efficace.

Je commence par combiner mes livres deux par deux. Je prends deux livres, je les compare, je mets le plus petit à gauche et le plus grand à droite. À la fin de cette opération, j’ai 64 ensembles de deux livres, avec dans chaque ensemble un petit livre à gauche et un grand livre à droite. Pour faire cette opération, j’ai dû faire, en tout, 64 comparaisons, et 128 déplacements de livres (je suppose que je déplace toujours les livres, ne serait-ce que pour les prendre en main et lire les auteurs/titres).

Ensuite, je prends mes ensembles de deux livres, et je les combine aussi de façon à avoir des ensembles de 4 livres, toujours ordonnées. Pour faire ça, je compare les deux premiers livres de deux ensembles, le plus petit des deux devient le premier livre de mon nouvel ensemble de 4. Je compare ensuite le livre restant de l’ensemble de 2 avec le premier livre de l’ensemble de 2, et je mets le plus petit en 2e position de mon ensemble de 4. Là, il peut se passer deux choses. Ou bien il me reste un livre dans chacun des ensembles initiaux ; auquel cas, je les compare, et je les mets dans l’ordre dans mon ensemble de 4. Ou bien il me reste un ensemble de deux ; je peux alors me contenter de les ajouter à la fin de mon ensemble de 4 et j’ai mon ensemble de 4. Voilà deux petits dessins qui distinguent les deux cas ; chaque carré représente un livre dont l’auteur a un nom commençant par la lettre indiquée, chaque rectangle représente mes ensembles de livres (les initiaux de 2 et le final de 4 livres), et les éléments rouges sont ceux qui sont comparés à chaque étape.

mergesort-1

mergesort-2

Bref, pour chaque ensemble de 4 que je crée, je dois faire 4 déplacements, et 2 ou 3 comparaisons. Je termine cette opération avec 32 ensembles de 4 livres ; donc au final je fais 32*4 = 128 déplacements et entre 32*2 = 64 et  32*3 = 96 comparaisons.

Je crée ensuite 16 ensembles de 8 livres, également en comparant le premier élément de chaque ensemble de livres et en créant un ensemble commun trié. Pour combiner deux ensembles de 4, il me faut 8 déplacements et entre 4 et 7 comparaisons. Je ne vais pas rentrer dans le détail de la manière d’obtenir ces chiffres ; la manière la plus simple avec ce genre de chiffres est d’énumérer tous les cas, ça commence à être fastidieux à 4, mais c’est encore gérable. Donc pour créer les 16 ensembles de 8 livres, il faut que je fasse 16*8 = 128 déplacements et entre 16*4 = 64 et 16*7 = 112 comparaisons.

Et je continue comme ça jusqu’à avoir 2 ensembles de 64 livres, que je finis par combiner (directement dans la bibliothèque pour gagner du temps) pour obtenir une bibliothèque rangée.

Bon, et combien de temps ça me prend cette affaire ? Je vais déjà commencer par donner une estimation pour 128 livres, et après je regarderai ce que ça donne pour n livres. Le plus pénible, ça ne surprendra personne, est d’évaluer le nombre de comparaisons quand on combine deux ensembles de livres. Je vais me permettre une approximation de plus pour dire que, si je veux combiner deux ensembles qui font chacun k éléments en un gros ensemble qui fait 2*k éléments, il me faut au plus 2*k comparaisons. Pour voir ça, on peut essayer de raisonner par énumération et faire une preuve propre et tout. J’avoue que j’ai pas le courage, d’autant plus que je sais où mon raisonnement va, et que je sais que j’ai pas envie de faire des calculs précis, parce qu’au final c’est pas très important d’être précis. On peut aussi faire l’observation suivante : à chaque fois qu’on fait une comparaison, on pose un bouquin dans le « gros » ensemble. Comme je ne pose que 2*k livres, je ne peux pas faire plus de 2*k comparaisons : si je faisais, par exemple, 2*k+1 comparaisons, il faudrait que je pose 2*k+1 livres… et je ne les ai pas. Donc, je vais estimer qu’à chaque fois que je combine deux ensembles de k éléments chacun en un ensemble de 2*k éléments, je fais au maximum 2*k comparaisons, et que je fais exactement 2*k déplacements. La deuxième observation, pour aller un peu plus loin et gagner encore un peu de temps dans les estimations, c’est qu’à chaque fois que je combine mes ensembles de k éléments en ensembles de 2*k éléments, je pose, en tout, exactement 128 livres (puisque c’est le nombre total de livres que j’ai, que chaque livre est dans un « petit » ensemble au départ et qu’il arrive dans un « grand » ensemble). Donc, je ne fais, au maximum, que 128 comparaisons à chaque étape.

Il me reste donc à compter le nombre d’étapes.

Pour 128 livres, ça me fait donc, au maximum :

  1. Passer de 128 ensembles de 1 à 64 ensembles de 2 
  2. Passer de 64 ensembles de 2 à 32 ensembles de 4
  3. Passer de 32 ensembles de 4 à 16 ensembles de 8
  4. Passer de 16 ensembles de 8 à 8 ensembles de 16
  5. Passer de 8 ensembles de 16 à 4 ensembles de 32
  6. Passer de 4 ensembles de 32 à 2 ensembles de 64
  7. Passer de 2 ensembles de 64 à 1 ensemble de 128

Soit 7 étapes. Dans chacune de ces 7 étapes, j’ai 128 déplacements, et au maximum 128 comparaisons, soit au maximum 7*(128+128) = 1792 opérations. Notons que je n’ai fait ici aucune hypothèse sur l’ordre initial des livres. À comparer avec les 5050 opérations du « pire cas » du tri précédent, ou avec les environ 2700 opérations du cas « moyen » – nombres qui étaient d’ailleurs calculés pour 100 livres et pas 128 - pour 128 livres, on aurait, respectivement, 8256 opérations pour le « pire cas » et environ 4300 opérations pour le cas moyen.

Qu’en est-il exactement de la formule générale pour n livres ? Je pense qu’on peut être d’accord sur le fait que, à chaque étape, on déplace n livres, et qu’on fait au plus n comparaisons (puisque chaque comparaison correspond au fait de poser un livre). Donc, à chaque étape, je fais au plus 2*n comparaisons. La question est maintenant de savoir combien d’étapes on fait. Et c’est ici que mon splendide billet sur les logarithmes (kof) m’est utile. Est-ce que vous pouvez voir la similarité avec la figure suivante ?

arbre

Et si je dis que les feuilles de l’arbre sont les livres en bordel avant la première étape ? C’est plus clair ? (J’espère…). Au niveau d’au-dessus, les feuilles (livres) sont combinées en ensembles de deux, qu’on combine au niveau d’au-dessus en ensembles de quatre, etc… jusqu’à n’avoir qu’un seul ensemble qui contient tous les livres. Et le nombre d’étapes est précisément égal au logarithme (en base 2) du nombre de livres, ce qui correspond à la « profondeur » (le nombre de niveaux) de l’arbre en question.

Donc, pour conclure, pour n livres, j’ai, dans le modèle que j’ai défini, 2*n*log(n) opérations (où mon log est en base 2).

Voilà, je vais arrêter là pour ce premier billet. Dans le billet suivant, j’expliquerai pourquoi je ne me suis pas trop fatiguée à faire des calculs complètement exacts et pourquoi la phrase que je prononce probablement le plus souvent c’est « pff, c’est une constante, on s’en fout ». (Et peut-être aussi pourquoi des fois on s’en fout pas tant que ça 🙂 ). J’espère que c’était à peu près compréhensible jusqu’ici ; sinon, n’hésitez pas à râler, poser des questions, et tout ce genre de choses. Moi en tous cas je trouve ça rigolo d’écrire tout ça 🙂