الگوریتم رأی‌گیری Boyer–Moore برای پیدا کردن «عنصر اکثریت» در یک دنباله استفاده می‌شود؛ یعنی عنصری که بیش از (\lfloor n/2 \rfloor) بار در بین (n) عنصرِ ورودی تکرار شده باشد. هدف این الگوریتم این است که این عنصر را در زمان خطی (O(n)) و با استفاده از حافظه‌ی ثابت (O(1)) پیدا کند، بدون این که از ساختمان داده‌هایی مانند جدول درهم‌سازی استفاده شود.

ایده و شهود الگوریتم

شهود اصلی این است که عناصر متفاوت همدیگر را «خنثی» می‌کنند. هر زمان یک رأی برای نامزد فعلی و یک رأی برای عنصری دیگر دیده می‌شود، این دو رأی را می‌توان حذف‌شده در نظر گرفت؛ اگر عنصری واقعاً اکثریت باشد، تعداد تکرار آن بیش از مجموع بقیه عناصر است، بنابراین بعد از این خنثی‌سازی‌ها، همچنان حداقل یک نسخه از آن باقی می‌ماند و به عنوان نامزد نهایی انتخاب می‌شود.

نحوه‌ی کار گام‌به‌گام

الگوریتم در ساده‌ترین صورت دو متغیر نگه می‌دارد:

• یک candidate (نامزد فعلی)،
• یک count (تعداد رأیِ خالص برای این نامزد).

در یک گذر روی دنباله، برای هر عنصر x این قواعد اجرا می‌شود:

• اگر count برابر صفر باشد، x به عنوان candidate جدید انتخاب می‌شود و count برابر ۱ قرار می‌گیرد.
• اگر x با candidate برابر باشد، count یک واحد افزایش می‌یابد.
• اگر x با candidate برابر نباشد، count یک واحد کاهش می‌یابد.

در پایان این گذر، اگر اکثریت وجود داشته باشد، candidate همان عنصر اکثریت است. در نسخه‌ی مطمئن الگوریتم، یک گذر دوم هم انجام می‌شود تا تعداد تکرار candidate شمرده شود و بررسی شود که آیا واقعاً بیش از (n/2) بار تکرار شده است یا نه؛ اگر نه، نتیجه این است که عنصری با اکثریت مطلق وجود ندارد.

پیچیدگی و محدودیت

پیچیدگی زمانی الگوریتم خطی است؛ یک گذر برای پیدا کردن نامزد و در صورت نیاز یک گذر دیگر برای تأیید، بنابراین (O(n)). پیچیدگی فضایی نیز ثابت است، زیرا تنها چند متغیر ساده نگه داشته می‌شود و به حافظه‌ی متناسب با اندازه‌ی ورودی نیاز نیست.

محدودیت مهم این است که این الگوریتم تنها برای حالتی مناسب است که عنصر اکثریت (بیش از نصف) وجود داشته باشد؛ اگر هیچ عنصری بیش از (n/2) بار تکرار نشده باشد، مقدار candidate لزوماً «پُرتکرارترین» عنصر (مد) نیست، به همین دلیل گذر دوم برای تأیید ضروری است، اگر بخواهیم تشخیص دهیم اکثریت وجود دارد یا نه.