다중 세트, 맵 및 해시 맵 복잡성

다중 세트, 맵 및 해시 맵 복잡성

---

다음과 같은 경우 STL 멀티 셋, 맵 및 해시 맵 클래스의 Big O 표기법의 복잡성을 알고 싶습니다.

• 항목 삽입
• 항목 액세스
• 항목 검색
• 항목 비교

---

맵, 세트, ​​멀티 맵 및 멀티 세트

이들은 균형 잡힌 이진 검색 트리 유형 인 레드-블랙 트리를 사용하여 구현됩니다 . 다음과 같은 점근 적 실행 시간이 있습니다.

삽입 : O (log n)
조회 : O (log n)
삭제 : O (log n)

hash_map, hash_set, hash_multimap 및 hash_multiset

이것들은 해시 테이블을 사용하여 구현됩니다 . 다음과 같은 런타임이 있습니다.

삽입 : O (1) 예상, O (n) 최악의 경우
조회 : O (1) 예상, O (n) 최악의 경우
삭제 : O (1) 예상, O (n) 최악의 경우

적절한 해시 함수를 사용하면 최악의 동작을 거의 볼 수 없지만 명심해야 할 사항입니다. 이에 대한 예는 Crosby 및 Wallach의 알고리즘 복잡성 공격 을 통한 서비스 거부를 참조하십시오 .

---

이 정보는 SGI STL 문서에서 찾을 수 있습니다. http://www.sgi.com/tech/stl/

기본적으로 다중 집합과 맵은 모두 정렬 된 이진 트리이므로 N 항목 중 1 개를 삽입 / 찾는 데 O (log N)가 필요합니다. Sorted Assoc을 참조하십시오. 문서의 컨테이너.

분명히 Hashmap의 큰 장점은 항목을 삽입하고 찾는 데 O (1)입니다.

발견 후 액세스하는 것은 모든 구조에 대해 O (1)입니다. 비교, 그게 무슨 뜻이야? 결국 O (1)처럼 들립니다.

참고 URL : https://stackoverflow.com/questions/222658/multiset-map-and-hash-map-complexity