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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Анализ времени работы алгоритма)
Строка 12: Строка 12:
 
== Анализ времени работы алгоритма ==
 
== Анализ времени работы алгоритма ==
 
Пусть <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(\frac{n}{5})</tex>  
# время работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(k)</tex>, где <tex>k</tex>- количество элементов в этой части. Но <tex>k</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> k \le \frac{7n}{10}</tex>, то есть в худшем случае <tex> k = \frac{7n}{10}</tex>.  
+
# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(k)</tex>, где <tex>k</tex>- количество элементов в этой части. Но <tex>k</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> k \le \frac{7n}{10}</tex>, то есть в худшем случае <tex> k = \frac{7n}{10}</tex>.  
  
 
Тогда получаем, что   
 
Тогда получаем, что   

Версия 22:55, 7 июня 2011

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

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

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

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

Разбиваем наш массив на группы по 5 элементов(на самом деле можно разбивать и на другое нечетное количество элементов больших 5). Затем в каждой группе находим средний элемент(медиану), это можно сделать любой сортировкой. И запускаем рекурсивно этот алгоритм от медиан. Тем самым мы найдем средний элемент среди медиан, то есть медиану медиан. Эту медиану медиан выберем рассекающим элементом для поиска [math]k[/math]-го элемента. Далее разбиваем массив на две части: слева от рассекающего элемента числа меньшие него, а справа - числа больше рассекающего элемента или равные ему. И рекурсивно запускаем наш алгоритм от той части массива, в котором будет лежать [math]k[/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(k)[/math], где [math]k[/math]- количество элементов в этой части. Но [math]k[/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] k \le \frac{7n}{10}[/math], то есть в худшем случае [math] k = \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{10n}{7}) \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]

Ссылки