Thuật toán để kiểm tra nếu tập A là tập hợp con của tập B nhanh hơn thời gian tuyến tính

Question

Có một thuật toán (tốt nhất là thời gian không đổi) để kiểm tra xem tập A có phải là tập con của tập B không?

Tạo cấu trúc dữ liệu để tạo thuận lợi cho vấn đề này không được tính vào thời gian chạy.

Answer 1

Vâng, bạn sẽ phải xem từng phần tử của A, vì vậy phải có ít nhất thời gian tuyến tính ở kích thước A.

Thuật toán O(A+B) rất dễ sử dụng hashtables (lưu trữ các phần tử của B trong một Hashtable, sau đó tra từng phần tử A). Tôi không nghĩ rằng bạn có thể làm tốt hơn trừ khi bạn biết một số cấu trúc tạm ứng cho B. Ví dụ: nếu B được lưu trữ theo thứ tự sắp xếp, bạn có thể thực hiện O(A log B) bằng tìm kiếm nhị phân.

Answer 2

Bạn có thể sử dụng bộ lọc hoa (http://en.wikipedia.org/wiki/Bloom_filter). Tuy nhiên có thể có những sai lầm tích cực, có thể được giải quyết bằng phương pháp được đề cập bởi Keith ở trên (nhưng lưu ý rằng độ phức tạp của trường hợp băm nhỏ nhất là KHÔNG O (n), nhưng bạn có thể làm O (nlogn)

1. Xem nếu A là một tập hợp con của B theo Bloom lọc
2. Nếu có, thì làm một kiểm tra kỹ lưỡng

Answer 3

Nếu bạn có một danh sách các chữ cái chung nhỏ nhất và cặp chữ cái trong bộ chuỗi, bạn có thể lưu trữ các bộ của bạn được sắp xếp với các chữ cái và cặp thư ít phổ biến nhất của chúng và tối đa hóa cơ hội tung ra các kết quả phủ định nhanh nhất có thể. 10 Nó không rõ ràng với tôi như thế nào tốt này sẽ kết hợp với một bộ lọc nở, Có lẽ một bảng băm sẽ làm vì không có rất nhiều digrams và chữ cái.

Nếu bạn có một số thông tin về kích thước tối đa các tập con hoặc thậm chí kích thước chung, bạn có thể xử lý trước dữ liệu tương tự bằng cách đặt tất cả các tập hợp con của một kích thước nhất định vào bộ lọc nở như đã đề cập.

Bạn cũng có thể kết hợp cả hai loại này.