Алгоритм большинства голосов Бойера — Мура

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

Состояние алгоритма после каждого входящего символа. Входные символы представлены вдоль нижней части фигуры. Сохраненные элементы и их счет показаны на графике.

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

Описание

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

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

• алг (a₁, a₂,... a_n):
  • counter ← 0
  • для всех i от 1 до n:
    • если counter = 0, то:
      • majority_element ← a_i
      • counter ← 1
    • иначе если a_i = majority_element:
      • counter ← counter+1
    • иначе:
      • counter ← counter-1
  • вывод majority_element

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