temps d'exécution prévu pour le tri sélectif et le tri par insertion hybride

Question

Je suis en train d'apprendre en autodidacte la 3e édition du CLRS et voici l'une des questions les plus difficiles que j'ai rencontrées. ainsi que sa réponse au service de tous.

7.4-5 Nous pouvons améliorer le temps d'exécution du tri sélectif dans la pratique en tirant parti de l'option du temps d'exécution rapide du tri par insertion lorsque son entrée est "presque" triée. Lors de l'appel de quicksort sur un sous-réseau contenant moins de k qu'il renvoie simplement sans trier le sous-réseau. Après le retour de l'appel de niveau supérieur au tri sélectif, exécutez le tri par insertion sur l'ensemble du tableau pour terminer le processus de tri. Argumentez que cet algorithme de tri s'exécute en O(nk+nlg(n/k)) délai prévu. Comment choisir k tant en théorie qu'en pratique et en pratique ?

Answer 1

Si vous évaluez l'équation nlgn > nk + nlog(n/k) vous obtenez log k > k . Ce qui est impossible. En théorie, ce n'est donc pas possible. Mais en pratique, des facteurs constants interviennent dans le tri par insertion et le tri sélectif. Jetez un coup d'œil à la solution discutée dans ce pdf . Vous pouvez mettre à jour votre réponse. .

Answer 2

En fait, la réponse est k = 8 .

L'algorithme obtenu est la composition de deux fonctions anonymes, dont l'une est O(nk) et l'autre qui est O(n lg n/k) . Ces fonctions anonymes cachent les constantes du cas moyen. Le tri par insertion s'exécute en n^2/4 dans le cas moyen et le tri sélectif aléatoire fonctionne en 1.386 n lg n dans le cas moyen. Nous voulons trouver une valeur de k qui minimise la valeur de nk/4 + 1.386( n lg n/k ) ce qui équivaut à nk/4 + 1.386 n lg n - 1.386 n lg k . Il s'agit de trouver le maximum de la fonction 1.386 lg k - k/4 . Cette valeur maximale est atteinte à k = 8 .

Answer 3

Une feuille a une probabilité égale d'avoir une taille comprise entre 1 a k .
La taille attendue d'une feuille est donc k/2 .
Si la taille attendue d'une feuille est k/2 nous nous attendons alors à ce que n/(k/2)=(2n)/k de telles feuilles.
Pour simplifier, disons que nous attendons n/k de telles feuilles et que la taille attendue de chaque feuille est de k .
La durée d'exécution prévue de INSERTION-SORT est O(n^2) .
C'est ce que nous avons constaté dans l'exercice 5.2-5 et le problème 2-4c.
Ainsi, la durée d'exécution prévue de INSERTION-SORT L'utilisation est O((n/k)*(k^2))=O(nk) .
Si nous nous attendons à ce que nos groupes de partition soient de taille k alors la hauteur de l'arbre de récurrence devrait être de lgn-lgk=lg(n/k) puisque nous prévoyons d'arrêter lgk plus tôt.
Il y a O(n) à chaque niveau de l'arbre de récurrence.
Cela nous amène à O(nlg(n/k)) .
Nous concluons que le temps d'exécution attendu est de O(nk+nlg(n/k)) .

En théorie, nous devrions choisir k=lgn car nous obtenons ainsi la meilleure durée d'exécution attendue de O(nlgn) .

En pratique, nous devrions choisir k à l'une des valeurs autour de lgn qui nous permet d'obtenir de meilleures performances qu'en exécutant simplement RANDOMIZED-QUICKSORT .

La deuxième partie de la réponse utilise la notation big-O de manière assez vague, de sorte que pour un choix plus précis de k Veuillez suivre le lien indiqué dans la deuxième réponse d'Ankush.