25.03.2022

Алгоритм большинства голосов Бойера — Мура — это алгоритм для нахождения преобладающего элемента последовательности. Преобладающим элементом последовательности длины n называется такой элемент этой последовательности, который встречается в ней более чем n/2 раз. Сложность данного алгоритма O(n), а требуемая дополнительная память — O(1).

Алгоритм назван в честь Р. Бойера и Джей Мура, опубликовавших его в 1981 году.

Описание

Алгоритм требует введения двух дополнительных переменных: первая будет содержать элемент последовательности, который является наиболее подходящим на роль преобладающего элемента из уже рассмотренных, а вторая является счётчиком и изначально равна нулю. Алгоритм состоит из единственного прохода по рассматриваемой последовательности. На каждом шаге выполняются следующие действия: если текущее значение переменной-счётчика равно нулю, то данный элемент последовательности записывается в первую переменную, а счётчик становится равен 1. Если же значение счётчика отлично от нуля, то текущий элемент последовательности сравнивается со значением, записанным в первую переменную. Если они совпадают, то счётчик увеличивается на 1, иначе — уменьшается на 1.

Псевдокод алгоритма:

  • алг (a1, a2,... an):
    • counter ← 0
    • для всех i от 1 до n:
      • если counter = 0, то:
        • majority_element ← ai
        • counter ← 1
      • иначе если ai = majority_element:
        • counter ← counter+1
      • иначе:
        • counter ← counter-1
    • вывод majority_element

После рассмотрения всех элементов в первой переменной будет содержаться преобладающий элемент последовательности, если таковой существует. Однако если такового элемента в последовательности нет, то первая переменная всё равно будет содержать некоторый элемент последовательности . Поэтому, если уверенности в существовании преобладающего элемента нет, то следует выполнить дополнительный проход по массиву, дабы убедиться, что найденный элемент в массиве встречается более чем n/2 раз. Если в результате второго прохода окажется, что элемент встречается не более n/2 раз, то последовательность преобладающего элемента не содержит.


Имя:*
E-Mail:
Комментарий: