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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

  • Изначально присвоить
  • Для каждого элемента выполнить: если , присвоить .

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

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

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

Алгоритм BFPRT (линейный детерминированный)[править | править вики-текст]

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

Принцип действия[править | править вики-текст]

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

  1. Список делится на подмножества элементов, по 5 элементов в каждом (кроме последнего подмножества). Число элементов в подмножествах может варьировать от 5 до 21 и должно быть в любом случае нечётным.
  2. Каждое подмножество сортируется с помощью подходящего алгоритма сортировки.
  3. Пусть  — множество медиан, образовавшихся в подмножествах после сортировки. Рекурсивно находится медиана в  — медиана медиан. Назовем её .
    • Результирующая после 3 шага структура, имеет следующую особенность:
      • Четверть всех элементов в любом случае имеет ключ . (Подмножество множества )
      • Четверть всех элементов в любом случае имеет ключ . (Подмножество множества )
  4. Теперь список разбивается относительно медианы s на 2 подмножества и . При этом нужно сравнить с s только половину всех элементов, так как две четверти элементов уже отсортированы относительно s. В результате каждое из подмножеств и содержит максимально 3/4 всех элементов (минимально — 1/4 всех элементов).
  5. Если:
    • , то искомый элемент найден — это медиана медиан
    • , то алгоритм вызывается рекурсивно на множестве
    • в любом другом случае, алгоритм вызывается рекурсивно на множестве

Гарантированное время работы[править | править вики-текст]

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

Литература[править | править вики-текст]