Как числа групп по размеру

Question

У меня есть п разные номера, и я хочу, чтобы отсортировать их в к групп, таких, что любое число в 1-й группе меньше, чем любое число в группе 2, и тех, кто в группе 2 меньше чем кто-либо в группе 3 и т. д. до группы k (номера не должны сортироваться внутри каждой группы). Меня просят разработать алгоритм, который работает в O (n log k), но я могу только придумать O (n^2).

Как это сделать?

Answer 1

Обратите внимание, что постановка задачи заключается в разделении п различных чисел в к группам. Это стало бы более сложным, если бы были дубликаты, как указано в ссылках на wiki ниже.

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

Неупорядоченная частичная сортировка с использованием алгоритма выбора с наихудшим временем O (n). Wiki ссылки:

http://en.wikipedia.org/wiki/Selection_algorithm

http://en.wikipedia.org/wiki/Selection_algorithm#Unordered_partial_sorting

http://en.wikipedia.org/wiki/Quickselect

http://en.wikipedia.org/wiki/Median_of_medians

http://en.wikipedia.org/wiki/Soft_heap#Applications

Answer 2

Вы можете достичь этого, изменив алгоритм сортировки Bucket, ниже я включил реализацию JavaScript, см. Github для получения дополнительной информации об исходном коде. Эта реализация использует 16 ведер, вам придется ее модифицировать, чтобы можно было использовать ведра k, и вы можете опустить сортировку самих ведер. Один из подходов заключался бы в использовании кодов 2^p, где p - наименьшее целое число, которое удовлетворяет 2^p < n. Этот алгоритм будет работать в O (п войти K)

// Copyright 2011, Tom Switzer 
 
// Under terms of ISC License: http://www.isc.org/software/license 
 

 
/** 
 
* Sorts an array of integers in linear time using bucket sort. 
 
* This gives a good speed up vs. built-in sort in new JS engines 
 
* (eg. V8). If a key function is given, then the result of 
 
* key(a[i]) is used as the integer value to sort on instead a[i]. 
 
* 
 
* @param a A JavaScript array. 
 
* @param key A function that maps values of a to integers. 
 
* @return The array a. 
 
*/ 
 
function bsort(a, key) { 
 
    key = key || function(x) { 
 
    return x 
 
    }; 
 
    var len = a.length, 
 
    buckets = [], 
 
    i, j, b, d = 0; 
 
    for (; d < 32; d += 4) { 
 
    for (i = 16; i--;) 
 
     buckets[i] = []; 
 
    for (i = len; i--;) 
 
     buckets[(key(a[i]) >> d) & 15].push(a[i]); 
 
    //This implementation uses 16 buckets, you will need to modify this 
 
    for (b = 0; b < 16; b++) 
 
     //The next two lines sort each bucket, you can leave it out 
 
     for (j = buckets[b].length; j--;) 
 
     a[++i] = buckets[b][j]; 
 
    } 
 
    return a; 
 
} 
 

 

 
var array = [2, 4, 1, 5, 3]; 
 

 
$('#result').text(bsort(array, function(x) { 
 
    return x 
 
}));

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> 
 
<div id="result"></div>

Answer 3

Использование алгоритма K-выбор с статсумме из QuickSort - QuickSelect.
Пусть K - сила 2 для простоты.
На первом этапе мы делаем разбиение N элементов, оно принимает O (N) ~ p * N время, где p - некоторая константа
На втором этапе мы рекурсивно делаем 2 раздела N/2 элементов, требуется 2 * p * N/2 = p * N раз.
На третьем этапе мы делаем 4 раздела N/4 элементов, оно принимает 4 * p N/4 = p N раз.
...
На последнем этапе мы делаем K-разбиения элементов N/K, оно принимает K * p * N/K = p * N раз.

Примечание есть Log (K) стадии, поэтому общее время входа (K) * р * N = O (N * Log (K)

Answer 4

Спасибо за вашу помощь, в основном Быстрый выбор (или любой алгоритм линейной временной сортировки, который находит k-ю статистику в линейном времени, достаточно), и после запуска k-1 раз мы делаем двоичный поиск по исходному массиву, чтобы разделить элементы на группы, получив O (nlog k) .

Кроме того, если вы не хотите, чтобы сделать бинарный поиск, в Быстрый выбор, вы можете также отделить элементы и найти статистические данные в каждом подмножестве! @rcgldr, @MBo спасибо за ваши идеи!