Как найти k-й по величине элемент в несортированном массиве длины n в O (n)?

Question

Я считаю, что есть способ найти k-й по величине элемент в несортированном массиве длины n в O (n). Или, возможно, это «ожидаемый» O (N) или что-то. Как мы можем это сделать?

Answer 1

Это называется нахождением k-го порядка статистики . Существует очень простой рандомизированный алгоритм (называемый quickselect ), который принимает O(n) среднее время, O(n^2) время наихудшего случая, и довольно сложный неслучайный алгоритм (называемый introselect ), принимающий O(n) худшее время. В Википедии есть информация, но она не очень хорошая.

Все, что вам нужно, находится в этих слайдов PowerPoint . Просто для извлечения базового алгоритма O(n) алгоритм наихудшего случая (интроселект):

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Это также очень подробно описано в книге «Введение в алгоритмы» Кормена и др.

Answer 2

Если вам нужен истинный O(n) алгоритм, а не O(kn) или что-то в этом роде, то вам следует использовать быстрый выбор (в основном это быстрая сортировка, когда вы выбрасываете раздел, который вам не интересен). У моего профессора отличная рецензия с анализом времени выполнения: ( ссылка )

Алгоритм QuickSelect быстро находит k-й наименьший элемент несортированного массива из n элементов. Это 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(n<sup>2</sup>)

Но если выбор действительно случайный, ожидаемое время выполнения задается как

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

, где мы делаем не совсем разумное предположение, что рекурсия всегда попадает в большее из A1 или A2.

Давайте догадаемся, что T(n) <= an для некоторых a. Тогда мы получим

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

и теперь каким-то образом мы должны получить ужасную сумму справа от знака плюс, чтобы поглотить cn слева. Если мы просто связываем это как 2(1/n) ∑<sub>i=n/2 to n</sub> an, мы получаем примерно 2(1/n)(n/2)an = an. Но это слишком много - нет места, чтобы выжать лишние cn. Итак, давайте расширим сумму, используя формулу арифметического ряда:

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

, где мы используем n как «достаточно большое», чтобы заменить уродливые floor(n/2) факторы гораздо более чистыми (и меньшими) n/4. Теперь мы можем продолжить с

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

при условии a > 16c.

Это дает T(n) = O(n). Это ясно Omega(n), поэтому мы получаем T(n) = Theta(n).

Answer 3

Быстрый Google для этого ('kth самый большой массив элементов') вернул это:

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

(это было специально для 3d крупнейших)

и этот ответ:

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)

Answer 4

Вам нравится быстрая сортировка. Выберите элемент наугад и засуньте все выше или ниже. В этот момент вы будете знать, какой элемент вы на самом деле выбрали, и если это k-й элемент, который вы сделали, в противном случае вы повторяете с корзиной (выше или ниже), что k-й элемент попадет. По статистике, время требуется, чтобы найти, что k-й элемент растет с n, O (n).

Answer 5

Сопутствующий программисту анализ алгоритма дает версию, что равно O (n), хотя автор утверждает, что постоянный коэффициент настолько высок, что вы, вероятно, предпочтете наивный метод сортировки списка-затем-выбора.

Я ответил на письмо вашего вопроса:)

Answer 6

Стандартная библиотека C ++ имеет почти такую ​​же функцию , функция , вызов nth_element, хотя она изменяет ваши данные. Он ожидал линейного времени выполнения 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

Answer 7

Хотя не совсем уверен насчет сложности O (n), но он обязательно будет между O (n) и nLog (n). Также обязательно быть ближе к O (n), чем nLog (n). Функция написана на Java

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;
    }
}

Answer 8

Я реализовал поиск k-го минимума в n несортированных элементах, используя динамическое программирование, в частности, турнирный метод. Время выполнения O (n + klog (n)). Используемый механизм указан как один из методов на странице Википедии об алгоритме выбора (как указано в одной из публикаций выше). Вы можете прочитать об алгоритме, а также найти код (java) на странице моего блога Finding Kth Minimum . Кроме того, логика может выполнять частичное упорядочение списка - вернуть первые K min (или max) за O (klog (n)) время.

Несмотря на то, что код обеспечивает результат k-го минимума, аналогичная логика может использоваться для нахождения k-го максимума в O (klog (n)), игнорируя предварительную работу, проделанную для создания дерева турниров.

Answer 9

Вы можете сделать это в O (n + kn) = O (n) (для постоянной k) для времени и O (k) для пространства, отслеживая k самых больших элементов, которые вы видели.

Для каждого элемента в массиве вы можете просмотреть список k наибольших и заменить наименьший элемент новым, если он больше.

Приоритетное решение для кучи Уоррена более изящно.

Answer 10

Сексуальный быстрый выбор в Python

def quickselect(arr, k):
    '''
     k = 1 returns first element in ascending order.
     can be easily modified to return first element in descending order
    '''

    r = random.randrange(0, len(arr))

    a1 = [i for i in arr if i < arr[r]] '''partition'''
    a2 = [i for i in arr if i > arr[r]]

    if k <= len(a1):
        return quickselect(a1, k)
    elif k > len(arr)-len(a2):
        return quickselect(a2, k - (len(arr) - len(a2)))
    else:
        return arr[r]