Expositions de ce domaine
Les grandes questions de ce domaine
Qu’est-ce qu’un algorithme ?
Un algorithme est une liste d’étapes précises qui résout un problème, rédigée si clairement qu’une machine peut la suivre sans la comprendre. Une recette s’en approche ; la façon de chercher un mot dans le dictionnaire aussi. Les programmes sont des algorithmes écrits dans un langage qu’un ordinateur peut exécuter.
Pourquoi certains algorithmes sont-ils plus rapides que d’autres ?
Parce qu’ils font moins de travail quand l’entrée grandit. Pour trier mille éléments, une méthode simple comme le tri à bulles fait environ un demi-million de comparaisons, alors que le tri fusion en demande une dizaine de milliers. La notation Big-O, comme O(n²) et O(n log n), décrit la façon dont le travail augmente, pas le temps sur un ordinateur donné.
Comment un ordinateur trie-t-il une liste ?
En comparant les éléments deux par deux et en les déplaçant, encore et encore, selon un plan fixe. Des plans différents donnent des algorithmes de tri différents : certains échangent des voisins, d’autres coupent la liste en deux et refusionnent les moitiés dans l’ordre, d’autres choisissent un pivot et séparent les petits éléments des grands.