무작위 퀵 무작위 퀵을 구현

방법 항목 : 랜덤 피벗 선택

방법 2 : 입력의 랜덤 순열을 생성하고 피벗

같이, 제 1 요소를 고른다 퀵에게 먹이

방법 1은 방법 2와 무작위 화가 동일합니까?

참고 : Method2처럼 보이는 모든 파티션이 똑같이 생성되지만 method1은 그렇지 않습니다. 그래서 그들이 같지 않다면 성능에 어떤 영향이 있는지 이해하고 싶습니다.

2013-02-13 vikky.rk

예라고 말하고 싶습니다. 각 단계에서의 이진 파티션은 두 방법 모두에서 동일한 법칙을 따릅니다. –

예. 어느 경우 든 특정 요소가 피벗으로 선택 될 확률은 1/len (입력)입니다. (그러나 두 번째 방법은 랜덤 치환을 생성하기 위해 추가 선형 패스가 필요하므로 상수 요소에 의해 거의 확실하게 느려집니다.)

2013-02-13 22:13:48 jacobm

그러나 특정 입력에 대해서는 두 번째 방법이 모두 n! 순열은 똑같이 발생하지만 첫 번째 방법은 입력의 상대적 순서를 변경하지 않으므로 입력에 가능한 모든 파티션을 포함하지는 않습니다. 그래서 나는 차이가 있다고 느끼지만 어떤 영향을 미칠지 확신하지 못합니다. –

"모든 가능한 파티션"이 무슨 뜻인지 잘 모르겠습니다. 피벗 요소보다 크거나 작은 요소 집합은 순서에 전혀 의존하지 않습니다. – jacobm

나는 혼란 스럽다. 미안하다. 이해한다. 감사 –

답변