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

안녕하세요 좋은 강의 잘 듣고 있습니다!

open addressing으로 collision을 해결할 때의 worst case에 대해서는 말씀해주시지 않아서 조금 혼란스러운데요, 이 방법은 최악의 경우에도 O(n)의 시간복잡도를 갖지 않는 것일까요? 제 생각에는 open addressing도 separate chaining과 마찬가지로 최악의 경우 O(n)의 시간복잡도를 가져야할 것 같습니다.

예시를 들어보면

hash function: h = x mod 10

linear probing을 사용

데이터가 1, 11, 21, 31, 41 이렇게 다섯개가 있는 상황에서 순서대로 hash table에 저장하게 된다면 41을 찾는 상황에서 index를 아래와 같은 순서로 접근하는 것으로 이해했습니다.

1 -> 2 (1 + 1) -> 3 (1 + 2) -> 4 (1 + 3) -> 5 (1 + 4)

이 순서로 탐색을 하게 되면 O(n) 만큼의 시간이 소요되는 것 아닌가요?

제가 잘못 이해한 부분이 있다면 알려주시면 감사하겠습니다!