먼저 n 요소 배열을 정렬하여 첫 번째 k 요소의 순서가 가장 낮습니다 (위치 알고리즘에서)

Question

이것은 내가 붙어있는 숙제 문제입니다.

첫 번째 k- 요소가 가장 작고 증가하는 순서로 n 요소 배열을 정렬해야합니다. k < = n/log (n)의 경우 알고리즘은 O (n)이어야합니다.

나의 해결책 : 내가 생각했던 간단한 해결책은 배열을 heapify (O (n))하는 것이다. 그런 다음 k 요소를 삭제하고 힙/배열의 시작 색인을 0에서 1 - 2 - 3으로 이동합니다 (등등, k에서 끝까지 계속). 이것은 O (n + k * lg (n) + k * n) = O (kn + k * lg (n)) 일 것이다. 주어진 k의 조건에 대해 O (n^2/log (n) + n)이된다.

또 다른 가능한 구현은 O (n)이 될 기수 정렬을 사용하는 것입니다.하지만 전체 배열을 정렬하므로 k 요소를 정렬하라는 요청을 받았기 때문에 올바른 해결책이 아닌 것 같습니다.

나에게 답을 알려줄 필요는 없지만 힌트가 도움이 될 것입니다.

Answer 1

나는 당신의 힙 아이디어를 좋아합니다. 나는 실제로 그것이 당신이 열거 한 시간 범위 내에서 작동 할 것이라고 생각하고 분석에 약간의 결함이 있다고 생각합니다.

다음을 수행한다고 가정 해보십시오. 배열에서 내부 힙을 빌드 한 다음 최소 k 개 요소를 큐에서 빼내고 나머지 n-k 요소는 배열의 어느 위치에 두었습니다. 요소가 어디에서 끝날지 생각하면 배열의 k 번째 요소가 배열의 뒤에 오름차순으로 저장되어야하고 나머지 n-k 요소는 힙 순서로 앞에 있어야합니다. 이것을 보는데 어려움이 있다면, heapsort가 어떻게 작동하는지 생각해보십시오 - k가 대기열에서 제외 된 후에 가장 큰 k 요소가 뒤에 내림차순으로 있고 나머지 요소는 앞에 힙순으로 정렬되어 있습니다. 여기서는 max-heap을위한 min-heap을 교환했기 때문에 이상한 순서가 있습니다. 결과적으로 끝에서 배열을 뒤집을 경우 앞에 k 값이 작은 요소가 앞에오고 n-k 나머지 요소가옵니다. 다음

이 올바르게 K 작은 요소를 찾을 것이며, 실행은 판정 :

heapify의

• 비용 : O (n)은 K를 꺼내의
• 비용 : O (K 로그 N) 어레이를 반전
• 비용 : O (N)
• 총 비용 : O (N + K 로그 N) 지금

, 가정 K ≤ N 그/로그 n. 그런 다음 런타임은

O (N + K 로그 n을) = O는 (N + (N/로그 n)이 로그 n) = O는 (n)이

그래서이 완료입니다! 알고리즘은 잘 작동합니다. 또한, O (1) 보조 공간이 필요합니다 (힙을 내장 할 수 있으며 O (1) 공간에서 배열을 뒤집을 수 있습니다).

더 잘 할 수 있습니다. @timrau는 quickselect (또는 더 일반적으로 선형 시간 선택 알고리즘)를 사용한다는 주석에서 제안했습니다. 이 알고리즘은 배열의 첫 번째 k 슬롯에 순서대로 최하위 k 개의 요소를 넣고 마지막 n - k 슬롯에 남아있는 n - k 요소를 순서대로 배열하도록 배열을 다시 배열합니다. 그렇게하면 k (nifty!)에 관계없이 O (n) 시간이 걸립니다. 여러분이 그렇게했다고 가정하고, 첫 번째 k 요소를 정렬하면됩니다.이것은 O (n + k log n) 시간 힙 기반 알고리즘보다 점근 적으로 나은 시간 O (n + k log k)를 필요로합니다.

알려진 선형 시간 선택 알고리즘 중에서 조심하면 빠른 선택과 중앙값 알고리즘을 모두 구현할 수 있으므로이 방법에 필요한 총 공간은 O (1)입니다.

Answer 2

O (n log k) 인 약간 수정 된 힙 선택 알고리즘으로이 작업을 수행 할 수 있습니다. Quickselect의 O (n) 복잡도보다 점차적으로 "나 빠졌지 만"힙 선택은 k가 n과 비교할 때 매우 작을 때 Quickselect를 능가 할 수 있습니다. 자세한 내용은 When theory meets practice을 참조하십시오. 하지만 백만 개의 목록에서 상위 1,000 개의 항목을 선택하는 경우 힙 선택이 거의 확실합니다.

어쨌든이 작업을 수행하려면 배열의 첫 번째 k 항목부터 배열 앞쪽에 크기 k의 최대 힙 (표준 BuildHeap 함수 사용)을 작성해야합니다. 그것은 O (k)를 필요로합니다. O를 취할 것

for (i = k; i < length; ++i) 
{ 
    if (array[i] < array[0]) // If item is smaller than largest item on heap 
    { 
     // put large item at the current position 
     temp = array[i]; 
     array[i] = array[0]; 

     // put new item at the top of heap and sift it down 
     array[0] = temp; 
     SiftDown(0); 
    } 
} 

시간 (N K 로그), 그러나 제한 요인은 내부의 코드를 수행 할 필요가 얼마나 많은 시간 정말 그런 다음,이 같은 배열의 항목의 나머지 부분을 처리 가정 어구. 항목이 이미 힙에있는 가장 큰 항목보다 작은 경우에만이 단계에서 처리를 수행합니다. 최악의 경우는 배열이 역순으로 정렬 된 경우입니다. 그렇지 않으면 놀라 울 정도로 빠릅니다.

이 작업이 완료되면, 가장 작은 k 항목이 배열의 앞에 있습니다.

그런 다음 O (k log k) 인 그들을 정렬해야합니다.

그래서 전체 절차는 O (k + n log k + k log k)입니다. k가 n보다 훨씬 작 으면 Quickselect보다 훨씬 빠릅니다.