skydreamer21   2년 전

이론적으로 해시를 쓰는 거랑 이분탐색을 쓰는 거랑 어떤 방법이 더 빠를까요?

Hash의 contains 가 O(1)이고 이분탐색은 찾을때마다 O(logn) 이라 제 생각엔 Hash 가 아주 조금 더 빠를 것 같은데

실제로 구현해보면 이분탐색이 아주 미세하게(16ms) 빠르게 나오네요. 물론 차이가 누가 빠르다 할정도로 유의미한건 아니지만 

이론적으로는 위의 생각이 맞는지 궁금합니다.. (저는 java11로 구현했습니다.)

djm03178   2년 전

logn은 굉장히 작은 수입니다. 특히 한 번 정렬해놓고 그 안에서 이분탐색을 하는 것은 상수도 매우 작은 편에 속합니다. 반면의 해시의 경우 평균이 O(1)인 것이기 때문에 최악의 경우에는 O(n)이 될 수도 있고, 그렇지 않더라도 일반적으로 해시 충돌 및 리해싱 등이 자주 일어나기 때문에 O(1)이라고 해도 작지는 않습니다. 딱 둘을 이론적으로 비교하고 어떻다고 말하기는 어려워 보입니다. 물론, n이 무한히 커지면 해시가 평균적으로는 더 빠르지만, 이 정도 작은 수라면 경험적으로 얼추 둘이 비슷하게 나오는 것 같습니다.

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