quicksort => 예상 실행 시간을 사용하여 배열에서 k 번째로 작은 항목을 찾으십니까?

Question

수정 된 버전의 quicksort를 사용하여 배열에서 k 번째로 작은 항목을 찾으려면 왜 예상 진 행 시간 O (n) (Programming Pearls book에 명시된 바와 같이)입니까?

1) Runs quick sort on the array 
2) If k is > the correct location of pivot, then run quicksort on the 2nd half. 
Otherwise run it on the first half. 

나는 인상이 걸릴 것이라고 O (N * logn) 작업에서였다

내가 사용하는 알고리즘은 다음을 수행합니다.

Answer 1

이 링크, K 번째 순서 통계는 점점 뒤에 무작위 빠른 선택, http://pine.cs.yale.edu/pinewiki/QuickSelect,

아이디어에 대한 증거를 이해하는 데 도움이 될 가능성은 (1)에 한 파티션를 않습니다 피벗을 선택하고 빠른 정렬에 의해 제안 된대로 데이터를 파티션하고 검색 할 요소가있는 파티션을 찾으십시오. 파티셔닝은 O (n)의 복잡성이 있습니다. 파티셔닝 한 후에는 빠른 정렬과 달리 두 파티션을 모두 처리해야하는 결과 파티션 중 하나만 선택하여 처리해야합니다. 아래의 설명에서

, 나는 모든 반복에, 피벗 동일 반쪽의 배열을 분할, 우리가 가정하자, 단순 들어

, 증명하려고하지만, 예상되는 복잡성을 이해하는 직관적 인 생각을주고 싶어하고 있지 않다 다음 복잡성은 모든 반복에 최악의 경우는 처리하기 위해 (1 n 형) 것 분할 요소를 받고, 직관적 인 이해를 돕기 위하여

n + (n/2) + (n/4) ... <= c.n, O(n) 

로, 명확 O (N)입니다 단지의 확률로 발생 (1/n)이다. 그래서 최악의 경우의 복잡성은 어쨌든 O (n^2)입니다.

예상되는 복잡성에 대한 엄격한 증거를 원하는 경우 제공되는 링크를 통해 이동할 수 있습니다.

Answer 2

해당 알고리즘은 책에 설명되어 있지 않습니다. (2) 등