WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

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

Литература

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

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

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии