인프런 커뮤니티 질문&답변

안녕하세요 수현님! 좋은 질문 감사합니다!!

대부분의 알고리즘에서는 최악의 경우(Worst-case)를 기준으로 분석하는 것이 일반적입니다.
그 이유는 어떤 입력이 들어올지 확실하지 않기 때문입니다.

즉, 입력 데이터에 따라 성능이 달라질 수 있기 때문에, 알고리즘의 성능을 보수적으로 평가하기 위해 최악을 고려하는 것입니다.
만약 최선만 고려한다면, 현실에서 예상보다 성능이 낮아질 가능성이 크기 때문입니다.

그렇다면 왜 해시 테이블만 최선을 고려하는 경우가 많을까요?
이유는 해시 테이블은 현실에서도 최선과 비슷한 성능을 가지기 때문입니다.

해시 테이블을 사용할 때, 보통 좋은 해시 함수를 사용한다고 가정합니다.
이 경우 대부분의 키는 서로 다른 해시값을 가지므로 충돌이 거의 발생하지 않으며, 삽입/탐색이 O(1) 로 동작합니다.

즉, 현실적인 사용 환경에서는 최선의 경우(O(1))가 가장 자주 발생하므로, 일반적으로 평균적인 성능을 기준으로 설명하는 경우가 많습니다.

물론 해시 테이블도 최악의 경우가 발생할 수 있습니다. 해시 함수가 충돌을 너무 많이 일으키면 O(N) 이 될 수도 있습니다. 예를 들어 보안이 중요한 시스템에서는 해시 테이블의 최악의 경우(O(N))를 고려해야 합니다.

해시 충돌을 의도적으로 유도하는 공격(Hash Collision Attack)이 가능하기 때문인데, 이건 한번 찾아보셔도 좋을 것 같습니다!!

안녕하세요, 인프런 AI 인턴입니다.

수현님께서 질문하신 해시 테이블의 시간복잡도에 대한 부분은 해시 테이블의 특성과 관련이 있습니다. 해시 테이블의 평균적인 시간복잡도는 매우 효율적이어 일반적으로 최선의 경우 O(1)이기 때문입니다. 이는 해시 함수가 잘 설계되어 있어 데이터가 균일하게 분배되는 경우를 말합니다.

그러나, 해시 테이블에서도 충돌이 발생할 수 있습니다. 이럴 때는 충돌 해결 전략에 따라 시간복잡도가 달라질 수 있으며, 최악의 경우 O(N)까지 증가합니다. 예를 들어, 해시 함수가 적절치 않아서 모든 키가 동일한 해시 인덱스로 매핑되는 경우가 있을 수 있습니다.

보통 알고리즘의 시간복잡도를 고려할 때는 평균적인 경우를 중점적으로 다루지만, 시스템 요구사항에 따라 최악의 경우를 대비해야 할 때도 있습니다.

관련된 내용을 더 알아보고자 하신다면, 다음의 질문 링크를 통해 다른 논의들로부터 힌트를 얻어보실 수 있습니다:
- 해시 충돌에서 링크드 리스트말고 해시테이블을 이용해서 구현하지 않는 이유가 있을까요?

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.