Quicksort와 Median 점근 적 행동

Question

Quicksort와 Median은 같은 방법을 사용합니다 (Divide and concuer). 그렇다면 다른 점근 적 행동을하는 이유는 무엇입니까?

퀵소트가 적절한 피벗을 사용하지 않을 수 있습니까?

Answer 1

Hoare의 원래 select 알고리즘을 사용하면 Quicksort에서 할 수있는 것과 동일한 최악의 성능을 얻을 수 있습니다.

중앙값의 중앙값을 사용하면 최악의 경우를 제한하고 가장 일반적인 경우는 더 느려집니다.

중앙값의 중앙값을 사용하면 Quicksort의 피벗을 찾을 수 있습니다.이 피치는 거의 동일한 효과를 나타냅니다 - 최악의 경우를 제한하면서 대부분의 경우 느려지는 경우가 있습니다.

물론 (일반적으로) 각 파티션 작업은 O (N)이며, 대략 O (N log N) 개의 전체적인 복잡성을 갖기 위해 log (N) 파티션 작업을 수행 할 것으로 예상합니다.

중앙값 찾기를 사용하면 약 O (로그 N) 단계까지 수행 할 것으로 예상되지만 이전 단계의 파티션은 중간 값 (또는 관심있는 사 분위수 등) 만 포함 할 수 있습니다. O (N log N) 대신 O (N log N) 정도의 복잡성을 갖기 때문에 전체 파티션을 항상 분할하지 않고 각 단계마다 파티션 크기를 (약) 2로 나눌 것을 기대합니다.

[큰 O는 정말 상한선 (즉, 최악의 경우) 복잡성을 표현하도록되어있는 반면이 전역 것을 참고, 나는 종류의 예상 복잡성을 표현하기 위해 큰 O 표기법을 남용하고 있습니다.]

을

Answer 2

Quicksort (링크의 메서드 참조)에서 partition 메서드를 사용하면 올바른 위치를 가진 요소의 인덱스를 반환하는 메디아를 찾을 수 있습니다.이 위치를 기준으로하면 중앙값을 포함하는 선택한 부분 만 확인하면됩니다 .

예를 들어 배열 길이는 5이므로 중앙값은 3입니다. 파티션 방법은 2를 반환하므로 전체 배열을 퀵 정렬로 사용하지 않고 배열의 위쪽 부분 만 2에서 5로 확인하면됩니다.