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

В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n).

Выбор с помощью сортировки

Задачу выбора можно свести к сортировке. Можно упорядочить массив, а затем взять нужный по счёту элемент. Это эффективно в том случае, когда выбор нужно делать многократно: тогда можно отсортировать массив за O(n log n) и затем выбирать из него элементы. Однако если выбор нужно произвести однократно, этот алгоритм может оказаться неоправданно долгим.

Линейный алгоритм для нахождения минимума (максимума)

Способ за линейное время найти минимум (максимум) в массиве:

• Изначально присвоить $min=a[0];$
• Для каждого элемента $a[i]$ выполнить: если $min>a[i]$, присвоить $min=a[i]$.

Линейный в среднем алгоритм для нахождения k-й порядковой статистики

Существует алгоритм для нахождения k-й порядковой статистики, основанный на алгоритме быстрой сортировки и работающий за O(n) в среднем.

Идея алгоритма заключается в том, что массив разбивается на две части относительно случайно (равновероятно) выбранного элемента — в одну часть попадают элементы, меньшие, чем выбранный, в другую — остальные (эта операция выполняется за $O(n)$, по её окончании выбранный элемент находится в позиции $j$). Если в первой части оказалось ровно $k-1$ элементов ($j=k$), то выбранный элемент является искомым, если $j>k$, то алгоритм выполняется рекурсивно для первой части массива, иначе — для второй (в последнем случае для следующей итерации от $k$ отнимается $j$). Рекурсивные вызовы приводят к экспоненциально уменьшающемуся с каждой итерацией размеру обрабатываемого массива, и по этой причине время выполнения алгоритма составляет $O(n)$.

Алгоритм BFPRT (линейный детерминированный)

BFPRT-Алгоритм позволяет найти k-ю порядковую статистику гарантированно за O(n). Назван в честь своих изобретателей: Manual Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest и Robert Endre Tarjan. Используется при достаточно длинном списке элементов, свыше 800 элементов.

Принцип действия

Ввод: число $i$, обозначающее $i$-й элемент.

1. Список делится на подмножества элементов, по 5 элементов в каждом (кроме последнего подмножества). Число элементов в подмножествах может превышать 5 и должно быть в любом случае нечётным. Однако если делить список на подмножества из 3 элементов, время работы не будет линейным.
2. Каждое подмножество сортируется с помощью подходящего алгоритма сортировки.
3. Пусть $S$ — множество медиан, образовавшихся в подмножествах после сортировки. Рекурсивно находится медиана в $S$ — медиана медиан. Назовем её $s$.
   • Результирующая после 3 шага структура, имеет следующую особенность:
     • Четверть всех элементов в любом случае имеет ключ $<s$. (Подмножество множества $S_{1}$)
     • Четверть всех элементов в любом случае имеет ключ $>s$. (Подмножество множества $S_{2}$)
4. Теперь список разбивается относительно медианы s на 2 подмножества $S_{1}$ и $S_{2}$. При этом нужно сравнить с s только половину всех элементов, так как две четверти элементов уже отсортированы относительно s. В результате каждое из подмножеств $S_{1}$ и $S_{2}$ содержит максимально 3/4 всех элементов (минимально — 1/4 всех элементов).
5. Если:
   • $i=|S_{1}|+1$, то искомый элемент найден — это медиана медиан $s$
   • $i\leq |S_{1}|$, то алгоритм вызывается рекурсивно на множестве $S_{1}$
   • в любом другом случае, алгоритм вызывается рекурсивно на множестве $S_{2}$

Гарантированное время работы

При каждом рекурсивном вызове, алгоритм позволяет отбросить минимум четверть всех элементов. Это обеспечивает верхнюю оценку на гарантированное линейное время работы для детерминированного алгоритма, так как оно выражается рекуррентным соотношением $T(n)=O(n)+T\left({\frac {n}{5}}\right)+T\left({{\frac {7}{10}}n}\right)$. В общем случае, если подмножества имеют размер $2k+1$, время работы выражается как $T(n)=O(n)+T\left({\frac {n}{2k+1}}\right)+T\left({{\frac {3k+1}{4k+2}}n}\right)$.

Литература

• Volker Heun. Основные Алгоритмы = Grundlegende Algorithmen. — 1-е изд. — Мюнхен: Vieweg Verlag, 2000. — С. 86. — ISBN 3-528-03140-9.
• Time Bounds for Selection by Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Journal of Computer and System Sciences 7,4 August 1973, 448—460  (англ.)