Salut, habrozhiteli! Ce livre est basé sur les cours d'algorithmique en ligne que Tim Rafgarden dirige sur Coursera et Stanford Lagunita, et ces cours ont vu le jour grâce aux conférences qu'il donne aux étudiants de l'Université de Stanford depuis de nombreuses années.
Les algorithmes sont le cœur et l'âme de l'informatique. Vous ne pouvez pas vous en passer, ils sont partout - du routage réseau et des calculs génomiques à la cryptographie et à l'apprentissage automatique. «L'algorithme parfait» fera de vous un véritable pro qui définira les tâches et les résoudra magistralement à la fois dans la vie et lors d'un entretien lors de l'embauche d'une entreprise informatique. Tim Rafgarden parlera de l'analyse asymptotique, de la notation big-O, des algorithmes de division et de conquête, de la randomisation, du tri et de la sélection. Le livre s'adresse à ceux qui ont déjà une expérience en programmation. Vous passerez à un nouveau niveau pour voir la grande image, pour comprendre les concepts de bas niveau et les nuances mathématiques.
* 6.3. Algorithme DSelect
L'algorithme RSelect est exécuté en temps linéaire pour chaque entrée, dans lequel l'attente mathématique est associée à des choix aléatoires effectués par l'algorithme. La randomisation est-elle requise pour la sélection linéaire? Dans cette section et plus loin, ce problème est résolu en utilisant un algorithme linéaire déterministe pour le problème de choix.
Pour la tâche de tri, le temps d'exécution moyen de l'algorithme QuickSort randomisé O (n log n) est le même que l'algorithme déterministe MergeSort, et les deux algorithmes QuickSort et MergeSort sont des algorithmes utiles pour une utilisation pratique. D'un autre côté, bien que l'algorithme de sélection linéaire déterministe décrit dans cette section fonctionne bien en pratique, il n'est pas en concurrence avec l'algorithme RSelect. Cela se produit pour deux raisons: en raison des facteurs constants importants dans le temps de fonctionnement de l'algorithme DSelect et du travail effectué par l'algorithme associé à l'allocation et à la gestion de RAM supplémentaire. Néanmoins, les idées de l'algorithme sont si cool que je ne peux pas m'empêcher de vous en parler.
6.3.1. Idée brillante: médiane des médianes
L'algorithme RSelect est rapide, car il y a une forte probabilité que les éléments de support aléatoires soient assez bons, fournissant une répartition approximativement équilibrée du tableau d'entrée après la séparation, de plus, de très bons éléments de support progressent rapidement. Si nous ne sommes pas autorisés à utiliser la randomisation, alors comment calculer un assez bon élément de référence sans faire trop de travail?
L'idée ingénieuse d'un choix linéaire déterministe est d'utiliser la «médiane des médianes» comme indicateur de la vraie médiane. L'algorithme considère les éléments du tableau d'entrée comme des équipes sportives et organise un tournoi à élimination directe en deux tours, dont le champion est l'élément de soutien; voir aussi fig. 6.1.
Le premier tour est une phase de groupe avec des éléments aux positions 1 à 5 du tableau d'entrée comme premier groupe, des éléments aux positions 6 à 10 comme deuxième groupe, etc. Le vainqueur du premier tour d'un groupe de cinq éléments est défini comme la médiane de l'élément (c'est-à-dire le troisième plus petit). Puisqu'il y a
groupes de cinq éléments, il existe
premiers gagnants. (Comme d'habitude, nous ignorons les fractions pour plus de simplicité.) Un champion de tournoi est défini comme la médiane des gagnants du premier tour.
6.3.2. Pseudocode pour l'algorithme DSelect
Comment calculer réellement la médiane des médianes? La mise en œuvre de la première étape du tournoi à élimination est simple, car chaque calcul de la médiane ne comprend que cinq éléments. Par exemple, chacun de ces calculs peut être effectué par force brute (pour chacune des cinq possibilités, vérifiez en détail s'il s'agit d'un élément intermédiaire) ou en utilisant nos informations sur le problème de tri (section 6.1.2). Pour mettre en œuvre la deuxième étape, nous calculons la médiane de
vainqueurs du premier tour récursivement.
Les lignes 1–2 et 6–13 sont identiques à l'algorithme RSelect. Les lignes 3 à 5 sont la seule nouvelle partie de l'algorithme; ils calculent la médiane de la médiane du tableau d'entrée, en remplaçant la ligne dans l'algorithme RSelect, qui sélectionne l'élément de référence au hasard.
Les lignes 3 et 4 calculent les gagnants du premier tour du tournoi à élimination, où l'élément central de chaque groupe de cinq éléments est calculé en utilisant la méthode de la force brute ou l'algorithme de tri, et copiez ces gagnants dans le nouveau tableau C.La ligne 5 calcule le champion du tournoi en calculant récursivement la médiane du tableau C; puisque C a une longueur (provisoirement)
-th statistiques ordinales du tableau C. Aucune randomisation n'est utilisée à aucune étape de l'algorithme.
6.3.3. Comprendre l'algorithme DSelect
Un appel récursif à l'algorithme DSelect lors du calcul d'un élément de référence peut sembler dangereusement cyclique. Pour comprendre ce qui se passe, désignons d'abord le nombre total d'appels récursifs.
La bonne réponse est: (c). En ignorant le cas de base et le cas heureux dans lequel l'élément de référence est les statistiques de commande requises, l'algorithme DSelect effectue deux appels récursifs. Pour comprendre pourquoi, n'en abusez pas; il suffit de vérifier le pseudo-code de l'algorithme DSelect ligne par ligne. La ligne 5 a un appel récursif et un autre sur la ligne 11 ou 13.
Il y a deux questions communes déroutantes sur ces deux appels récursifs. Premièrement, n'est-ce pas un fait que l'algorithme RSelect ne fait qu'un seul appel récursif, la raison pour laquelle il fonctionne plus vite que nos algorithmes de tri? DSelect n'abandonne-t-il pas cette amélioration en effectuant deux appels récursifs? La section 6.4 montre que puisque l'appel extra récursif sur la ligne 5 ne devrait résoudre qu'une sous-tâche relativement petite (avec 20% des éléments dans le tableau d'origine), nous pouvons toujours enregistrer l'analyse linéaire.
Deuxièmement, deux appels récursifs jouent des rôles fondamentalement différents. Le but de l'appel récursif sur la ligne 5 est de déterminer un bon élément de référence pour l'appel récursif en cours. L'objectif de l'appel récursif sur la ligne 11 ou 13 est celui habituel - résoudre récursivement la tâche restante plus petite laissée par l'appel récursif en cours. Néanmoins, la structure récursive de l'algorithme DSelect suit pleinement la tradition de tous les autres algorithmes de division et de conquête que nous avons étudiés: chaque appel récursif effectue un petit nombre d'appels récursifs ultérieurs avec des sous-tâches strictement plus fines et fait un travail supplémentaire. Si nous ne craignions pas que des algorithmes tels que MergeSort ou QuickSort s'exécutent pour toujours, nous ne devrions pas nous inquiéter de l'algorithme DSelect.
6.3.4. Exécution de l'algorithme DSelect
L'algorithme DSelect n'est pas seulement un programme bien défini qui se termine en un temps limité - il s'exécute en temps linéaire, ne faisant plus de travail que sur un facteur constant que nécessaire pour lire les données d'entrée.
Théorème 6.6 (durée de fonctionnement de l'algorithme DSelect). Pour chaque tableau d'entrée de longueur n ≥ 1, le temps d'exécution de l'algorithme DSelect est O (n).
Contrairement au temps d'exécution de l'algorithme RSelect, qui ne peut en principe pas dépasser Θ (n2), le temps d'exécution de l'algorithme DSelect est toujours égal à O (n). Néanmoins, dans la pratique, vous devriez préférer RSelect à l'algorithme DSelect, car le premier fonctionne au même endroit, et la constante cachée dans le temps de fonctionnement moyen «O (n)» dans Theorem 6.1 est plus petite que la constante cachée dans Theorem 6.6.
»Plus d'informations sur le livre sont disponibles sur
le site Web de l'éditeur»
Contenu»
ExtraitPour Khabrozhiteley 20% de réduction sur le coupon -
AlgorithmesLors du paiement de la version papier du livre, une version électronique du livre est envoyée par e-mail.
PS: 7% du coût du livre ira à la traduction de nouveaux livres informatiques, la liste des livres remis à l'imprimerie est
ici .