제일 먼저, 직접 이분탐색을 활용한 풀이를 작성해서 제출해보셨나요? 본인의 해시맵 코드와 남의 이분탐색 코드를 비교해서 그런 결론을 내리면 위험한 게, 그 차이가 이분탐색과 해시맵의 차이에서 온 게 아니라 다른 요인에서 온 것일 가능성을 배제할 수 없습니다.
아래 설명은 본인이 이분탐색을 활용하는 코드를 직접 제출하셨는데도 동일한 현상이 발생했을 때 유효한 설명입니다.
-----------------------
시간복잡도는 절대적인 소요시간을 알려주는 게 아니라, 입력량이 늘어남에 따라 소요시간이 어떤 양상으로 늘어나는지를 간편하게 볼 수 있는 지표입니다. 때문에 O(nlogn) 알고리즘이 O(n) 알고리즘보다 빠른 게 그렇게 드문 일은 아닙니다.
이게 가장 많이 보이는 경우가 hashmap을 사용하는 경우입니다. 해시맵은 원소의 삽입, 접근 및 삭제가 O(1)에 이뤄지긴 하지만, 해시맵에 들어있는 값이 많으면 많을수록 이 연산에 오랜 시간이 걸리게 됩니다. 이는 해시 충돌로 인해 발생하는 현상으로, 해시맵에 들어가는 값이 몇십만~몇천만 개 이상으로 늘어나면 같은 O(1)이라고는 해도 확실히 속도가 느려집니다.
한편 벡터는 메모리상에 연속되어 있는 배열이나 다름없으며, 각 값에 접근하는 속도도 컴퓨터 특성상 매우 최적화되어 있습니다. 때문에 벡터의 원소에 접근하는 연산 역시 O(1)이지만 해시맵에서 검색하는 시간복잡도 O(1)보다 압도적으로 빠릅니다.
이와 같이 같은 시간복잡도의 연산이라도 실제 소요시간은 큰 차이가 나는 걸 흔히 "상수 차이가 크다"고 표현합니다. 시간복잡도 표기는 가장 차수가 높은 항의 계수를 빼고 생각하는 것으로, 이 계수가 크면 시간복잡도로는 유리해보여도 실제로는 속도가 느린 경우가 발생하는 겁니다. 이 차이가 크다는 걸 구어적으로 "상수 차이"라고 하는 겁니다.
다만 해시맵도 해시 알고리즘을 어떻게 구현하느냐에 따라 소요시간의 차이는 매우 크며, 이 차이까지 고려하게 되면 해시맵의 퍼포먼스는 사실상 예측 불가하게 됩니다.
yms737 1년 전
안녕하세요. 제가 문제를 C++의 unordered_set 자료구조를 사용해서 풀었습니다.
unorderd_set은 hash기반 구조여서 삽입, 탐색이 O(1)으로 알고있습니다. (삽입, 검색 모두 다하면 O(N + M))
제가 정답은 맞았는데 시간이 440ms가 걸렸습니다.
다른분들 코드를 보니 대부분 입력을 배열에 넣어놓은 뒤 정렬 후 이분 탐색을 통해 값을 찾는 과정을 거치셨다는 것을 알게됐습니다.
이렇게 하면 시간복잡도는 O(NlogN)이 걸릴 것이라 생각합니다. (삽입, 정렬, 검색 모두 다하면 O(N + NlogN + MlogM))
하지만 이렇게 해결하신 분들은 대부분 200ms 내외의 시간이 걸리는 것을 발견했습니다.
hash기반 구조를 쓰는 것이 더 시간이 짧을 것 같은데 시간이 더 오래걸리는 이유가 궁금합니다!!