Оптимальная медиана выбора медиан - 3 элемента по сравнению с 5 элементами?

Question

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

Что сбивает с толкуя - выбор блоков с 5 элементами, а не блоков с 3 элементами.С блоками из 5 элементов мне кажется, что вы выполняете операции n/4 = n/5 + n/25 + n/125 + n/625 + ... median-of-5, тогда как с блоками из 3 элементов вы выполняете операции n/2 = n/3 + n/9 + n/27 + n/81 + ... median-of-3.То, что каждое медиана-5 - это 6 сравнений, а каждое медиана-3 - это 2 сравнения, что приводит к 3*n/2 сравнениям с использованием сравнения медиана-5 и n с использованием медианы-3.

Может кто-нибудь объяснить это несоответствие, и какова может быть мотивация для использования блоков из 5 элементов?Я не знаком с обычной практикой применения этих алгоритмов, так что, возможно, есть какой-то способ, которым вы можете вырезать некоторые шаги и все же «приблизиться» к медиане, чтобы обеспечить хороший разворот, и этот подход лучше работает с блоками из 5 элементов

Answer 1

Причина в том, что при выборе блоков из 3 мы можем потерять гарантию наличия алгоритма времени O (n).

Для блоков из 5 сложность времени равна

T(n) = T (n / 5) + T (7n / 10) + O (n)

Для блоков из 3 получается

T (n) = T(n / 3) + T (2n / 3) + O (n)

Проверьте это: http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

Answer 2

Я считаю, что это связано с обеспечением "хорошего" раскола. Разделение на блоки из 5 элементов обеспечивает наихудшее разделение на 70-30. Стандартный аргумент выглядит следующим образом: из блоков n/5 по меньшей мере половина медиан>> медиана медиан, следовательно, по крайней мере половина блоков n/5 имеет как минимум 3 элемента (1/2 5)> = медиана медиан, и это дает 3n/10 разбиение, что означает, что другой раздел 7n/10 в худшем случае.

Это дает T(n) = T(n/5) + T(7n/10) + O(n).

Начиная с n/5 + 7n/10 < 1, время работы в худшем случае составляет O (n) .

Выбор трехэлементных блоков делает это таким образом: по крайней мере половина из блоков n/3 имеет как минимум 2 элемента> = медиана медиан, следовательно, это дает n/3 разбиение или 2n/3 в худшем случае случай.

Это дает T(n) = T(n/3) + T(2n/3) + O(n).

В этом случае n/3 + 2n/3 = 1, поэтому он уменьшается до O (n log n) в худшем случае.

Answer 3

Вы можете использовать блоки размером 3!Да, я так же удивлен, как и вы.В 2014 году (вы спросили в 2010 году) вышла статья, в которой показано, как это сделать.

Идея заключается в следующем: вместо того, чтобы делать median3, partition, median3, partition,..., вы делаете median3, median3, partition, median3, median3, partition, ....В статье это называется «Алгоритм повторного шага».

Таким образом, вместо:

T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)

получается:

T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)

Указанная статья - Выберите с группами из 3 или 4 тактов линейное время К. Чена и А. Думитреску (2014, arxiv) или Выберите с группами 3 или 4 (2015, домашняя страница автора).

PS: Быстрый детерминированный выбор А. Александреску (из славы языка D!), Который показывает, как реализовать вышеупомянутое еще более эффективно.