Quelle est la probabilité de comparaison entre le plus petit et le plus grand élément du tableau lorsque vous choisissez rapidement l'élément pivot au hasard?

Question

Considérez le récursif quick sort avec random pivoting c'est-à-dire que chaque fois qu'un élément de pivot aléatoire est choisi uniformément. Lorsque cet algorithme randomisé est appliqué à un tableau avec n élément distinct, quel est le probability que le smallest et le greatest L'élément sera compared Pendant la course de l'algorithme.