znxenter   1년 전

map이 내부적으로 레드블랙트리라고 알고있어서

바이너리 서치 트리의 형태를 가지기 때문에 map을 사용하면

stl sort를 하고 binary search를 하는 것과 같은 수행시간을 가질 것이라 생각해서

아래와 같이 코드를 짜고 돌려보았는데

시간 초과가 뜨네요 ㅠ

그냥 sort하고 binary search해서 해결하긴 했는데

왜 map이 더 느린걸까요? stl이 가지고 있는 기본적인 오버헤드 때문일까요?

dotorya   1년 전

RB tree라고 해도 binary search보단 연산이 많을 것 같습니다. 트리 구조 유지를 위한 회전이라거나..

한번 정렬해두면 끝인 binary search에 비해 계속 삽입과정을 반복하게 되어 그런 것 같습니다.


제 경험상으로는 map이 직접 구현한 binary search보다 3~4배정도 느린것 같네요.

100만 NlgN이라면 아슬아슬하지 않을까 싶습니다.

znxenter   11달 전

음음 그렇군요 ㅋㅋ

감사합니다^^

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