0
빠른 선택을 위해 마지막 요소보다 무작위 피벗을 선택하는 것이 중요합니까?빠른 선택의 피벗 요소 선택
필자는 항상 마지막 요소를 피벗으로 선택하여 필요한 요소를 찾을 수 있습니다. 런타임에 영향을 미칩니 까?
A
답변
3
피벗 선택은 주어진 배열에서 quickselect의 런타임에 큰 영향을 미칩니다. 당신은 항상 당신의 피벗과 마지막 요소를 선택하는 경우
결정 quickselect에서, 당신은 항상 정렬 된 목록 밖으로 선택하려고하면 어떻게되는지 상상. 피벗은 항상 최악의 피벗 일 것이며 배열에서 하나의 숫자 만 제거하여 Θ (n) 개의 런타임이됩니다. 무작위 quickselect에서
, 그것은 런타임이 될 것이라고 여전히 기술적으로 가능 Θ (N 2) 알고리즘은 항상 각 재귀 호출에 최악의 선택을하게, 그러나 이것은 매우 않을 경우. 런타임은 확률이 높은 O (n)이며 "킬러"입력이 없습니다. 즉
하는 결정 론적가 선택한 피벗과 quickselect는 항상이 임의의 피벗과 quickselect 더 킬러 입력이없는 동안, 그것은 시간 Θ (N 2)에서 실행되도록 강제 적어도 하나의 "킬러"입력 뛰어난 평균 시간 보장을 제공합니다. 분석 결과는 완전히 다릅니다.
희망이 도움이됩니다.
입력이 이미 정렬 된 경우 마지막 (또는 첫 번째) 요소를 피벗으로 선택하면 문제가 발생합니다. – Jasper