Complexité moyenne d'un algorithme de tri rapide

[Matt1627]

Bonjour, pour l'algorithme de tri rapide suivant, je comprends sa complexité dans le meilleur des cas qui est en O(n) et celle dans le pire des cas qui est en O(n²). Cependant, je ne comprends pas pourquoi sa complexité moyenne est en O(n*log(n)). D'où sort le log(n) ? On ne peut pas faire la moyenne entre la complexité dans le pire des cas et celle dans le meilleur des cas pour trouver la complexité moyenne ?

def tri_rapide(Liste):
     if not Liste:
         return []
     else:
         pivot=Liste[-1]
         Liste_inf=[k for k in Liste if k<pivot]
         Liste_sup=[k for k in Liste[:-1] if k>=pivot]
         return tri_rapide(Liste_inf) + [pivot] + tri_rapide(Liste_sup)

Merci d'avance à toute personne m'accordant un peu de son temps.
-----

[pm42]

Tu as lu l'explication ici https://fr.wikipedia.org/wiki/Tri_ra..._et_complexité ?

Et non, on ne peut pas faire la moyenne entre le meilleur et le pire des cas. Pourquoi ça marcherait ?
C'est (toutes proportions gardées) comme si tu disais : si je joue au loto, je peux perdre le prix du ticket ou gagner 10 millions. Donc mon espérance de gain est la moyenne de cas le plus favorable et le plus défavorable.

L'article de Wikipedia explique d'ailleurs pourquoi l'écart-type au delà de la complexité moyenne est faible et que donc les cas les plus défavorables sont rares.

[Matt1627]

Excusez-moi pour ma tardive réponse. Merci beaucoup en tout cas.