Алгоритм выбора Runtime

Question

Я пытаюсь выяснить наиболее оптимальный способ вычисления запроса top-k для некоторой агрегации данных, скажем, массива. Раньше я думал, что лучший способ состоял в том, чтобы запустить массив и сохранить кучу или сбалансированное двоичное дерево размером k, используя это для вычисления значения top-k. Теперь я столкнулся с алгоритмом выбора, который, предположительно, работает еще быстрее. Я понимаю, как работает алгоритм выбора и как его реализовать, я просто немного запутался в том, как он работает в O (n). Я чувствую, что для того, чтобы он работал в O (n), вам должно быть очень повезло. Если вы продолжаете выбирать случайную точку поворота и разбивать вокруг нее, вполне возможно, что вы просто закончите, в основном, сортируя почти весь массив, прежде чем наткнуться на свой k-й индекс. Есть ли какие-либо оптимизации, например, не выбор случайного стержня? Или мое сохранение метода кучи/дерева достаточно для большинства случаев.

Answer 1

Что вы говорите о том, что есть quickselect, also known as Hoare's selection algorithm.

У него есть O(n) средний показатель производительности, но его наихудшая производительность составляет O(n2).

Как и quicksort, quickselect имеет хорошую среднюю производительность, но чувствителен к выбранной оси. Если выбраны хорошие опорные точки, что означает те, которые последовательно уменьшают поиск, заданный определенной долей, тогда набор поиска уменьшается экспоненциально и по индукции (или суммируя геометрический ряд), видим, что производительность является линейной, так как каждый шаг является линейным и общее время - это постоянное время (в зависимости от того, как быстро уменьшается набор поиска). Однако, если плохие совпадения последовательно выбираются, например, каждый раз снижается только по одному элементу, то наихудшая производительность является квадратичной: O(n2).

В терминах выбирающих шарниров:

Самым простым решением является выбор случайного поворота, которое дает almost certain линейное время. Детерминистически можно использовать среднюю стратегию (3) в среднем (как в quicksort), что дает линейную производительность на частично отсортированных данных, как это принято в реальном мире. Однако надуманные последовательности могут по-прежнему вызывать худшую сложность; Дэвид Муссер описывает последовательность «медианы 3 убийц», которая позволяет атаковать эту стратегию, что было одной из причин его алгоритма introselect.

Можно обеспечить линейные характеристики даже в худшем случае с использованием более сложной стратегии поворота; это делается в алгоритме median of medians. Однако накладные расходы на вычисление стержня высоки, и, следовательно, это обычно не используется на практике. Можно комбинировать базовый quickselect со средой медианов как резерв, чтобы получить как быструю среднюю производительность, так и линейную производительность наихудшего случая; это делается в introselect.

^{(цитаты из Wikipedia)}

Так вы довольно вероятно, чтобы получить O(n) производительности со случайными цапфами, но, если k мал и n велико, или если вы просто маловероятны, решение O(n log k) с использованием размера k кучи или BST могут превзойти это.

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