Я борюсь с домашним заданием, и мне нужно немного подтолкнуть - вопрос в том, чтобы разработать алгоритм, который за время O (nlogm) найдет несколько наименьших элементов 1<k1<k2<...<kn, и у вас есть m * k. Я знаю, что простой алгоритм выбора требует o(n) времени, чтобы найти k-й элемент, но как уменьшить m в вашем повторении? Я хотел бы делать и k1, и kn в каждом прогоне, но это займет только 2, а не m/2.
Был бы признателен за некоторые направления. Спасибо
Если я правильно понимаю вопрос, у вас есть вектор K, содержащий m индексов, и вы хотите найти k-й ранжированный элемент A для каждого k в K. Если K содержит наименьшие m индексов (т.е. k = 1,2, ...,m), то это можно легко сделать за линейное время T=O(n) с помощью быстрого выбора, чтобы найти элемент k_m (поскольку все меньшие элементы будут слева в конце быстрого выбора). Итак, я предполагаю, что K может содержать любой набор m индексов.
Один из способов добиться этого — запустить quickselect для всех K одновременно. Вот алгоритм
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 содержит только один элемент, это то же самое, что и рандомизированный быстрый выбор. Чтобы понять, почему время работы в среднем равно 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)
Так как m уменьшается вдвое каждый раз, то n будет встречаться в этом суммировании log m раз. Чтобы фактически получить ожидаемое время выполнения, требуется немного больше работы, потому что вы не можете предположить, что сводная точка разделит оба массива пополам, но если вы выполните вычисления, вы увидите, что время выполнения на самом деле составляет O (n log м) в среднем.
При редактировании: анализ этого алгоритма может упростить это, выбрав опорную точку, запустив p=Quickselect(A,k_i), где k_i — средний элемент K, а не выбирая p случайным образом. Это гарантирует, что K каждый раз делится пополам, и поэтому количество рекурсивных вызовов будет точно log m, а поскольку quickselect выполняется за линейное время, результат все равно будет O(n log m).
m? Почему вы используете little-oh вo(n)? - person NPE schedule 09.10.2013