Алгоритм большинства голосов Бойера — Мура — это алгоритм для нахождения преобладающего элемента последовательности. Преобладающим элементом последовательности длины n называется такой элемент этой последовательности, который встречается в ней более чем n/2 раз. Сложность данного алгоритма O(n), а требуемая дополнительная память — O(1).
Алгоритм назван в честь Р.Бойера (англ.) и Дж. Мура (англ.), опубликовавших его в 1981 году.[1]
Описание
Алгоритм требует введения двух дополнительных переменных: первая будет содержать элемент последовательности, который является наиболее подходящим на роль преобладающего элемента из уже рассмотренных, а вторая является счётчиком и изначально равна нулю. Алгоритм состоит из единственного прохода по рассматриваемой последовательности. На каждом шаге выполняются следующие действия: если текущее значение переменной-счётчика равно нулю, то данный элемент последовательности записывается в первую переменную, а счётчик становится равен 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
- если counter = 0, то:
- вывод majority_element
После рассмотрения всех элементов в первой переменной будет содержаться преобладающий элемент последовательности, если таковой существует. Однако если такового элемента в последовательности нет, то первая переменная всё равно будет содержать некоторый элемент последовательности . Поэтому, если уверенности в существовании преобладающего элемента нет, то следует выполнить дополнительный проход по массиву, дабы убедиться, что найденный элемент в массиве встречается более чем n/2 раз. Если в результате второго прохода окажется, что элемент встречается не более n/2 раз, то последовательность преобладающего элемента не содержит.[2]
Примечания
- ↑ Boyer, R. S. & Moore, J S. (1991), "MJRTY - A Fast Majority Vote Algorithm", in Boyer, R. S., Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers, с. 105–117, doi:10.1007/978-94-011-3488-0_5, <http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA131702>. Originally published as a technical report in 1981.
- ↑ Cormode, Graham & Hadjieleftheriou, Marios (October 2009), "Finding the frequent items in streams of data", Communications of the ACM Т. 52 (10): 97, DOI 10.1145/1562764.1562789.
 |
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .