Алгоритм O (n) наихудшего случая для k-выбора

Существует еще один алгоритм вычисления статистики k-го порядка на основе мягкой кучи структуры данных, которая представляет собой вариант стандартной очереди с приоритетами, которому разрешено «искажать» некоторое количество хранимых в ней приоритетов. Алгоритм более подробно описан в статье в Википедии, но основная идея состоит в том, чтобы использовать мягкую кучу для эффективного (O(n) времени) выбора опорной точки для функции распределения, которая гарантирует хорошее разделение. В некотором смысле это просто модифицированная версия алгоритма медианы медиан, которая использует (возможно) более простой подход к выбору опорного элемента.

Мягкие кучи не особенно интуитивно понятны, но их довольно хорошее описание доступно в этой статье. («Простая реализация и анализ мягких куч Chazelle»), который включает формальное описание и анализ структуры данных.

Однако, если вам нужен действительно быстрый алгоритм O(n) для наихудшего случая, подумайте о том, чтобы изучить introselect. Этот алгоритм на самом деле довольно блестящий. Он начинается с использования алгоритма быстрого выбора, который неразумно выбирает опорную точку и использует это для разделения данных. Это очень быстро на практике, но имеет плохое поведение в худшем случае. Introselect исправляет это, отслеживая внутренний счетчик, который отслеживает его прогресс. Если когда-либо кажется, что алгоритм вот-вот ухудшится до времени O(n²), он переключает алгоритмы и использует что-то вроде медианы медиан, чтобы обеспечить гарантию наихудшего случая. В частности, он следит за тем, какая часть массива отбрасывается на каждом шаге, и если происходит некоторое постоянное количество шагов до того, как половина входных данных будет отброшена, алгоритм переключается на алгоритм медианы медиан, чтобы гарантировать, что следующая опорная точка будет хорошей до того, как будет отброшена половина входных данных. затем перезапуск с помощью быстрого выбора. Это гарантирует наихудший случай O (n) времени.

Преимущество этого алгоритма в том, что он чрезвычайно быстр для большинства входных данных (поскольку quickselect очень быстр), но имеет отличное поведение в худшем случае. Описание этого алгоритма вместе с соответствующим алгоритмом сортировки introsort можно найти по адресу в этой статье ("Алгоритмы интроспективной сортировки и выбора").

Надеюсь это поможет!

Я думаю, что вы действительно должны протестировать его и выяснить, какова производительность, когда у вас есть N миллионов элементов в вашем контейнере. Этот алгоритм уже реализован в библиотеке STL (C++), так как std::nth_element гарантированно ожидается O(n). Поэтому, если вы использовали C++, вы могли бы легко запустить некоторые тесты и посмотреть, достаточно ли хороша производительность для того, что вы ищете.

Заметным исключением является C++, который предоставляет шаблонный метод nth_element с гарантией ожидаемого линейного времени.

Это зависит. Если вы беспокоитесь о том, что в худшем случае это произойдет случайно, я бы не стал беспокоиться. По мере того, как данные становятся достаточно большими, наихудший случай становится настолько маловероятным, что вряд ли стоит защищаться от него.

Если вы делаете выбор в ситуации, когда клиент может предоставить данные в наихудшем порядке для отказа в обслуживании на вашем сервере, то, вероятно, стоит использовать медиану медиан, чтобы гарантировать, что наихудший порядок не повредит производительности в какой-либо значительной степени.

Обновлено:

Существует алгоритм линейного времени, модификация быстрой сортировки, предложенная самим изобретателем быстрой сортировки Хоаром. Я предлагаю обратиться к разделу 9.3 «Выбор в наихудшем линейном времени» в книге CLRS. Вот краткий алгоритм, предполагающий, что у нас есть метод random_partition из быстрой сортировки (который использует случайный свод для разделения):

FindKth(array, l, u, k)
{
   int m = random_partition(array, l, u);
   if m == k : return array[k] /*we have found the kth element*/
   if m > k: return FindKth(array, l, m-1, k); /* we have found element > kth largest, concentrate on the left partition */
   else: return FindKth(array, m+1, u, k-m); /* find the k-m th element in the right partition */
}

Вы также можете обратиться к книге Дональда Кнута TAOCP Vol.3 Sorting and Searching, стр. 633. Прелесть этого метода в том, что массив не нужно полностью сортировать! Я думаю, что STL nth_permutation использует этот метод, вы можете обратиться к разделу примечаний.