Open addressing을 사용할 때의 worst case

Question

안녕하세요 좋은 강의 잘 듣고 있습니다!   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) 만큼의 시간이 소요되는 것 아닌가요?   제가 잘못 이해한 부분이 있다면 알려주시면 감사하겠습니다!

nossi · Answer

안녕하세요 준환님. 제가 해당 내용을 설명드리지 않아서 혼란스러우셨군요 ㅜ 준환님께서 말씀하신대로, open addressing의 worst case의 시간복잡도는 O(n)이고, 준환님께서 가정하신 예시가 정확한 예시입니다. 잘 이해하고 계시네요! 혹시 다른 궁금하신 점 있으시면 언제든지 질문 주세요 :)