Développement : Complexité moyenne du tri rapide

Détails/Enoncé :

On établit la complexité $O(n\log(n))$ du tri rapide _déterministe_.

Versions :

  • Auteur :
  • Remarque :
    L'étude est un peu subtile, et le lemme important et qu'en partant de permutations équiprobables, on arrive après la phase de division du tableau à des permutations des tableaux restant à trier qui sont encore équiprobables, ce qui est rarement bien fait dans les livres d'algorithmique…
  • Référence :