Поиск k-ой порядковой статистики за линейное время

Алгоритм был разработан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest), Робертом Тарьяном (Robert Tarjan).

Идея алгоритма

Этот алгоритм является модификацией алгоритма поиска k-ой порядковой статистики. Важное отличие заключается в том, что время работы алгоритма в наихудшем случае — [math]O(n)[/math], где [math]n[/math] — количество элементов в множестве. Главная идея алгоритма заключается в том, чтобы гарантировать хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее [math]\dfrac{3n}{10}[/math]. Элементов же больших опорного элемента, также не менее [math]\dfrac{3n}{10}[/math]. Благодаря этому алгоритм работает за линейное время в любом случае.

Описание алгоритма

1. Все [math]n[/math] элементов входного массива разбиваются на группы по пять элементов, в последней группе будет [math]n \bmod 5[/math] элементов. Эта группа может оказаться пустой при [math]n[/math] кратным [math]5[/math].
2. Сначала сортируется каждая группа, затем из каждой группы выбирается медиана.
3. Путем рекурсивного вызова шага определяется медиана [math]x[/math] из множества медиан (верхняя медиана в случае чётного количества), найденных на втором шаге. Найденный элемент массива [math]x[/math] используется как рассекающий (за [math]i[/math] обозначим его индекс).
4. Массив делится относительно рассекающего элемента [math]x[/math].
5. Если [math]i = k[/math], то возвращается значение [math]x[/math]. Иначе запускается рекурсивно поиск элемента в одной из частей массива: [math]k[/math]-ой статистики в левой части при [math]i \gt k[/math] или [math](k - i - 1)[/math]-ой статистики в правой части при [math]i \lt k[/math]

Пример работы алгоритма

Рассмотрим работу алгоритма на массиве из [math] 25 [/math] элементов, обозначенных кружками.

На вход подается массив, разобьем элементы на группы по 5 элементов. Отсортируем элементы каждой группы и выберем медианы. Полученные медианы групп отмечены белыми кружками.

Рекурсивно вызовемся от медиан групп и получим рассекающий элемент. На рисунке он обозначен белым кружком, внутри которого изображен символ [math] x [/math].

На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по [math] 8 [/math] элементов, всего же в массиве [math] 25 [/math], то есть мы получили хорошее (то есть соответствующее нашему утверждению) разбиение массива относительно опорного элемента, так как [math] 8 \gt [/math] [math]\dfrac{3 \cdot 25}{10}[/math]. Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и в общем случае.

Cначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент [math]x[/math]. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан [math]x[/math]. Таким образом, как минимум [math]\dfrac{n}{10}[/math] групп содержат по [math]3[/math] превышающих величину [math]x[/math], за исключение группы, в которой меньше [math]5[/math] элементов и ещё одной группы, содержащей сам элемент [math]x[/math]. Таким образом получаем, что количество элементов больших [math]x[/math], не менее [math]\dfrac{3n}{10}[/math].

Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент [math]x[/math], мы получим, что как минимум [math]\dfrac{3n}{10}[/math] меньше, чем элемент [math]x[/math]. Теперь проведем анализ времени работы алгоритма.

Анализ времени работы алгоритма

Пусть [math]T(n)[/math] — время работы алгоритма для [math]n[/math] элементов, тогда оно не больше, чем сумма:

1. времени работы на сортировку групп и разбиение по рассекающему элементу, то есть [math]Cn[/math];
2. времени работы для поиска медианы медиан, то есть [math]T[/math][math]\left(\dfrac{n}{5}\right)[/math];
3. времени работы для поиска [math]k[/math]-го элемента в одной из двух частей массива, то есть [math]T(s)[/math], где [math]s[/math] — количество элементов в этой части. Но [math]s[/math] не превосходит [math]\dfrac{7n}{10}[/math], так как чисел, меньших рассекающего элемента, не менее [math]\dfrac{3n}{10}[/math] — это [math]\dfrac{n}{10}[/math] медиан, меньших медианы медиан, плюс не менее [math]\dfrac{2n}{10}[/math] элементов, меньших этих медиан. С другой стороны, чисел, больших рассекающего элемента, так же не менее [math]\dfrac{3n}{10}[/math], следовательно [math] s \leqslant [/math] [math]\dfrac{7n}{10}[/math], то есть в худшем случае [math] s = [/math] [math]\dfrac{7n}{10}[/math].

Тогда получаем, что [math]T(n) \leqslant T[/math][math]\left(\dfrac{n}{5}\right)[/math][math] + T[/math][math]\left(\dfrac{7n}{10}\right)[/math][math] + Cn [/math]

Покажем, что для всех [math] n [/math] выполняется неравенство [math]T(n) \leqslant 10Cn [/math].

Докажем по индукции:

1. Предположим, что наше неравенство [math]T(n) \leqslant 10Cn [/math] выполняется при малых [math] n [/math], для некоторой достаточно большой константы [math] C [/math].
2. Тогда, по предположению индукции, [math]T[/math][math]\left(\dfrac{n}{5}\right)[/math] [math] \leqslant 10C [/math][math]\dfrac{n}{5}[/math] [math] = 2Cn[/math] и [math] T[/math][math]\left(\dfrac{7n}{10}\right)[/math] [math] \leqslant 10C [/math][math]\dfrac{7n}{10}[/math] [math] = 7Cn[/math], тогда

[math]T(n) \leqslant T[/math][math]\left(\dfrac{n}{5}\right)[/math] [math] + T[/math][math]\left(\dfrac{7n}{10}\right)[/math] [math] + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \leqslant 10Cn[/math]

Так как [math]T(n) \leqslant 10Cn [/math], то время работы алгоритма [math]O(n)[/math]

Источники инфомации

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ — Вильямс, 2013. — 1328 с. — ISBN 978-5-8459-1794-2
• Wikipedia — Selection algorithm