Mesures de complexités

Cette partie s'intéresse à la notion de complexités pour un algorithme qui permet de mesurer ses performances.

Complexité d'un algorithme

Cette partie s'intéresse à la notion de complexité d'un algorithme et donne les moyens de la calculer.

Utilisation pour calculer théoriquement et en pratique la complexité d'algorithmes :

On s'entraîne

Projet

TBD pour aller plus loin timeit et pypertf. TBD code voir qu'il y a une légère variation à chaque appel même avec les même données. DOnc faire une moyenne. pyperf

Calculs

TBD exo recherche : min/max/moyenne. Un autre ou moyenne proche du min Maintenant que l'on peut calculer les complexités, on peut reprendre les algorithmes itératifs et récursifs que nous avons crées précédemment :

TBD k-moyenne de la partie non corrigée. Elle mérite d'être corrigée TBD ne garder que les exos qui font sens. Et de difficulté croissante.

On vérifie qu'on sait faire :

TBD : une fois qu'on a un algorithme qui fait ce qu'on veut on essaie de le faire le plus vite possible (en moins d'instruction possible) TBD égalité de mots binaires. max O(n) en moyenne O(2)