Complexité moyenne du tri rapide
On établit la complexité $O(n\log(n))$ du tri rapide _déterministe_.
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 926 | Analyse des algorithmes : complexité. Exemples.2021 |
| 5 | 8 | Algorithmes de tri. Exemples, complexité et applications.2022 |
Utilisateur : Devevey
L'algorithme présenté dans le Beauquier n'est pas le tri rapide de base, c'est pour ça qu'on se base sur celui présenté dans le Cormen et qu'on adapte la preuve du Beauquier pour calculer la complexité en moyenne du tri rapide.
Références :
Eléments d'algorithmique - Beauquier, Berstel et Chrétienne
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Utilisateur : Meven
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érences :
Eléments d'algorithmique - Beauquier, Berstel et Chrétienne