926 - Analyse des algorithmes : complexité. Exemples.2021

Rapport du jury 2019

Il s’agit ici d’une leçon d’exemples. Le candidat doit prendre soin de proposer l’analyse d’algorithmes portant sur des domaines variés, avec des méthodes d’analyse également variées : approche combinatoire ou probabiliste, analyse en moyenne ou dans le pire cas. $\\$ Si la complexité en temps est centrale dans la leçon, la complexité en espace ne doit pas être négligée. La notion de complexité amortie a également toute sa place dans cette leçon, sur un exemple bien choisi, comme union find (ce n’est qu’un exemple).