k 개의 가장 큰 원소를 추출하기

Question

만약 정수가 n이라면, O (k + logn) 시간에 n 개의 값 중에서 k 개의 가장 큰 원소를 나열 할 수 있습니까? 내가 얻은 가장 가까운 것은 최대 힙을 만들고 O (klogn) 시간이 걸리는 최대 k 시간을 추출하는 것입니다. 또한 inorder traversal 사용에 대해 생각합니다.

Answer 1

당신은 의 아이디어 퀵을 사용하기 때문에 때때로 빠른 선택라고한다 array.Technique에서 k 번째 요소를 추출하기위한 분할 및 정복 기술을 사용할 수 있습니다.

이것은 QuickSort, 우리는 다음의 정확한 위치 및 주위 partition 어레이에 피벗 부재를 이동하는 pivot 요소를 선택. 아이디어는, 은 완전한 퀵 소트을하지 않고 피벗 자체가 k 번째 작은 요소 인 지점에서 멈 춥니 다. 또한 피벗의 왼쪽과 오른쪽을 모두 재발행하지 말고 피벗의 위치에 따라 그 중 하나를 재발행하십시오. 이 방법의 최악의 시간 복잡도는 O(n^2)이지만, 평균적으로 O(n)에서 작동합니다.

Answer 2

힙을 생성하려면 O (nlogn)이 필요하고 k 요소를 추출하려면 O (klogn)가 필요합니다. k 요소를 추출하는 것이 O (klogn)라는 결론에 이르면 힙을 빌드하는 데 걸리는 시간을 걱정하지 않는다는 의미입니다.

그런 경우 목록 (O (nlogn))을 정렬하고 k 개의 가장 큰 요소 (O (k))를 취하십시오.

Answer 3

이 문제를 해결하는 방법.

1. 데이터를 정렬 한 다음 최상위 k를 가져옵니다. 정렬에는 O(n lg n)이 필요하고 상단 k를 반복하는 데 O(k)이 필요합니다. 총 시간 : O(n lg n + k)

2. 데이터에서 최대 힙을 작성하고 상위 k 배를 제거하십시오. 힙 빌드는 O(n)이고 다시 가기 작업을 수행하는 작업은 O(lg N)입니다. 총 시간 : O(n) + O(k lg n)

3. 실행중인 최대 힙 크기는 k로 유지하십시오. 모든 데이터를 반복하고 힙에 추가 한 다음 힙 전체를 가져옵니다. 총 시간 : O(n lg k) + O(k)

4. k 번째로 큰 값을 찾으려면 선택 알고리즘을 사용하십시오. 그런 다음 모든 데이터를 반복하여 해당 값보다 큰 모든 항목을 찾습니다.

   . 평균 실행 시간이 O(n)이고 최악의 경우가 O(n^2) 인 QuickSelect을 사용하면 k 번째로 큰 것을 찾을 수 있습니다. 총 평균 케이스 시간 : O(n) + O(n) = O(n). 총 최악의 경우 시간 : O(n^2) + O(n) = O(n^2).

   b. O(n)의 최악의 실행 시간을 가지지 만 현재 위치가 아닌 median-of-medians 알고리즘을 사용하면 k 번째로 큰 것을 찾을 수 있습니다. 총 시간 : O(n) + O(n) = O(n).