[performance] O (n)에서 길이 n의 정렬되지 않은 배열에서 k 번째로 큰 요소를 찾는 방법은 무엇입니까?

당신이 진실을 원한다면 O(n) 알고리즘O(kn) 이와는 반대로 quickselect를 사용해야합니다 (기본적으로 관심없는 파티션을 버리는 곳은 quicksort입니다). 내 교수님은 런타임 분석을 통해 훌륭한 글을 작성했습니다 : ( reference )

QuickSelect 알고리즘은 정렬되지 않은 n요소 배열에서 k 번째로 작은 요소를 빠르게 찾습니다 . 이것은 RandomizedAlgorithm 그래서 우리는 최악의 경우는 계산, 예상 시간을 실행할 수 있습니다.

알고리즘은 다음과 같습니다.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

이 알고리즘의 실행 시간은 무엇입니까? 적이 우리를 위해 동전을 뒤집 으면 피벗이 항상 가장 큰 요소이며k 항상 1이며

T(n) = Theta(n) + T(n-1) = Theta(n2)

그러나 선택 사항이 실제로 임의 인 경우 예상 실행 시간은 다음과 같습니다.

T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))

우리는 재귀가 항상 더 큰 영역에 도달한다고 전적으로 합리적이지 않다고 가정하고 있습니다. A1 또는A2 .

T(n) <= an일부를 추측 해 봅시다a . 그럼 우리는 얻는다

T(n)
 <= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
 = cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n ai

이제 어떻게 든 우리는 왼쪽에있는 +를 흡수하기 위해 더하기 부호의 오른쪽에 끔찍한 합계를 가져와야합니다 cn. 우리가 방금 묶으면 대략적으로 얻을 수 있습니다 . 그러나 이것은 너무 큽니다-여분으로 짜낼 공간이 없습니다.2(1/n) ∑i=n/2 to n an2(1/n)(n/2)an = ancn . 산술 시리즈 공식을 사용하여 합계를 확장 해 봅시다.

∑i=floor(n/2) to n i
 = ∑i=1 to n i - ∑i=1 to floor(n/2) i
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2
 <= n2/2 - (n/4)2/2
 = (15/32)n2

여기서 우리는 n이 “충분히 크다”는 것을 이용하여 못생긴 floor(n/2)요소를 훨씬 더 깨끗하고 작은 것으로 대체합니다 n/4. 이제 우리는 계속할 수 있습니다

cn + 2 (1/n) ∑i=floor(n/2) to n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

제공 a > 16c.

이 제공합니다 T(n) = O(n). 분명히 Omega(n)그렇습니다 T(n) = Theta(n).

답변

"Make one pass through tracking the three largest values so far."

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)

const int N = ...;
double a[N];
// ...
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a

public int quickSelect(ArrayList<Integer>list, int nthSmallest){
    //Choose random number in range of 0 to array length
    Random random =  new Random();
    //This will give random number which is not greater than length - 1
    int pivotIndex = random.nextInt(list.size() - 1);

    int pivot = list.get(pivotIndex);

    ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
    ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();

    //Split list into two.
    //Value smaller than pivot should go to smallerNumberList
    //Value greater than pivot should go to greaterNumberList
    //Do nothing for value which is equal to pivot
    for(int i=0; i<list.size(); i++){
        if(list.get(i)<pivot){
            smallerNumberList.add(list.get(i));
        }
        else if(list.get(i)>pivot){
            greaterNumberList.add(list.get(i));
        }
        else{
            //Do nothing
        }
    }

    //If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
    if(nthSmallest < smallerNumberList.size()){
        return quickSelect(smallerNumberList, nthSmallest);
    }
    //If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
    //The step is bit tricky. If confusing, please see the above loop once again for clarification.
    else if(nthSmallest > (list.size() - greaterNumberList.size())){
        //nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
        //smallerNumberList
        nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
        return quickSelect(greaterNumberList,nthSmallest);
    }
    else{
        return pivot;
    }
}