Поиск k-ой порядковой статистики за линейное время
| Определение: |
| -ой порядковой статистикой набора элементов линейно упорядоченного множества называется такой его элемент, который является -ым элементом набора в порядке сортировки |
Историческая справка
Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна (BFPRT-алгоритм) создан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest) и Робертом Тарьяном (Robert Tarjan) в 1973 году.
Идея алгоритма
Этот алгоритм почти ни чем не отличается от алгоритма поиска k-ой порядковой статистики, но имеет важное отличие в том, что время работы алгоритма в наихудшем случае равно , что будет доказано ниже. Главная идея алгоритма заключается в том, чтобы гарантировать хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее , где количество элементов в массиве, благодаря этому алгоритм работает за линейной время в любом случае.
Описание алгоритма
- Все элементов входного массива разбиваются на группы по пять элементов, в последней группе будет элементов. Эта группа может оказаться пустой при кратных .
- Сначала сортируется каждая группа, затем выбираем медиану в каждой из этих групп.
- Путем рекурсивного вызова шага 1 определяется медиана из множества медиан, найденных на втором шаге. Где — рассекающий элемент, — индекс рассекающего элемента. Если медиан окажется четное количество, то на место рассекающего элемента будут претендовать две медианы, переменной будет присвоено значение большей из этих двух медиан.
- Делим массив относительно рассекающего элемента . Все элементы меньшие будут находиться левее в массиве и будут иметь меньший индекс и наоборот, если элементы больше .
- Если , то возвращается значение . Иначе вызывается рекурсивно шаг 1, и выполняется поиск -го в порядке возрастания элемента в левой части массива,если , или в правой части, если .
Псевдокод
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;
Medians[1..n/5] = A[(l + 2):5:(r - 2)]; //создаем массив медиан
j = l + 2;
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)
m = i; //находим индекс элемента x в исходном массиве
if (m = k)
return A[m];
if (m > k)
select(A, k, r, m - k + 1); //делаем рекурсивный вызов от той части массива, где находится к-ый элемент
else
select(A, l, k, m);
}
Пример
На вход подается массив, разобьем элементы на группы по 5 элементов. Отсортируем элементы каждой группы и выберем медианы. Вызовемся рекурсивно от медиан.
Разобьем на группы по 5 медианы. Отсортируем элементы каждой группы и выберем медианы
Выберем медианы медиан. В итоге мы получили один элемент равный . Это и есть рассекающий элемент.
Анализ времени работы алгоритма
Чтобы проанализировать время работы алгоритма, сначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент . В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан . Таким образом, как минимум содержат по превышающих величину , за исключение группы, в которой меньше элементов и ещё одной группы, содержащей сам элемент . Таким образом получаем, что количество элементов меньших элемента , не менее , где это количество элементов в массиве. Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент , мы получим, что как минимум меньше, чем элемент . Теперь проведем анализ времени работы алгоритма. Пусть — время работы алгоритма для элементов, тогда оно не больше, чем сумма:
- времени работы на сортировку групп и разбиение по рассекающему элементу, то есть ;
- времени работы для поиска медианы медиан, то есть ;
- времени работы для поиска -го элемента в одной из двух частей массива, то есть , где — количество элементов в этой части. Но не превосходит , так как чисел, меньших рассекающего элемента, не менее — это медиан, меньших медианы медиан, плюс не менее элементов, меньших этих медиан. С другой стороны, чисел, больших рассекающего элемента, так же не менее , следовательно , то есть в худшем случае .
Тогда получаем, что
Покажем, что для всех выполняется неравенство .
Докажем по индукции:
- Очевидно, что для малых выполняется неравенство
- Тогда, по предположению индукции, и , тогда
Так как , то время работы алгоритма
Литература
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
