Analyse de tri rapide randomisé

Cette séance de cours couvre l'analyse du tri rapide (randomisé), en se concentrant sur le temps de fonctionnement et le nombre de comparaisons. L'instructeur explique le concept de variables aléatoires et le nombre total prévu de comparaisons. La séance de cours traite également de la limite sur le nombre total de comparaisons et l'application de la linéarité de l'attente. En outre, il présente un résumé de tri rapide, prouvant que son temps de fonctionnement attendu est O (nlogn) pour toute entrée. Les limites inférieures pour le tri et les arbres de décision dans le contexte du tri de comparaison sont également explorées, mettant en évidence l'optimalité de la fusion-tri, du tas tri et du tri rapide.