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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 49: Строка 49:
 
Так как <tex>T(n) \leqslant 10Cn </tex>, то время работы алгоритма <tex>O(n)</tex>
 
Так как <tex>T(n) \leqslant 10Cn </tex>, то время работы алгоритма <tex>O(n)</tex>
  
==Литература==
+
==Источники инфомации==
 
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. '''Алгоритмы: построение и анализ''' {{---}} Вильямс, 2013. {{---}} 1328 с. {{---}} ISBN 978-5-8459-1794-2
 
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. '''Алгоритмы: построение и анализ''' {{---}} Вильямс, 2013. {{---}} 1328 с. {{---}} ISBN 978-5-8459-1794-2
 
* [http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Selection algorithm — Wikipedia]
 
* [http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Selection algorithm — Wikipedia]

Версия 00:53, 4 июня 2015

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

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

Поиск.png


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


Поиск2.png

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

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

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

Поиск5.png

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

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

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

Тогда получаем, что [math]T(n) \leqslant T([/math][math]\frac{n}{5}[/math][math]) + T([/math][math]\frac{7n}{10}[/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]\frac{n}{5}[/math][math]) \leqslant 10C [/math][math]\frac{n}{5}[/math][math] = 2Cn[/math] и [math] T([/math][math]\frac{7n}{10}[/math][math]) \leqslant 10C [/math][math]\frac{7n}{10}[/math][math] = 7Cn[/math], тогда

[math]T(n) \leqslant T([/math][math]\frac{n}{5}[/math][math]) + T([/math][math]\frac{7n}{10}[/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
  • Selection algorithm — Wikipedia