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

Question

Кроме алгоритма медианы медиан, есть ли другой способ сделать k-выборку за O (n) наихудшего случая?Имеет ли смысл применение медианы медиан;Я имею в виду, достаточно ли преимущества в производительности для практических целей?

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

Обновлен:

Существует алгоритм линейного времени, модификация для быстрой сортировки, предложенная самим изобретателем быстрой сортировки Хоаром. Я предлагаю обратиться к разделу 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 Том 3 Дональда Кнута Сортировка и поиск с.633 Прелесть этого метода в том, что массив не нужно полностью сортировать! Я думаю, что STL nth_permutation использует эту технику, вы можете обратиться к разделу заметок.