SebRmv (./8) :
3-l'exemple archi-classique d'algo où l'on fait une étude de la complexité en moyenne est le tri rapide (quick sort)
la complexité en comparaisons dans le pire cas est O(n^2) alors qu'elle est O(n log(n)) en moyenne

Y a-t-il un seul autre algo dont on étudie la complexité en moyenne ?

Bon, j'exagère un peu, mais c'est vrai que je n'ai aucun souvenir d'une étude en moyenne pour autre chose...