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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
#Делим массив относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</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</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>.
===Псевдокод===
 
    select(A, l, r, k) {
 
                                                   
 
        if (r - l + 1 <= 5) {
 
            sort(A[l..r]);                            //если элементов не больше 5, сортируем их и возвращаем к-ый элемент       
 
            return A[k];
 
        }
 
                                                     
 
        for i = l..(r - 4)
 
            sort(A[i..i + 4];                        //сортируем каждую группу
 
            i += 5;
 
                                                     
 
        n = r - l + 1;
 
        j = l + 2; 
 
        Medians[1..n / 5];                            //создаем массив медиан
 
        for i = 1..n / 5
 
            Medians[i] = A[j];
 
            j += 5;
 
                                                   
 
        x = select(Medians, 1, n/5, n/10);          //x - рассекающий элемент 
 
                                                                                                                             
 
        A = share(A, l, r, x);                      //делим массив относительно элемента x
 
                                                   
 
        for i = l to r
 
            if (A[i] == x)                          //находим индекс элемента x в исходном  массиве
 
                m = i;                             
 
        if (m = k)
 
            return A[m];
 
                                                   
 
        if (m > k)
 
            select(A, k, r, m - k + 1);            //делаем рекурсивный вызов от той части массива, где находится к-ый элемент 
 
        else
 
            select(A, l, k, m);
 
    }
 
  
===Пример===
+
=== Пример работы алгоритма ===
 +
Рассмотрим работу алгоритма на массиве из <tex> 25 </tex> элементов, обозначенных кружками.
 +
 
 
На вход подается массив, разобьем элементы на группы по 5 элементов.
 
На вход подается массив, разобьем элементы на группы по 5 элементов.
Отсортируем элементы каждой группы и выберем медианы. Вызовемся рекурсивно от медиан.
+
Отсортируем элементы каждой группы и выберем медианы. Полученные медианы групп отмечены белыми кружками.
  
[[Файл:BFPRT2.png| 300px]]
+
[[Файл:поиск.png| 300px]]
  
Разобьем на группы по 5 медианы.
+
Рекурсивно вызовемся от медиан групп и получим рассекающий элемент. На рисунке он обозначен белым кружком, внутри которого изображен символ <tex> x </tex>.
Отсортируем элементы каждой группы и выберем медианы
 
  
[[Файл:BFPRT.png| 80px]]
+
[[Файл:поиск2.png| 300px]]
  
Выберем медианы медиан. В итоге мы получили один элемент равный <tex>40</tex>. Это и есть рассекающий элемент.
+
Проведем анализ рассекающего элемента. На рисунке обозначена заштрихованная область. В эту область попали все элементы, которые точно меньше рассекающего элемента. Всего элементов во входном массиве <tex> 25 </tex>, элементов меньших рассекающего <tex> 8 </tex>. В итоге мы получили, что количество элементов, которые меньше опорного элемента более <tex>\frac{3n}{10}</tex>.  
  
 +
[[Файл:поиск3.png| 300px]]
  
  

Версия 21:40, 9 июня 2012

Определение:
[math]k[/math]-ой порядковой статистикой набора элементов линейно упорядоченного множества называется такой его элемент, который является [math]k[/math]-ым элементом набора в порядке сортировки

Историческая справка

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

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

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

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

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

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

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

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

Поиск.png

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

Поиск2.png

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

Поиск3.png


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

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

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

  1. времени работы на сортировку групп и разбиение по рассекающему элементу, то есть [math]Cn[/math];
  2. времени работы для поиска медианы медиан, то есть [math]T(\frac{n}{5})[/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 \le \frac{7n}{10}[/math], то есть в худшем случае [math] s = \frac{7n}{10}[/math].

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

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

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

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

[math]T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le 10Cn[/math]

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

Литература

  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ

Ссылки