c++ unordered_map : 어떻게 최악의 데이터를 만들까?
레퍼런스 사이트에서 보면, unordered_map의 insert나 delete나 find 함수는 평균적으로 O(1)이라고 나와 있습니다. 그런데, 최악의 경우, O(n)이라고 나와 있습니다. [관련글] 해쉬 테이블의 평균 복잡도를 분석해 봅시다. 왜 최악의 경우에 O(n)일까요? 이유는 간단합니다. Chaining 방식이 List이기 때문입니다. 그러면, 왜 최악의 경우에 선형 시간이 걸리는지는 해결이 된 셈입니다. 하나의 버킷에 좌르르륵 skew가 되어 있으면 List의 경우에는 계속 찾아야만 하니까 O(n)이 걸립니다. 그런데, 아무리 최악의 경우가 O(n)이라고 한다면, 저격 데이터를 만드는 게 굉장히 어렵다면 사실 그냥 써도 무난할 겁니다만. 생각보다 충돌이 극단적으로 일어나는 데이터를 만드는 ..
레퍼런스/분석
2019. 10. 23. 15:45
최근댓글