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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Алгоритм был разработан Мануэлем Блюмом (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