Comment comprendre l'analyse du temps de fonctionnement attendu du sort rapide randomisé dans cet article?

Question

J'apprends le livre nommé Data Structures & Algorithms in Python.

À la page 557-558, il y a une preuve du temps de fonctionnement attendu de qucick-sort randomisé. J'ai des problèmes qui me déroutaient certains jours. Je les noterai sous une forme audacieuse.

Voici un texte original:

Proposition 12.3: Le temps d'exécution attendu du sort rapide randomisé sur une séquence $ s $ de taille $ n $ est $ o (n log n) $.

Justification: Nous supposons que deux éléments de $ s $ peuvent être comparés en $ o (1) $. Considérez un seul appel récursif de sort rapide randomisé et laissez $ n $ indiquer la taille de l'entrée pour cet appel. Dites que cet appel est «bon» si le pivot choisi est tel que les sous-séquences $ l $ et $ g $ ont une taille au moins $ frac {n} {4} $ et au plus $ frac {3n} {4} $ chaque; Sinon, un appel est «mauvais».

Maintenant, considérons les implications de notre choix d'un pivot uniformément au hasard. Notez qu'il y a $ frac {n} {2} $ de bons choix possibles pour le pivot pour tout appel donné de la taille n de l'algorithme de sort rapide randomisé. Ainsi, la probabilité que tout appel soit bon est $ frac {1} {2} $. Notez en outre qu'un bon appel va au moins partitionner une liste de taille $ n $ en deux listes de taille $ frac {3n} {4} $ et $ frac {n} {4} $, et un mauvais appel pourrait être Aussi mauvais que de produire un seul appel de taille $ n - 1 $.

Considérez maintenant une trace de récursivité pour le sort rapide randomisé. Cette trace définit un arbre binaire, $ t $, de sorte que chaque nœud dans $ t $ correspond à un appel récursif différent sur un sous-problème de tri une partie de la liste originale.

Dire qu'un nœud $ v $ en $ t $ est en groupe de taille $ i $ Si la taille du sous-problème de $ v $ est supérieure à $ Left ( frac {3} {4} droite) ^ {i + 1} n $ et au plus $ Left ( frac {3 } {4} à droite) ^ Dans $, analysons le temps attendu passé à travailler sur tous les sous-problèmes pour les nœuds du groupe de taille $ i $. Par la linéarité des attentes (proposition A.19), le temps prévu pour travailler sur tous ces sous-problèmes est la somme des temps attendus pour chacun. Certains de ces nœuds correspondent à de bons appels et certains correspondent à de mauvais appels. Mais notez que, comme un bon appel se produit avec probabilité $ frac {1} {2} $, le nombre attendu d'appels consécutifs que nous devons passer avant d'obtenir un bon appel est de $ $.

---

⓵ De plus, notez que dès que nous avons un bon appel à un nœud en groupe de taille $ i $, ses enfants seront en groupes de taille supérieurs à $ i $.

⓶ Ainsi, pour tout élément $ x $ de la liste des entrées, le nombre attendu de nœuds en groupe de taille $ i $ contenant $ x $ dans leurs sous-problèmes est de 2 $. En d'autres termes, la taille totale attendue de tous les sous-problèmes du groupe de taille $ i $ est de 2 $ $.

---

Étant donné que le travail non réénuitif que nous effectuons pour tout sous-problème est proportionnel à sa taille, cela implique que le temps total attendu de traitement des sous-problèmes pour les nœuds en groupe $ i $ est $ o (n) $.

Le nombre de groupes de taille est $ log _ { frac {4} {3}} n $, puisque la multiplication à plusieurs reprises par $ frac {3} {4} $ est la même que la division à plusieurs reprises par $ frac {4} { 3} $. C'est-à-dire que le nombre de groupes de taille est $ o ( log n) $. Par conséquent, le temps d'exécution attendu total du sort rapide randomisé est $ o (n log n) $. (Voir figure 11.13.)

Voici mes problèmes:

1. Selon cette phrase:

   ⓵ De plus, notez que dès que nous avons un bon appel à un nœud en groupe de taille $ i $, ses enfants seront en groupes de taille supérieurs à $ i $.

À quelle taille le nœud $ s (a) $ appartient-il? Et pourquoi?

2. ⓶ Ainsi, pour tout élément $ x $ de la liste des entrées, le nombre attendu de nœuds en groupe de taille $ i $ contenant $ x $ dans leurs sous-problèmes est de 2 $. En d'autres termes, la taille totale attendue de tous les sous-problèmes du groupe de taille $ i $ est de 2 $ $.

Je ne peux pas vraiment comprendre le sens de cette phrase.