두 개의 std::set이 주어지면 두 세트를 동시에 반복하고 요소를 비교하여 선형 복잡성을 초래할 수 있습니다. 요소가 임의의 순서로 저장 될 수 있기 때문에 이것은 std::unordered_set에 대해 작동하지 않습니다. 따라서 std::unordered_set의 경우 얼마나 비쌉니까 a == b입니까? operator== 및 operator!=의비 정렬 된 두 세트를 비교하는 것이 얼마나 비쌉니까?
복잡성 : 평균 경우
선형의 복잡성. N 여기서 N은 컨테이너의 크기입니다. 표준 §23.2.5에서
더 자세한 점 11 :
unordered_set를 들어
및 unordered_map의 복잡성 operator== (즉,에 의해 반환 된 조건에 value_type의 == 운영자 호출의 수, key_equal() 및 hash_function() 의해 반환 심부름)에 N가 a.size() 인 최악의 경우에서 2 개의 평균 경우와 N N에 비례한다.
매우 최악의 경우는 O (n²)입니다.
그러나 순서가 지정되지 않은 세트는 사실 해시에 의해 정렬됩니다. 따라서 해시를 비교할 수 있습니다 (세트가 동일하지 않을 경우). 동일한 해시 (선형)가 뒤에 동일한 해시 값을 가진 실제 값 (O (n²))을 가지고 있는지 확인할 수 있습니다.
가장 좋은 경우 O (n)입니다.
일반적으로 해시 함수가 "양호"(다른 개체 -> 항상 다른 해시) 인 경우 O (n), 해시 함수가 "나쁜"인 경우 O (n²) 해시 값)
"해시 함수가 좋다 (다른 객체 -> 항상 다른 해시)"-> 다른 해시는 끔찍한 해시 알고리즘 (예 : 복제 된 8 * 128 비트 해시 값을 반환하여 최대 128 자의 해시 문자열)에서도 참일 수 있습니다. 문자열)하지만 버킷의 수에 mod를 넣으면 그 결과는 추악합니다. 충돌 회피를 용이하게하는 입력에 대한 특별한 통찰력이 없다면 좋은 해시 함수 포스트 modding은 일반적으로 사용되지 않은 버킷에 대한 사용률의 충돌로 인해 O (n) 평균을 발생시킵니다. –
@TonyDelroy : 이것을 지적 해 주셔서 감사합니다! "좋은 해시"는 "다른 값"을 반환 할뿐만 아니라 버킷에 대한 "잘 분산 된"존중을 반환해야합니다 (해시 공간은 버킷에 대해 균일하고 우선적이어야하며 사용자가 언급 한 효과를 최소화해야합니다) –
해쉬 테이블을 사용하는 등 효율적인 방법으로 집합 멤버를 확인할 수 있습니까? – Thilo
C++ 표준의 명확하고 이해하기 쉽고 이해하기 쉬운 단어로 : "정렬되지 않은 두 개의 컨테이너 'a'와'b'는'a.size() == b.size()'와 동등한 비교를합니다. a.equal_range (Ea1)로부터 얻어진 등가 키 그룹 ([Ea1, Ea2])에는'b.equal_range (Ea1)'에서 얻어진 등가 키 그룹'[Eb1, Eb2] distance (Ea1, Ea2) == distance (Eb1, Eb2)'와 is_permutation (Ea1, Ea2, Eb1)은'true'를 반환합니다 .' unordered_set'의 경우 ...'operator =='...의 복잡성은 다음과 같습니다. N이''a.size() '인 경우 평균치의 경우'N '과 최악의 경우'N^2'에 비례합니다. –