多數投票演算法

博耶-摩爾多數投票演算法（英語：Boyer–Moore majority vote algorithm）,中文常作多數投票演算法、摩爾投票演算法等，是一種用來尋找一組元素中占多數元素的常數空間複雜度、線性時間複雜度演算法。這一演算法由羅伯特·S·博耶（英語：Robert S. Boyer）和J·斯特羅瑟·摩爾（英語：J Strother Moore）在1981年發表^[1]，也是處理資料流（英語：streaming algorithm）的一種典型演算法。

x軸為計數器中儲存的元素，而下方y軸為輸入的元素序列。遇到相同元素或者計數器中沒有元素，計數器加入重複元素，如果遇到不同元素計數器消除一個元素。

這一演算法應用的問題原型是在集合中尋找可能存在的多數元素，這一元素在輸入的序列重複出現並占到了序列元素的一半以上；在第一遍遍歷之後應該再進行一個遍歷以統計第一次演算法遍歷的結果出現次數，確定其是否為眾數；如果一個序列中沒有占到多數的元素，那麼第一次的結果就可能是無效的隨機元素。對於資料流而言，則不太可能在亞線性空間複雜度的情況下中就尋找到出現頻率最高的元素；而對於序列，其元素的重複次數也有可能很低。^[2]

演算法

該演算法在其局部變數中儲存一個陣列元素和一個計數器，計數器初始化為 0。然後對陣列進行遍歷操作，在遍歷到元素 x 的時候：如果計數器為 0，則演算法將 x 儲存到陣列元素變數，並將計數器設定為 1。 否則，它將 x 與儲存的元素進行比較，然後遞增計數器（如果它們相等）或遞減計數器（不相等）。 在此過程結束時，如果陣列中存在占多數的元素，則它將是儲存的陣列元素變數的值。

演算法可以用虛擬碼如下表示：

• 初始化元素m並給計數器i賦初值i = 0
• 對於輸入佇列中每一個元素x：
  • 若i = 0, 那麼 m = x and i = 1
  • 否則若m = x, 那麼 i = i + 1
  • 否則 i = i − 1
• 返回 m

即便輸入序列沒有多數元素，這一演算法也會返回一個序列元素。然而如果能夠進行第二輪遍歷，檢驗返回元素的出現次數，就能判斷返回元素是否為多數元素。因此演算法需要兩次遍歷，亞線性空間演算法無法通過一次遍歷就得出輸入中是否存在多數元素。^[3]

參見

• 元素唯一性問題，判斷序列中該元素唯一
• 多數函式（英語：Majority function），返回多數元素的布林類型集合
• 多數問題 (元胞自動機)（英語：Majority problem (cellular automaton)），在細胞自動機計算模型中尋找多數元素