Pourquoi Quicksort aléatoire a-t-il le coût d'exécution O (n log n) dans le pire des cas

Le tri rapide aléatoire est une extension du tri rapide dans lequel l'élément pivot est choisi au hasard. Quelle peut être la pire complexité temporelle de cet algorithme. Selon moi, ce devrait être , car le pire des cas se produit lorsque le pivot choisi au hasard est sélectionné dans l' ordre trié ou inversé . Mais dans certains textes [1] [2] sa pire complexité temporelle est écrite comme$O(n^2)$O ( n log n )$O(n\log{n})$

Qu'est-ce qui est correct?

Vos deux sources font référence au "temps d'exécution prévu le plus défavorable" deJe suppose que cela fait référence à l'exigence de temps prévue, qui diffère du pire des cas.$O(n \log n).$

Quicksort a généralement une exigence de temps absolue dans le pire des cas de . Le pire des cas se produit lorsque, à chaque étape, la procédure de partition divise un tableau de longueurs en tableaux de taille et . Cette sélection "malchanceuse" des éléments pivot nécessite des appels récursifs O ( n ) , conduisant à un pire cas O ( n 2 ) .$O(n^2)$$n$ n - $1$$n-1$$O(n)$$O(n^2)$

Le choix du pivot de manière aléatoire ou aléatoire dans le tableau avant le tri a pour effet de rendre le pire des cas très improbable, en particulier pour les grands tableaux. Voir Wikipedia pour une preuve que l' exigence de temps attendue est . Selon uneautre source, "la probabilité que le tri rapide utilise un nombre quadratique de comparaisons lors du tri d'un grand tableau sur votre ordinateur est bien inférieure à la probabilité que votre ordinateur soit frappé par la foudre".$O(n\log n)$

Éditer:

Selon le commentaire de Bangye, vous pouvez éliminer la pire séquence de sélection de pivot en sélectionnant toujours l'élément médian comme pivot. Étant donné que la recherche de la médiane prend du temps , cela donne les performances dans le pire des cas Θ ( n log n ) . Cependant, étant donné qu'il est très peu probable que le tri rapide randomisé tombe sur le pire des cas, la variante déterministe médiane du tri rapide est rarement utilisée.$O(n)$$\Theta(n \log n)$

Il vous manquait que ces textes parlent de " temps d'exécution prévu dans le pire des cas ", pas de "temps d'exécution dans le pire des cas".

Ils discutent d'une implémentation Quicksort qui implique un élément aléatoire. Normalement, vous avez un algorithme déterministe, c'est-à-dire un algorithme qui, pour une entrée donnée, produira toujours exactement les mêmes étapes. Pour déterminer le «pire cas d'exécution», vous examinez toutes les entrées possibles et choisissez celle qui produit le pire temps d'exécution.

Mais ici, nous avons un facteur aléatoire. Compte tenu de certaines entrées, l'algorithme ne fera pas toujours les mêmes étapes car un caractère aléatoire est impliqué. Au lieu d'avoir un temps d'exécution pour chaque entrée fixe, nous avons un "temps d'exécution prévu" - nous vérifions chaque valeur possible des décisions aléatoires et leur probabilité, et le "temps d'exécution prévu" est la moyenne pondérée du temps d'exécution pour chaque combinaison de décisions aléatoires , mais toujours pour une entrée fixe.

Nous calculons donc le «temps d'exécution attendu» pour chaque entrée possible, et pour obtenir le «temps d'exécution attendu dans le pire des cas», nous trouvons la seule entrée possible où le temps d'exécution attendu est le plus mauvais. Et apparemment, ils ont montré que le pire des cas pour le "runtime attendu" est juste O (n log n). Je ne serais pas surpris si le simple fait de choisir le premier pivot au hasard changerait le pire cas d'exécution attendu en o (n ^ 2) (petit o au lieu de Big O), car seuls quelques-uns des n pivots conduiront au pire des cas comportement.

Notez qu'il y a deux choses à prendre en compte: la permutation d'entrée et les pivots (un par partitionnement).

$n$$\Theta(n \log n)$

$\Theta(n \log n)$ , à savoir celles qui choisissent la médiane exacte comme pivot et traitent les doublons de manière agréable.

En bout de ligne, vérifiez vos sources pour quelle implémentation ils utilisent et quelle quantité ils considèrent comme aléatoire resp. fixé dans leur analyse.

$O(n^2)$

Le pire des cas pour le tri rapide aléatoire est constitué des mêmes éléments que l'entrée. Ex: 2,2,2,2,2,2

$T(n) = T(n-1) + n$$O(n^2)$