Как найти несколько наименьших элементов ki в массиве?

Question

Я борюсь с моей домашней работой и нуждаюсь в небольшом нажатии - вопрос заключается в том, чтобы разработать алгоритм, который в O (nlogm) позволит найти несколько наименьших элементов 1<k1<k2<...<kn, и у вас есть m * k. Я знаю, что простой алгоритм выбора принимает o (n) время для поиска k-го элемента, но как вы уменьшаете m в своем повторении? Я хотя бы делал и k1 и kn в каждом прогоне, но это выведет только 2, а не m/2.

Поблагодарите несколько поручений.

Answer 1

Если я правильно понял вопрос, у вас есть вектор K, содержащий m индексов, и вы хотите найти k-й ранжированный элемент A для каждого k из K. Если K содержит наименьшие m индексов (т. Е. k = 1,2, ..., m), то это легко можно сделать в линейном времени T = O (n), используя quickselect для нахождения элемента k_m (так как все меньшие элементы будут слева в конце Быстрый выбор). Поэтому я предполагаю, что K может содержать любой набор из m индексов.

Один из способов добиться этого - запустив quickselect на всех К одновременно. Вот алгоритм

QuickselectMulti(A,K) 
If K is empty, then return an empty result set 
Pick a pivot p from A at random 
Partition A into sets A0<p and A1>p. 
i = A0.size + 1 
if K contains i, then remove i from K and add (i=>p) to the result set. 
Partition K into sets K0<i and K1>i 
add QuickselectMulti(A0,K0) to the result set 
subtract i from each k in K1 
call QuickselectMulti(A1,K1), add i to each index of the output, and add this to the result set 
return the result set 

Если K содержит только один элемент, это то же самое, что и рандомизированное quickselect. Чтобы понять, почему время работы в среднем равно O (n log m), сначала подумайте, что произойдет, когда каждая точка разворота точно разделяет как A, так и K пополам. В этом случае вы получите два рекурсивных вызовов, так что у вас есть

T = n + 2T(n/2,m/2) 
    = n + n + 4T(n/4,m/4) 
    = n + n + n + 8T(n/8,m/8) 

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

On edit: Анализ этого алгоритма может сделать это проще, выбирая ось вращения, запустив p = Quickselect (A, k_i), где k_i - средний элемент K, а не выбор p случайным образом. Это гарантирует, что K будет разделяться пополам каждый раз, поэтому количество рекурсивных вызовов будет точно соответствовать журналу m, а так как quickselect работает в линейном времени, результат будет по-прежнему равен O (n log m).