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

2017-11-06T01:08:53Z

93.85.57.46: итерацией

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

== Выбор с помощью сортировки ==
Задачу выбора можно свести к [[Алгоритм сортировки|сортировке]]. В самом деле, можно упорядочить массив, а затем взять нужный по счету элемент. Это эффективно в том случае, когда выбор нужно делать многократно: тогда можно отсортировать массив за O(''n'' log ''n'') и затем выбирать из него элементы. Однако если выбор нужно произвести однократно, данный алгоритм может оказаться неоправданно долгим.

== Линейный алгоритм для нахождения минимума (максимума) ==
Очевидно, как за линейное время найти минимум (максимум) в данном массиве:

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

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

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

== Алгоритм BFPRT (линейный детерминированный) ==
'''BFPRT-Алгоритм''' позволяет найти ''k''-ю порядковую статистику гарантированно за O(''n''). Назван в честь своих изобретателей: Manual '''B'''lum, Robert W. '''F'''loyd, Vaughan R. '''P'''ratt, Ronald L. '''R'''ivest и Robert Endre '''T'''arjan. Используется при достаточно длинном списке элементов, свыше 800 элементов.

=== Принцип действия ===
Ввод: число <math>i</math>, обозначающее <math>i</math>-й элемент.

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

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

== Литература ==
* {{книга
|автор = Volker Heun
|заглавие = Основные Алгоритмы
|оригинал = Grundlegende Algorithmen
|ссылка =
|издание = 1-е изд
|место = Мюнхен
|издательство = Vieweg Verlag
|год = 2000
|страницы = 86
|isbn = 3-528-03140-9
}}
* [http://people.csail.mit.edu/rivest/BlumFloydPrattRivestTarjan-TimeBoundsForSelection.pdf 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] {{ref-en}}

[[Категория:Алгоритмы поиска]]

Поле цифровой дидактики - Вклад [ru]

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