algorithm - powerset
선형 세트보다 빠른 시간에 세트 A가 세트 B의 부분 집합 일지 어떨지를 조사하는 알고리즘 (2)
집합 A가 집합 B의 부분 집합인지 확인하는 알고리즘 (가급적 일정 시간)이 있습니까?
이 문제를 해결하기 위해 데이터 구조를 생성하는 것은 런타임에 포함되지 않습니다.
음, A 각 요소를 살펴야하므로 A 의 크기에서 최소한 선형 시간이어야합니다.
해시 테이블 (해시 테이블에 B 요소를 저장 한 다음 A 각 요소를 찾아보기)을 사용하여 O(A+B) 알고리즘을 쉽게 사용할 수 있습니다. 나는 당신이 B 위한 진보 된 구조를 알지 못한다면 더 잘할 수 있다고 생각하지 않는다. 예를 들어 B 가 정렬 된 순서로 저장되어 있으면 이진 검색을 사용하여 O(A log B) 를 수행 할 수 있습니다.
문자열 집합에 가장 일반적인 문자 및 문자 쌍의 목록이있는 경우 가장 일반적인 문자 및 문자 쌍으로 정렬 된 집합을 저장하고 가능한 한 빨리 부정적인 일치를 버릴 가능성을 극대화 할 수 있습니다. 이것이 블룸 필터와 얼마나 잘 결합되는지는 분명하지 않습니다. 아마 많은 digram과 글자가 없으므로 해시 테이블이 가능할 것입니다.
하위 집합의 최대 크기 또는 공통 크기에 대한 정보가있는 경우 주어진 크기의 모든 하위 집합을 언급 된 블룸 필터에 넣어 데이터를 미리 처리 할 수 있습니다.
이 두 가지를 조합하여 수행 할 수도 있습니다.
