Probabilidade de que dois elementos são comparados em randomizados quicksort

Question

Estou tendo um problema em uma parte específica do randomizados de ordenação rápida análise.

Conforme a análise de ordenação rápida algoritmo o pivô é escolhido a partir de determinado subconjunto no qual ele é chamado a partir de um índice aleatório, em vez de apenas a escolha de um índice específico a cada vez.

Agora, suponha que nós damos uma matriz de tamanho de dizer $n$ para o nosso estudo randomizado quicksort algoritmo.

Agora eu solicitação de ter um olhar para a prova do lema-7.1 no texto apresentado abaixo.Agora temos dado uma matriz para o nosso algoritmo, que pode ser de qualquer permutação dos elementos, mas na parágrafo logo após a prova de $lema-7.1$.

por que o autor está considerando uma classificados instância de nossa matriz de entrada ao fazer a análise?

Além disso, se olhar para o texto depois de equação $(7.2)$ onde não justificaram sua lógica de encontrar a probabilidade de que $z_i$ deve ser comparado com $z_j$ no nosso algoritmo.Agora que eles estão considerando o subconjunto {$z_i$,...,$z_j$}.Não é este o caso de comparação de $z_i$,$z_j$ ficar muito específicas, se considerarmos que o subconjunto específico só?Eu quero dizer que nós estamos usando randomizados abordagem e a probabilidade de comparação pode ser derivada de um olhar mais amplo, como uma permutação de todos os casos possíveis, mais ou menos.

Que estamos usando um subconjunto específico e que os demais classificados não é convincente de como estamos chegando a probabilidade correta para o nosso algoritmo...

     {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??

E a probabilidade de $1/(j-i+1)$ -> no total.de elementos na subconjunto é também fixado para específicos $i$ e $j$

Considerando a probabilidade de comparação de $z_i$,$z_j$, o subconjunto em que os dois elementos estão lá e que é para ser particionada pode ser qualquer coisa(que eu.e composto por todos os possíveis elementos) e de qualquer tamanho (não apenas $j-i+1$)...

Pode ser a condição de aleatoriedade, na verdade, é levar tudo em conta, mas não estou conseguindo.Por favor, você pode me explicar a lógica de que eles estão usando para encontrar a referida probabilidade e por favor me convencer de que somos corretamente encontrar a probabilidade de comparação.

Para referência, eu estou anexando as páginas correspondentes de INTRODUÇÃO A ALGORITMOS 3ª ED-CLRS

Answer 1

Um muito simples prova:Eu acho que se há d inteiros com valores entre x e y, e n ≥ 2 elementos na matriz, então a probabilidade de que x e y são comparados é 2 / (d + 2), independente de n.

Prova por indução:Se n = 2 então, claramente, d = 0, então a alegação é de que x e y são comparados com probabilidade 2 / (0 + 2) = 1.Este é também claramente correta, desde que x e y devem ser comparados.

Agora, seja n ≥ 3.Para o primeiro particionamento, escolha um pivô de forma aleatória.Cada elemento da matriz é comparada com a dinâmica, e não outras comparações são feitas.Assim, se por um acaso, podemos escolher x ou y, como pivô, x e y serão comparados.A probabilidade de que 2 / n.Se por um acaso, podemos escolher uma de d elementos com valores entre x e y, então o particionamento mover x para uma partição e y para os outros, para que eles nunca são comparados.Se escolher um dos outros n - d - 2 elementos, então x e y terminam na mesma partição, e por indução eles serão comparados com probabilidade 2 / (d + 2).

Portanto, a probabilidade de que x e y são comparados é

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.

É claro que o mesmo resultado Yuval, pois de vez em |j - i| = d + 1.A aleatoriedade da amostra torna a análise muito fácil se disséssemos, por exemplo, "se n > 5, então nós escolhemos os 5 elementos ao acaso e escolha a mediana desses 5, como pivô", a análise seria muito mais complexo.

PS.A prova de que o papel é muito mais fácil:Como você particionar a matriz, $x_i$ e $x_j$ permanecer na mesma sub-partição até um pivô com eu <= pivot <= j é usado.Se essa dinâmica é i ou j, em seguida, $x_i$ e $x_j$ são comparadas, caso contrário, eles não são comparadas.Então a chance é de 2 / (abs (j-i) + 1).

Answer 2

A idéia da prova é de computar, para quaisquer dois elementos $x,y$ na matriz, a probabilidade de que eles são comparados no algoritmo.Esta probabilidade pode potencialmente dependem toda a matriz.No entanto, acontece que você pode calcular apenas dada a ordem de estatísticas de $x,y$, isto é, sua ordem relativa na matriz ordenada.Se você sabe que $x$ é o $i$esimo menor elemento na matriz e que $y$ é o $j$esimo menor elemento na matriz, então a probabilidade de que $x,y$ são comparados é $\frac{2}{|j-i|+1}$.

Este não é um caso especial – cada elemento $x$ na matriz é o $i$esimo menor elemento, para algum valor de $i$.Esta é apenas a informação pertinente que nos permite calcular a probabilidade de que $x$ e $y$ são comparados.