Нахождение верхнего лога n элементов несортированного списка за линейное время

Question

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

Спасибо

Answer 1

Чтобы получить верхние k элементов из несортированного списка, вы используете алгоритм Quickselect , чтобы разбить массив таким образом, чтобы первые k элементов были в начале массива.

Быстрый выбор в среднем равен O (n). Однако в патологических случаях это может занять O (n ^ 2) времени.

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

С точки зрения производительности, использование кучи для выбора элементов верхнего журнала (n) из списка почти наверняка будет быстрее, чем использование Quickselect. Причина в том, что Quickselect, хотя он (в среднем) линейный, имеет высокую постоянную. Для выбора 10 лучших элементов из списка 1 000 000 требуется почти то же время, что и для выбора 100 000 лучших элементов. Но мое исследование показывает, что использование кучи для выбора происходит быстрее, чем быстрый выбор, когда выбираемое число намного меньше (менее 1%) от общего количества элементов. Учитывая, что база журнала 2 из 1 000 000 составляет около 20, почти наверняка алгоритм выбора кучи будет быстрее, чем Quickselect.