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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 46 промежуточных версий 3 участников)
Строка 1: Строка 1:
{{Определение
+
Алгоритм был разработан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest), Робертом Тарьяном (Robert Tarjan).
|definition=
+
==Идея алгоритма==
'''<tex>k</tex>-ой порядковой статистикой''' набора элементов линейно упорядоченного множества называется такой его элемент, который является <tex>k</tex>-ым элементом набора в порядке сортировки
+
Этот алгоритм является модификацией алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]]. Важное отличие заключается в том, что время работы алгоритма в наихудшем случае — <tex>O(n)</tex>, где <tex>n</tex> — количество элементов в множестве. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\dfrac{3n}{10}</tex>. Элементов же больших опорного элемента, также не менее <tex>\dfrac{3n}{10}</tex>. Благодаря этому алгоритм работает за линейное время в любом случае.
}}
 
== Историческая справка ==
 
  
'''Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна''' (BFPRT-алгоритм) создан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest) и Робертом Тарьяном (Robert Tarjan) в 1973 году.
 
==Особенность алгоритма==
 
Этот алгоритм почти ни чем не отличается от алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]], но имеет важное отличие в том, что время работы алгоритма в наихудшем случае равно <tex>O(n)</tex> (это будет доказано ниже). Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве, благодаря этому алгоритм работает за линейной время в любом случае.
 
 
== Описание алгоритма ==
 
== Описание алгоритма ==
#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n</tex> <tex> mod</tex> <tex> 5</tex> элементов.
+
#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n \bmod 5</tex> элементов. Эта группа может оказаться пустой при <tex>n</tex> кратным <tex>5</tex>.
#Сначала сортируется каждая группа, затем выбираем медиану в каждой из этих групп.
+
#Сначала сортируется каждая группа, затем из каждой группы выбирается медиана.
#Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан, найденных на втором шаге. <tex>x</tex> - рассекающий элемент, <tex>i</tex> - индекс рассекающего элемента.(Если медиан окажется четное количество, то переменной <tex>x</tex> будет присвоено значение верхней медианы.)
+
#Путем рекурсивного вызова шага определяется медиана <tex>x</tex> из множества медиан (верхняя медиана в случае чётного количества), найденных на втором шаге. Найденный элемент массива <tex>x</tex> используется как рассекающий (за <tex>i</tex> обозначим его индекс).
#Делим массив относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот,если элементы больше <tex>x</tex>.
+
#Массив делится относительно рассекающего элемента <tex>x</tex>.
#Если <tex>i</tex> <tex>=</tex> <tex>k</tex>, то возвращается значение <tex>x</tex>. Иначе вызывается рекурсивно шаг 1, и выполняется поиск <tex>k</tex>-го в порядке возрастания элемента в левой части массива,если <tex>i</tex> <tex><</tex> <tex>k</tex>, или в правой части, если <tex>i</tex> <tex>></tex> <tex>k</tex>.
+
#Если <tex>i = k</tex>, то возвращается значение <tex>x</tex>. Иначе запускается рекурсивно поиск элемента в одной из частей массива: <tex>k</tex>-ой статистики в левой части при <tex>i > k</tex> или <tex>(k - i - 1)</tex>-ой статистики в правой части при <tex>i < k</tex>
===Псевдокод===
+
 
    select(L,k)
+
=== Пример работы алгоритма ===
    {
+
Рассмотрим работу алгоритма на массиве из <tex> 25 </tex> элементов, обозначенных кружками.
    if (length(L) <= 10)
+
 
    {
 
        sort L
 
        return the element in the kth position            // вернем элемент, находящийся на k-ой позиции;
 
    }
 
    partition L into subsets S[i] of five elements each  // разобьем L на подмножества S[i] размером 5 по 5 элементов;
 
        (there will be n/5 subsets total).
 
    for (i = 1 to n/5) do
 
        x[i] = select(S[i],3)                            //найдем медианы S[i];
 
    M = select({x[i]}, n/10)                              // M - рассекающий элемент;
 
    partition L into L1<M, L2=M, L3>M                    // разобьем L на подмножества L1, где все элементы меньше M;
 
    if (k <= length(L1))                                  // L3, где все элементы больше M и L2 равное M;
 
        return select(L1,k)
 
    else if (k > length(L1)+length(L2))
 
        return select(L3,k-length(L1)-length(L2))
 
    else return M                                        // элемент на k-ой позиции в исходном массиве;
 
    }
 
===Пример===
 
 
На вход подается массив, разобьем элементы на группы по 5 элементов.
 
На вход подается массив, разобьем элементы на группы по 5 элементов.
Отсортируем элементы каждой группы и выберем медианы. Вызовемся рекурсивно от медиан.
+
Отсортируем элементы каждой группы и выберем медианы. Полученные медианы групп отмечены белыми кружками.
 +
 
 +
[[Файл:поиск.png| 300px]]
 +
 
 +
 
 +
Рекурсивно вызовемся от медиан групп и получим рассекающий элемент. На рисунке он обозначен белым кружком, внутри которого изображен символ <tex> x </tex>.
  
[[Файл:BFPRT2.png| 300px]]
 
  
Разобьем на группы по 5 медианы.
+
[[Файл:поиск2.png| 300px]]
Отсортируем элементы каждой группы и выберем медианы
 
  
[[Файл:BFPRT.png| 80px]]
+
На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по <tex> 8 </tex> элементов, всего же в массиве <tex> 25 </tex>, то есть мы получили хорошее (то есть соответствующее нашему утверждению) разбиение массива относительно опорного элемента, так как <tex> 8  > </tex> <tex>\dfrac{3 \cdot 25}{10}</tex>. Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и в общем случае.
  
Выберем медианы медиан. В итоге мы получили один элемент равный <tex>40</tex>. Это и есть рассекающий элемент.
+
Cначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент <tex>x</tex>. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан <tex>x</tex>. Таким образом, как минимум <tex>\dfrac{n}{10}</tex> групп содержат по <tex>3</tex> превышающих величину <tex>x</tex>, за исключение группы, в которой меньше <tex>5</tex> элементов и ещё одной группы, содержащей сам элемент <tex>x</tex>. Таким образом получаем, что количество элементов больших  <tex>x</tex>, не менее <tex>\dfrac{3n}{10}</tex>.
  
 +
Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент <tex>x</tex>, мы получим, что как минимум <tex>\dfrac{3n}{10}</tex> меньше, чем элемент <tex>x</tex>. Теперь проведем анализ времени работы алгоритма.
  
 +
[[Файл:поиск5.png| 300px]]
  
 
== Анализ времени работы алгоритма ==
 
== Анализ времени работы алгоритма ==
Пусть <tex>T(n)</tex> - время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
+
Пусть <tex>T(n)</tex> время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
 
# времени работы на сортировку групп и разбиение по рассекающему элементу, то есть <tex>Cn</tex>;
 
# времени работы на сортировку групп и разбиение по рассекающему элементу, то есть <tex>Cn</tex>;
# времени работы для поиска медианы медиан, то есть <tex>T(\frac{n}{5})</tex>;
+
# времени работы для поиска медианы медиан, то есть <tex>T</tex><tex>\left(\dfrac{n}{5}\right)</tex>;
# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(s)</tex>, где <tex>s</tex>- количество элементов в этой части. Но <tex>s</tex> не превосходит <tex>\frac{7n}{10}</tex>, так как чисел, меньших рассекающего элемента, не менее <tex>\frac{3n}{10}</tex> - это <tex>\frac{n}{10}</tex> медиан, меньших медианы медиан, плюс не менее <tex>\frac{2n}{10}</tex> элементов, меньших этих медиан. С другой стороны, чисел, больших рассекающего элемента, так же не менее <tex>\frac{3n}{10}</tex>, следовательно  <tex> s \le \frac{7n}{10}</tex>, то есть в худшем случае <tex> s = \frac{7n}{10}</tex>.  
+
# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(s)</tex>, где <tex>s</tex> количество элементов в этой части. Но <tex>s</tex> не превосходит <tex>\dfrac{7n}{10}</tex>, так как чисел, меньших рассекающего элемента, не менее <tex>\dfrac{3n}{10}</tex> это <tex>\dfrac{n}{10}</tex> медиан, меньших медианы медиан, плюс не менее <tex>\dfrac{2n}{10}</tex> элементов, меньших этих медиан. С другой стороны, чисел, больших рассекающего элемента, так же не менее <tex>\dfrac{3n}{10}</tex>, следовательно  <tex> s \leqslant </tex> <tex>\dfrac{7n}{10}</tex>, то есть в худшем случае <tex> s = </tex> <tex>\dfrac{7n}{10}</tex>.  
  
 
Тогда получаем, что   
 
Тогда получаем, что   
<tex>T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn </tex>
+
<tex>T(n) \leqslant T</tex><tex>\left(\dfrac{n}{5}\right)</tex><tex> + T</tex><tex>\left(\dfrac{7n}{10}\right)</tex><tex> + Cn </tex>
  
Покажем, что для всех <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </tex>.
+
Покажем, что для всех <tex> n </tex> выполняется неравенство <tex>T(n) \leqslant 10Cn </tex>.
  
 
Докажем по индукции:
 
Докажем по индукции:
# Очевидно, что для малых <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </tex>  
+
# Предположим, что наше неравенство <tex>T(n) \leqslant 10Cn </tex> выполняется при малых <tex> n </tex>, для некоторой достаточно большой константы <tex> C </tex>.
# Тогда, по предположению индукции, <tex>T(\frac{n}{5}) \le 10C(\frac{n}{5}) = 2Cn</tex> и <tex> T(\frac{7n}{10}) \le 10C(\frac{7n}{10}) = 7Cn</tex>, тогда
+
# Тогда, по предположению индукции, <tex>T</tex><tex>\left(\dfrac{n}{5}\right)</tex> <tex> \leqslant 10C </tex><tex>\dfrac{n}{5}</tex> <tex> = 2Cn</tex> и <tex> T</tex><tex>\left(\dfrac{7n}{10}\right)</tex> <tex> \leqslant 10C </tex><tex>\dfrac{7n}{10}</tex> <tex> = 7Cn</tex>, тогда
<tex>T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le 10Cn</tex>
+
<tex>T(n) \leqslant T</tex><tex>\left(\dfrac{n}{5}\right)</tex> <tex> + T</tex><tex>\left(\dfrac{7n}{10}\right)</tex> <tex> + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \leqslant 10Cn</tex>
  
Так как <tex>T(n) \le 10Cn </tex>, то время работы алгоритма <tex>O(n)</tex>
+
Так как <tex>T(n) \leqslant 10Cn </tex>, то время работы алгоритма <tex>O(n)</tex>
  
== Ссылки ==
+
==Источники инфомации==
* [http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Selection algorithm — Wikipedia]
+
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. '''Алгоритмы: построение и анализ''' {{---}} Вильямс, 2013. {{---}} 1328 с. {{---}} ISBN 978-5-8459-1794-2
 +
* [http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Wikipedia — Selection algorithm]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
 +
[[Категория: Другие сортировки]]

Версия 18:52, 5 июня 2015

Алгоритм был разработан Мануэлем Блюмом (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 элементов. Отсортируем элементы каждой группы и выберем медианы. Полученные медианы групп отмечены белыми кружками.

Поиск.png


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


Поиск2.png

На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по [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]. Теперь проведем анализ времени работы алгоритма.

Поиск5.png

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

Пусть [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