Essayer de comprendre le 2N lnN compare pour quicksort

Je passais par l'analyse de quicksort dans le livre des algorithmes de Sedgewick. Il crée la relation de récurrence suivante pour le nombre de comparaisons dans le tri rapide tout en triant un tableau de N éléments distincts.

J'ai du mal à comprendre cela ... Je sais qu'il faut une probabilité de 1 / N pour qu'un élément devienne le pivot et que si k devient le pivot, alors le sous-tableau de gauche aura k-1 éléments et le sous-droit tableau aura Nk éléments.

1.Comment le coût du partitionnement devient-il N + 1? Faut-il N + 1 compare pour faire le partitionnement?

2.Sedgewick dit, pour chaque valeur de k, si vous les additionnez, la probabilité que l'élément de partitionnement soit k + le coût pour les deux sous-tableaux vous donne l'équation ci-dessus.

• Quelqu'un peut-il expliquer cela pour que ceux qui ont moins de connaissances en mathématiques (moi) puissent comprendre?
• Plus précisément, comment obtenez-vous le deuxième terme de l'équation?
• Que signifie exactement ce terme?

La fonction de coût Cpour quicksort se compose de deux parties. La première partie est le coût de partitionnement du tableau en deux «moitiés» (les moitiés n'ont pas à être de taille égale, d'où les guillemets). La deuxième partie est le coût du tri de ces deux moitiés.

1. Le (N + 1)terme est en fait un terme condensé, et vient des termes

   (N - 1) + 2
   

   Il s'agit du coût du partitionnement dans le tri rapide: se N-1compare à la valeur pivot, et 2 autres comparaisons en raison de certaines conditions aux limites dans le partitionnement.

2. La deuxième partie de l'équation comprend les coûts de tri des deux «moitiés» de chaque côté de la valeur pivot k.

   Après avoir choisi une valeur de pivot, vous vous retrouvez avec deux «moitiés» non triées. Le coût du tri de ces «moitiés» dépend de leur taille et est plus facilement décrit comme une application récursive de la fonction de coût C. Si le pivot est la plus petite des Nvaleurs, les coûts de tri de chacune des deux «moitiés» sont respectivement C(0)et C(N-1)(le coût de tri d'un tableau avec 0 éléments et le coût de tri d'un tableau avec des N-1éléments). Si le pivot est le cinquième plus petit, alors le coût de tri de chacune des deux «moitiés» est respectivement C(5)et C(N-6)(le coût de tri d'un tableau à 5 éléments et le coût de tri d'un à N-6éléments). Et de même pour toutes les autres valeurs de pivot.

   Mais combien cela coûte-t-il de trier ces deux «moitiés» si vous ne connaissez pas la valeur du pivot? Cela se fait en prenant le coût de chaque valeur possible du pivot et en le multipliant par la chance que cette valeur particulière apparaisse.

   Comme chaque valeur de pivot est également probable, la chance de choisir une valeur de pivot particulière est 1/Nsi vous avez des Néléments. Pour comprendre cela, pensez à lancer un dé. Avec un dé approprié, la chance pour chaque camp de se retrouver face vers le haut est égale, donc la chance de lancer un 1 est de 1/6.

   Combiné, cela donne le terme de sommation où, pour chaque valeur possible k du pivot, le coût ( C(k-1) + C(N-k)) est multiplié par la chance ( 1/N)

3. La dérivation supplémentaire de la formule de sommation dans la question au 2N lnNtitre prend trop de mathématiques pour expliquer les détails ici, mais elle est basée sur la compréhension que le coût du tri d'un tableau d' Néléments ( C(N)) peut être exprimé en termes de tri d'un tableau d' N-1éléments ( C(N-1)) et un facteur directement proportionnel à N.

1. Il semble que N + 1 comme nombre de comparaisons pour l'étape de partition soit une erreur dans le livre. Vous devez déterminer pour chacun des N-1 éléments non-pivot s'il est inférieur ou supérieur au pivot, ce qui prend une comparaison; donc N – 1 comparaisons au total, pas N + 1. (Considérons le cas le plus simple, N = 2, c'est-à-dire un pivot et un autre élément: il n'y a absolument aucune place pour faire trois comparaisons entre deux éléments.)

2. Considérons le cas où le pivot choisi se trouve être le plus petit élément (k = 1). Cela signifie que le tableau est divisé en une partie vide à gauche (il n'y a aucun élément inférieur au pivot) et une partie à droite qui contient tous les éléments à l'exception du pivot (tous les autres éléments sont supérieurs au pivot ). Cela signifie que les sous-problèmes que vous souhaitez maintenant résoudre de manière récursive ont respectivement des tailles 0 et N – 1 (k – 1 et N – k) et nécessitent des comparaisons C (0) et C (N – 1); ainsi, C (0) + C (N – 1) au total.

   Si le pivot se trouve être le deuxième plus petit élément (k = 2), les tailles des sous-problèmes sont 1 et N – 2 (k – 1 et N – k; un élément à gauche, car il est le seul plus petit que le pivot). Ainsi, la résolution récursive de ces sous-problèmes nécessite des comparaisons C (1) + C (N – 2). Et ainsi de suite si le pivot est le troisième plus petit élément, le quatrième, etc. Ce sont les expressions dans les numérateurs.

   Parce que le pivot est choisi au hasard parmi les N éléments, chaque cas (pivot est le plus petit, pivot est le deuxième plus petit, etc.) se produit avec une probabilité égale 1 / N. C'est de là que vient le N dans les dénominateurs.