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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
1.Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n</tex> <tex> mod</tex> <tex> 5</tex> элементов.
 
1.Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n</tex> <tex> mod</tex> <tex> 5</tex> элементов.
  
2.Выбираем медиану в каждой из этих групп.
+
2.Сначала сортируется каждая группа, затем выбираем медиану в каждой из этих групп.
  
3.Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан, найденных на втором шаге. <tex>x</tex> - рассекающий элемент, <tex>i</tex> - индекс рассекающего элемента.
+
3.Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан, найденных на втором шаге. <tex>x</tex> - рассекающий элемент, <tex>i</tex> - индекс рассекающего элемента.(Если медиан окажется четное количество, то переменной <tex>x</tex> будет присвоено значение нижней медианы.)
  
 
4.Делим массив относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот,если элементы больше <tex>x</tex>.
 
4.Делим массив относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот,если элементы больше <tex>x</tex>.
Строка 19: Строка 19:
 
===Особенность алгоритма===
 
===Особенность алгоритма===
 
Как будет доказано ниже, время работы алгоритма в наихудшем случае равно <tex>O(n)</tex>. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива, так как чисел, которые меньше рассекающего элемента не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве.
 
Как будет доказано ниже, время работы алгоритма в наихудшем случае равно <tex>O(n)</tex>. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива, так как чисел, которые меньше рассекающего элемента не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве.
 +
===Пример===
 +
 
== Анализ времени работы алгоритма ==
 
== Анализ времени работы алгоритма ==
 
Пусть <tex>T(n)</tex> - время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
 
Пусть <tex>T(n)</tex> - время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:

Версия 18:24, 15 мая 2012

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

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

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

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

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

Ссылки