chatterboy   1년 전

lower_bound와 map을 이용한 두 가지 방법으로 구현을 했습니다. 구현을 할 땐 당연히 lower_bound가 더 빠를 것이라고 생각했는데 공식 데이터에서

30배 이상 차이가 생기더라구요.. 매번 w를 deque나 map에서 찾을 때는 O(wlgn)로 생각했는데 어디서 이런 차이가 생기는 것인가요? lower_bound를

잘못 사용하고 있는건가요?

yukariko   1년 전

dq의 erase연산이 front와 back 에서만 O(1)이고 나머지는 선형으로 동작하기 때문에 느린것 같습니다.

chatterboy   1년 전

yukariko

크 그렇군요. 감사합니다.

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