Tổng quan
Thuật toán Bầu Chọn Đa Số Boyer–Moore tìm giá trị chiếm hơn một nửa mảng chỉ bằng một bộ đếm và một biến ứng viên — không bảng băm, không sắp xếp, không mảng phụ.
Ý tưởng là triệt tiêu. Hãy hình dung ghép mỗi lần xuất hiện của giá trị đa số với một lần xuất hiện của giá trị khác rồi xóa cả hai. Vì đa số vượt hẳn một nửa, nó không thể bị triệt tiêu hết — thứ còn sống tới cuối chắc chắn là nó. Bộ đếm chính là phép ghép cặp đó, thực hiện trong một lượt mà không bao giờ phải lưu các cặp.
Bầu Chọn Đa Số Boyer–Moore hoạt động thế nào?
- Bắt đầu với chưa có ứng viên nào và bộ đếm bằng 0.
- Với mỗi phần tử: nếu bộ đếm bằng 0, nhận phần tử này làm ứng viên mới và đặt bộ đếm bằng 1.
- Nếu không, khi phần tử bằng ứng viên thì tăng bộ đếm.
- Nếu khác, giảm bộ đếm — đây là một lần triệt tiêu giữa ứng viên và một phần tử không phải ứng viên.
- Sau lượt quét, ứng viên là khả năng duy nhất cho phần tử đa số. Chạy lượt thứ hai đếm số lần nó xuất hiện để xác nhận nó thật sự vượt quá n/2.
Khi nào nên dùng?
- Đồng thuận và chịu lỗi: tìm giá trị mà đa số bản sao hoặc cảm biến đồng ý, với bộ nhớ hằng số.
- Xử lý luồng dữ liệu quá lớn để lưu trữ — thuật toán không bao giờ giữ quá một giá trị.
- Mạch bầu chọn trong hệ nhúng và phần cứng, nơi bảng băm hoàn toàn không phải một lựa chọn.
- Mở rộng để tìm mọi phần tử xuất hiện quá n/k lần, bằng cách giữ k − 1 ứng viên và bộ đếm thay vì một.
Phân tích độ phức tạp
Thời gian là O(n): một lượt tìm ứng viên và một lượt xác nhận, cả hai đều tuyến tính. Bộ nhớ là O(1) — hai biến bất kể mảng lớn cỡ nào, và đó là điểm phân biệt nó với lời giải hiển nhiên bằng bảng băm tốn O(n) bộ nhớ. Lượt xác nhận không phải tùy chọn: trên mảng không có phần tử đa số, lượt đầu vẫn cho ra một ứng viên nào đó, và báo cáo nó mà không kiểm tra là sai.
Câu hỏi thường gặp
Vì sao lượt quét thứ hai là bắt buộc?
Vì thuật toán chỉ đảm bảo 'nếu tồn tại phần tử đa số thì đó là ứng viên này'. Nó không nói gì khi không tồn tại phần tử đa số — với [1, 2, 3] nó sẽ tự tin trả về 3. Chỉ có phép đếm mới phân biệt được hai tình huống.
'Đa số' có nghĩa là xuất hiện nhiều nhất không?
Không, và khác biệt này quan trọng. Đa số nghĩa là xuất hiện nhiều hơn hẳn n/2 lần. Giá trị xuất hiện nhiều nhất trong [1, 1, 2, 2, 3] là 1 hoặc 2 với hai lần mỗi loại, nhưng không cái nào là đa số, và thuật toán này không được thiết kế để tìm giá trị xuất hiện nhiều nhất.
Vì sao một ứng viên sai không bao giờ sống sót được?
Mỗi lần giảm bộ đếm ghép một phần tử đa số với một phần tử không phải đa số. Tổng số phần tử không phải đa số ít hơn n/2, nên chúng hết trước, và bộ đếm không thể về 0 ở đoạn cuối toàn giá trị đa số.