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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «BFPRT-Алгоритм»)
Перейти к: навигация, поиск

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

Выбор с помощью сортировки[править | править исходный текст]

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

Линейный алгоритм для нахождения минимума (максимума)[править | править исходный текст]

Очевидно, как за линейное время найти минимум (максимум) в данном массиве:

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

Алгоритм 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 до 21 и должно быть в любом случае нечётным.
  2. Каждое подмножество сортируется с помощью подходящего алгоритма сортировки.
  3. Пусть S - множество медиан, образовавшихся в подмножествах после сортировки. Рекурсивно находится медиана в S - медиана медиан. Назовем его s.
    • Результирующая после 3 шага структура, имеет следующую особенность:
      • Четверть всех элементов в любом случае имеет ключ  < s.
      • Четверть всех элементов в любом случае имеет ключ  > s.
  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

Особенности[править | править исходный текст]

При каждом рекурсивном вызове, алгоритм позволяет отбросить минимум четверть всех элементов.

Литература[править | править исходный текст]