정렬되지 않은 배열의 상위 5 개 요소

Question

정렬되지 않은 배열이 주어지고 효율적으로 상위 5 개 요소를 찾아야하므로 목록을 정렬 할 수 없습니다.

내 솔루션 :

• 이 배열의 최대 요소를 찾을 수 있습니다. O (n)

• 처리/사용 후이 최대 요소를 삭제하십시오.

• 단계 1을 반복한다. & 2, k 회 (이 경우 5 회).

시간 복잡도 : O (KN)/O (N) 공간 복잡성 : O (1)를.

나는 우리가 O (logN)의 최대 요소를 찾을 수 있다고 생각, 그래서 O (klogN)을 향상시킬 수있다. 내가 틀렸다면 나를 바로 잡아주세요.

우리가 이보다 더 잘 할 수 있을까요? 최대 힙을 사용하면 비효율적일까요?

PS - 숙제가 아닙니다.

Answer 1

당신이 n이 최대 요소의 수를 추적하는 목록 길이와 m 인 보조 힙이 O(nlogm)에서이 작업을 수행 할 수 있습니다 (상단에 마이너스 요소와 분 힙)를 사용 할 수 있습니다.

보조 힙은 최대 크기 (5)가 고정되어 있으므로 해당 구조의 작업은 O(1)으로 간주 할 수 있습니다. 이 경우 복잡도는 O(n)입니다.

의사 코드 :

foreach element in list: 
    if aux_heap.size() < 5 
     aux_heap.add(element) 
    else if element > aux_heap.top() 
     aux_heap.remove_top() 
     aux_head.add(element) 

Answer 2

partial quicksort 우리가 달성 O (n)을 사용하여, 이것은 임의의 보조 공간을 필요로하지 않는다. 다른 솔루션에서와 같이 최대 힙을 사용하려면 O (n log k) 시간이 필요합니다.