Aujourd'hui, nous avons rappelé le concept de complexité (temporelle) qui évalue le temps que prendra un algorithme à s’exécuter sur une entrée de taille n en comptabilisant le nombre d'opérations nécessaire puis en classifiant le résultat (O(1), O, O(n2)).
On a également rappelé les algorithmes de recherche d'une valeur dans une liste et de recherche de maximum dans une liste qu'on avait déjà vus la semaine passée et pourquoi ils ont une complexité O.
Ensuite, on a corrigé le Quiz intro à la complexité que vous aviez à faire pour aujourd'hui.
Si vous n'avez pas tout compris, cette vidéo corrige le Quiz en détail.
Finalement, on a introduit les algorithmes de tri. Ceci nous a permis de constater que des opérations très complexes comme faire du vélo ou trier des cartes à jouer sont réalisées par notre cerveau sans qu'on y prête attention. Par contre, quand on doit décortiquer et expliquer en détail comment on fait, on a beaucoup de mal. C'est justement en cela que consiste un algorithme. On se remet dans la peau d'un enfant qui apprend une nouvelle opération et on la détaille pas à pas.
Pour le tri, on s'est dit qu'il fallait donc éviter de dire: "On met le 1 tout à gauche." ou "Le minimum, c'est 1" ou "Ça se voit..." car ce ne sont pas des opérations "atomiques". On s'est fixé comme but de décrire les tris avec des opérations basiques comme:comparer deux cartes et échanger deux cartes
Du coup, on a essayé de trouver comment trier et je vous ai montré l'un des 5 algorithmes que nous allons voir: Le tri par insertion.
C'est cet algorithme qui est traité dans la vidéo sur la complexité du Quiz en devoir.
DEVOIRS:
- Faire le Quiz sur la complexité du tri par insertion
Bonne semaine!
JCB