En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine RousseauFévrier : Ça va être long ?
Si vous installez parfois des logiciels, vous avez forcément remarqué que la petite barre qui vous indique le temps restant est franchement mensongère. Elle semble avancer à sa guise, sans aucun rapport avec le temps écoulé, ou restant à écouler… Connaître le temps qu’un programme met à s’exécuter, ce n’est pourtant pas beaucoup demander ! En fait, si. Et en gros, à la louche, à peu près, en moyenne ? Même. Et même en faisant abstraction des performances des matériels utilisés, connaître le temps d’exécution d’un algorithme est un problème difficile – souvent insoluble en l’état actuel des connaissances. Bien souvent, on donne la complexité dans le pire des cas d’un algorithme, c’est-à-dire le temps de calcul théorique d’un algorithme sur la pire entrée possible, celle qui lui prendra le plus de temps à s’exécuter. On s’intéresse aussi beaucoup au temps de calcul en moyenne sur toutes les entrées possibles, qui est encore plus difficile à calculer. Et puis, pour résoudre un problème, il existe typiquement plusieurs algorithmes. Alors, savoir combien il faudrait de temps pour résoudre un problème particulier, c’est encore plus compliqué.
Parmi les algorithmes les plus étudiés, on trouve les algorithmes de tri, qui partent d’une suite d’objets non triés et s’occupent de la ranger dans un ordre bien défini. Il en existe de nombreux, aux noms poétiques : tri à bulles, tri par insertion, tri rapide… C’est une des rares familles d’algorithmes dont on connaît bien le temps théorique d’exécution, que ce soit dans le pire des cas ou en moyenne. Le tri par sélection, par exemple, fonctionne de manière très simple : on cherche la plus petite valeur à trier et on la met devant. Puis on cherche la deuxième plus petite dans ce qui reste, et on la met en deuxième, etc. Simple, mais pas terrible en complexité ! Pour n valeurs à trier, il faut lire une fois toutes les données pour trouver la plus petite valeur, ce qui coûte n opérations, pour la seconde, n-1, etc. Au total, on a de l’ordre de n2 opérations à faire dans le pire des cas comme en moyenne.
Le tri rapide, ou quicksort, est plus compliqué à comprendre mais plus efficace : on choisit arbitrairement une valeur dans les données à trier, et on met d’un côté toutes les valeurs plus petites, de l’autre toutes les plus grandes. Ça semble farfelu, c’est pourtant très astucieux : on se retrouve avec deux suites de données beaucoup plus petites à trier! Et on reprend sur ces deux suites. La complexité passe à n*log(n), ce qui représente un gain significatif en temps de calcul.
En général, on connaît la complexité dans le pire des cas de beaucoup d’algorithmes courants, beaucoup plus rarement la complexité en moyenne. Il reste beaucoup à apprendre.
Laisser un commentaire