san9407   5년 전

unordered_map은 삽입,검색 모두 O(1)로 알고있는데

이 문제에서 퀵소트후 바이너리 서치로 풀면 O(NlogN) 아닌가요????

하지만 시간은 정렬후 바이너리 서치로 푸는게 더빠르네요

혹시 이유를 알수있을까요??

djm03178   5년 전

unordered_map은 큰 해시를 가져야 하기 때문에 관리하는 데에 큰 비용이 들고, 평균이 O(1)인 것이지 실제로는 충돌이 발생하는만큼 느려질 뿐더러, 시간복잡도를 유지하기 위해서 해시에 가하는 변화 역시 많은 비용이 듭니다.

Practical한 상황에서 시간복잡도가 실제 시간을 지배하는 것은 아니라는 좋은 예입니다.

san9407   5년 전

친절한 답변 감사합니다!

solveit   5년 전

극단적인 예지만 시간 복잡도가 T(n) = 10^500n 도 O(n)이긴 하죠.

댓글을 작성하려면 로그인해야 합니다.