무작위 QuickSort에서 두 요소가 비교 될 확률

cs.stackexchange https://cs.stackexchange.com/questions/123575

문제

무작위 퀵 정렬 분석의 특정 부분에 문제가 있습니다.

무작위 퀵 정렬 알고리즘에 따라 피벗은 매번 특정 색인을 선택하는 대신 임의의 인덱스에서 호출되는 주어진 서브 세트에서 선택됩니다.

이제 우리는 $ n $ 을 우리의 무작위 QuickSort 알고리즘으로 제공한다고 가정합니다.

여기에 이미지 설명을 입력하십시오 >>

여기에 이미지 설명을 입력하십시오 >>

이제는 아래의 텍스트에서 LEMMA-7.1의 증거를 살펴 보도록 요청합니다. 이제 우리는 $ LEMMA-7.1 $의 증명 직후에 요소의 순열이 될 수있는 단락에서 알고리즘에 배열을 부여했습니다. .

분석을하는 동안 입력 배열의 정렬 된 인스턴스를 고려한 작성자는 무엇입니까?

Equation $ (7.2) $ 의 텍스트를 보면 $ z_i $ 은 알고리즘에서 $ z_j $ 과 비교되어야한다. 이제 서브 세트 { $ z_i $ , ..., $ z_j $ }을 고려하고 있다는 점에서 $ z_i $ , $ z_j $ 을 고려하면 너무 구체적으로 얻는이 경우는 그렇지 않습니다. 특정 하위 집합 만? 우리는 무작위 접근법을 사용하고 있으며 모든 가능한 경우의 순열과 같이보다 광범위한 모양을 사용하여 비교 확률이 유도 될 확률을 의미합니다.

우리가 특정 하위 집합을 사용하고 너무 정렬 된 것은 우리가 알고리즘에 대한 정확한 확률을 얻는 방법에 대해 확신하지 못합니다 ... 

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

및 $ 1 / (j-i + 1) $ -> 총 아니오의 확률. 그 요소의 요소의 하위 집합도 수정되었습니다 특정 $ i $ 및 $ j $

$ z_i $ , $ z_j $ 의 비교 확률을 고려하여 두 요소는 거기에 있고 분할 될 수있는 것은 (즉, 가능한 모든 요소로 구성된) 일 수 있습니다 ( $ J-I + 1 $ ) ...

무작위 화 조건이 실제로 모든 것을 취하는 것일 수 있습니다. 계정이지만 나는 그것을 얻지 못한다. 그 확률을 찾기 위해 그들이 사용하고있는 논리를 설명 할 수 있고 비교의 확률을 올바르게 찾는 것을 올바르게 발견했다는 것을 확신 해주십시오.

참조 용으로 알고리즘에 대한 해당 페이지를 첨부하고 있습니다. 3RD ED-- CLRS

Page 182 > 페이지 183 Page 184

도움이 되었습니까?

해결책

매우 간단한 증거 : X와 Y 사이의 값이있는 정수가 있고 배열에 n ≥ 2 요소가있는 경우 x와 y가 비교할 가능성이 2 / (d + 2)입니다. ), n과 무관합니다.

유도에 의한 증명 : N= 2이면 분명히 d= 0이면, 청구는 x와 y가 확률 2 / (0 + 2)= 1과 비교된다는 것을 주장하는 것은 또한 x와 y가 분명히 정확하다는 것입니다. 비교된다.

이제 n ≥ 3. 첫 번째 파티셔닝을 위해 임의의 피벗을 선택합니다. 모든 배열 요소는 피벗과 비교되며 다른 비교가 이루어지지 않습니다. 일치로 Pivot, X 및 Y를 비교하면서 X 또는 Y를 선택합니다. 그 확률은 2 / n입니다. 일치로 X와 Y 사이의 값이있는 D 요소 중 하나를 선택한 다음 파티셔닝이 X로 X를 하나의 파티션과 y로 이동하여 비교하지 않으므로 절대로 비교하지 않습니다. 다른 n-d-2 요소 중 하나를 선택한 다음 X와 Y는 동일한 파티션에서 끝나고 유도에 의해 확률 2 / (d + 2)와 비교됩니다.

x와 y가 비교 될 확률은 

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.
.

물론 Yuval 's와 같은 결과, 이후 | J - I |= D + 1. 무작위적으로 분석을 쉽게 만듭니다. "예를 들어"5시 5 일이면 5 개의 요소를 무작위로 선택하고 그 5의 중앙값을 피벗으로 선택합니다. "분석은 훨씬 더 복잡 할 것입니다.

ps. 용지의 증명은 훨씬 쉬워집니다. $ x_i $ 및 $ x_j $ i <= pivot <= j가 사용 된 피벗이 사용될 때까지 동일한 하위 파티션에 남아 있습니다. 그 피벗이 i 또는 j이면 $ x_i $ 및 $ x_j $ 이 비교됩니다. 그렇지 않으면 비교했다. 따라서 기회는 2 / (ABS (J-I) + 1)입니다.

다른 팁

증명의 아이디어는 $ x, y $ , 알고리즘에서 비교할 확률을 계산하는 것입니다. 이 확률은 잠재적으로 전체 배열에 의존 할 수 있습니다. 그러나 $ x, y $ , 즉 정렬 된 배열의 상대 순서를 지정한 것만으로 만 계산할 수 있다는 것이 밝혀졌습니다. $ x $ 은 배열의 $ i $ th $ y $ 은 배열의 $ j $ th 가장 작은 요소이며 $ x, y $ 은 $ \ frac {2} {| ji | +1} $ 입니다.

이것은 특별한 경우가 아닙니다. $ x $ 은 $ i $ $ i $ 의 일부 가치에 대해 가장 작은 요소. 이것은 우리가 $ x $ 및 $ y $ 의 확률을 계산할 수있는 적절한 정보 일뿐입니다. 비교.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top