「majority-vote」の記事

Boyer–Moore の過半数投票アルゴリズム：候補 1 つとカウンタで過半数を探す、2 回目の走査が要る理由

Boyer と Moore が 1980 年に考案した MJRTY は、候補 1 つとカウンタ 1 つで過半数要素の候補を選びます。動作規則、正しさの論証、過半数がないときの誤答と 2 回目の走査を原論文に沿って整理します。