Complexité des algorithmes
Progression
#Complexité des algorithmes : temps et espace
Nous commençons par rappeler les notations O, Ω et Θ, non pas comme un rituel mathématique mais comme un langage pour discuter de performance. Le modèle RAM sert de cadre : chaque opération arithmétique ou accès mémoire est supposé constant. À partir de cette base, nous explorons la complexité amortie avec l’exemple des tableaux dynamiques qui se redimensionnent, puis les analyses probabilistes qui s’opposent au pire cas.
Les études de cas mettent en scène des algorithmes que tout le monde croit connaître. Tri fusion et tri insertion sont comparés sur des jeux de données variés, illustrant que le second n’est pas obsolète lorsqu’on s’intéresse à de petits tableaux presque triés. Nous opposons recherche binaire et linéaire selon la structure disponible, et nous analysons une file de priorité pour comprendre pourquoi push et pop sont en O(log n).
#Exercices
- Démontrez l’amorti
O(1)d’une table de hachage par doublement. - Comparez l’impact mémoire d’un BFS vs DFS sur un graphe densité variable.