이 내 데이터 구조 숙제에 대한 질문 하나 : 우리는 퀵와 같은 배열의 1 % 이상인지 이하의 피벗 요소를 찾기 위해 보장 선형 시간 절차를 가지고증명하는 방법 Quicksort는 특별한 조건이있는 O (n * lg n)입니까?
가 가정 피벗과 같고 적어도 1 %는 피벗보다 크거나 같습니다. Quicksort가 최악의 경우의 복잡성 O (ng n)을 가짐을 보여주십시오.
일반적으로 quicksort의 최악의 경우의 복잡성은 O (n^2)입니다. 선택한 피벗의 모든 값이 촬영 된 세트 중 가장 크거나 작을 때이 문제가 발생한다고 읽었습니다.
짐작하면 적어도 1 %의 배열이 더 크고 배열의 1 % 이상이 피벗보다 작다는 가정하에 피벗이 가장 작거나 가장 큰 상황을 제거합니다 요소 집합입니다. 따라서 그것은 결코 O (n^2) 일 수 없습니다
이 소리가 맞습니까?
이 유형의 문제에서 주된 요인은 O (log (n)) 단계 만 있음을 보여줍니다.
이상적인 퀵 재귀는 우리가 쉽게 O (NlogN)로 마스터 정리로 표시 할 수 있습니다
T(N) = 2T(N/2) + O(n)
입니다.
O (n) 항은 재귀 트리의 모든 레벨에서 하나의 요소입니다. 또한 모든 요소는 이상적인 경우 모든 단계에서 처리되어야합니다. 기술적으로 대부분의 요소가 다른 요소보다 재귀 트리를 훨씬 더 멀리 만들 것이지만, "최악의 시나리오"가 발생하고 모든 요소가 모든 수준에서 처리된다는 점을 점근 손실없이 가정 할 수 있습니다. 따라서 우리가해야 할 일은 주어진 가정 하에서 재귀 트리에 최대 O (log (N)) 단계가 있음을 증명하는 것입니다.
퀵 재귀 당신의 가정을 제공 :
T(N) = T(N/100) + T(99N/100) + O(n).
, 최대 작업의 일정 번호가 정렬 일어날 것입니다 우리는 한 번 재귀 트리의 단일 지점에서 99 개 이하의 요소가 WLOG를 가정 할 수있다 그것들 (그러므로, O (1) * O (n) = O (n) 연산은 최하위 단계에서 발생하며, 재귀 트리는 축소도 성장도하지 않는다).
그래서 전체 트리에서 최대 단계 수를 어떻게 증명할 수 있습니까? 글쎄, 우리는 불행한 요소 (들)을 따른다! 우리는 N 개의 원소로 시작한다고 가정한다. 가정을 감안할 때 우리가 실제로 신경을 쓰는 재귀 트리 수준의 마지막 단계에서 가장 큰 지점을 형성하는 50 ~ 99 개의 요소가 있어야합니다. 99 %의 일부가 될 수있는 최악의 작업.
따라서 우리는 X 반복을 통해 1 % 씩 잘라낸 요소가 최대 99 개 있습니다. 이것은 이전에 보아 왔던 다른 재귀 트리, 즉 "기하학적으로 감소하는"트리처럼 보입니다. 수학에 관해서 :
99 = N*(.99)^X
99/N = (1/.99)^-X
(1/.99)^X = N/99
log_(1/.99) (1/.99)^X = log_(1/.99) N/99
X = log_(1/.99) N/99
오른쪽에서의 용어는 O (log (N))입니다. 그래서 이것은 각각 최대 O (N) 개의 작업을하는 재귀 수준의 최대 수이므로 전체 작업은 O (Nlog (N))입니다.
당신이 그보다 더 엄격한 것을 원한다면 (처음부터 실제 재귀 증명을 설명하는 것은 많은 일입니다), 그러나 이것은 대부분의 대학교에서 받아 들일 수 있습니다.
@MitchWheat 얼마나 순진합니까? 피봇 선택에서 중간 값이 없습니까? – John
@ 존 : naïve == 바닐라 == 중앙값 없음. –