Probabilité que deux éléments soient comparés dans des arbres randomisés

Question

J'ai un problème dans une partie spécifique de l'analyse de tri rapide randomisée.

Selon l'algorithme de tri rapide randomisé, le pivot est choisi parmi le sous-ensemble donné sur lequel il est appelé à partir d'un index aléatoire, au lieu de choisir simplement un index spécifique à chaque fois.

Supposons maintenant que nous donnons un éventail de taille dire $ n $ à notre algorithme QuicksTort randomisé.

Maintenant, je demande d'examiner la preuve de Lemma-7.1 dans le texte indiqué ci-dessous. Maintenant, nous avons donné un tableau à notre algorithme qui peut être de toute permutation des éléments, mais dans le paragraphe après la preuve de $ lemma-7.1 $ .

Pourquoi l'auteur compte-t-il une instance triée de notre tableau d'informations tout en faisant l'analyse?

En outre, si vous regardez le texte après l'équation $ (7.2) $ où il y a justifié leur logique de trouver la probabilité que $ z_i $ doit être comparé à $ z_j $ dans notre algorithme. Maintenant, ils envisagent le sous-ensemble { $ z_i $ , ..., $ z_j $ }. N'est-ce pas ce cas de comparaison de $ z_i $ , $ z_j $ devient trop spécifique si nous considérons que sous-ensemble spécifique seulement? Je veux dire que nous utilisons une approche randomisée et que la probabilité de comparaison pourrait être dérivée à l'aide d'un aspect plus large, tel qu'une permutation de tous les cas possibles ou.

que nous utilisons un sous-ensemble spécifique et que trop trié n'est pas convaincant de la manière dont nous obtenons la probabilité correcte pour notre algorithme ...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

et la probabilité de 1 $ / (j-i + 1) $ -> NO TOTAL. d'éléments dans le Le sous-ensemble est également fixé pour spécifique $ i $ et $ j $

En considérant la probabilité de comparaison de $ z_i $ , $ z_j $ , le sous-ensemble dans lequel Les deux éléments sont là et qui doit être partitionné peut être n'importe quoi (c'est-à-dire composé de tout élément possible) et de toute taille (non seulement $ J-i + 1 $ ) ...

Peut être la condition de randomisation prend en réalité tout dans compte mais je ne l'obtiens pas. S'il vous plaît pouvez-vous m'expliquer la logique qu'ils utilisent pour trouver ladite probabilité et me convaincre également que nous trouvons correctement la probabilité de comparaison.

Pour référence, je joins les pages correspondantes d'introduction aux algorithmes 3ème ed-- CLRS

Answer 1

Une preuve très simple: je prétend que s'il y a des entiers de D avec des valeurs entre X et Y, et il y a n ≥ 2 éléments dans la matrice, la probabilité que X et Y sont comparées sont 2 / (D + 2 (D + 2 ), indépendant de n.

Preuve par induction: Si n= 2 puis clairement D= 0, la réclamation est que x et y sont comparées à la probabilité 2 / (0 + 2)= 1. Ceci est aussi clairement correct, car x et y doivent être comparé.

Maintenant, laissez n ≥ 3. Pour la première partitionnement, nous choisissons un pivot au hasard. Chaque élément de tableau est comparé contre le pivot et aucune autre comparaison n'est faite. Donc, si par coïncidence, nous choisissons X ou Y comme pivot, X et Y seront comparés. La probabilité est 2 / n. Si, par coïncidence, nous choisissons l'un des éléments D avec des valeurs entre X et Y, le partitionnement déplacera X à une seule partition et y à l'autre, ils ne sont donc jamais comparés. Si nous choisissons l'un des autres éléments N-D - 2, alors x et y finissent dans la même partition, et par induction, ils seront comparés à la probabilité 2 / (D + 2).

donc la probabilité que X et Y soient comparées sont

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

C'est bien sûr le même résultat que Yuval's, depuis | J - I |= D + 1. La randomisation rend l'analyse assez facile - si nous disions par exemple "si N> 5, nous choisissons 5 éléments au hasard et choisissez la médiane de ces 5 comme pivot", l'analyse serait beaucoup plus complexe.

ps. La preuve dans le papier est beaucoup plus facile: lorsque vous partitionnez le tableau, $ x_i $ et $ x_j $ Restez dans la même sous-partition jusqu'à ce qu'un pivot avec i <= pivot <= j est utilisé. Si ce pivot est i ou j, alors $ x_i $ et $ x_j $ est comparé, sinon ils ne sont pas par rapport. Donc, la chance est 2 / (ABS (J-I) + 1).

Answer 2

L'idée de la preuve est de calculer, pour tout deux éléments $ x, y $ dans la matrice, la probabilité qu'ils soient comparées dans l'algorithme. Cette probabilité pourrait potentiellement dépendre de l'ensemble de la matrice. Cependant, il s'avère que vous pouvez le calculer uniquement compte tenu des statistiques de commande de $ x, y $ , c'est-à-dire leur ordre relatif dans la matrice triée. Si vous savez que $ x $ est la $ i $ th le plus petit élément de la matrice et que $ y $ est la $ j $ ème élément le plus petit de la matrice, puis la probabilité que $ x, y $ est comparé est comparé est $ \ frac {2} {| ji | +1} $ .

.

Ce n'est pas un cas particulier - chaque élément $ x $ dans le tableau est la $ i $ Th le plus petit élément, pour une certaine valeur de $ i $ . Il s'agit simplement des informations pertinentes qui nous permettent de calculer la probabilité que $ x $ et $ y $ est comparé.