2
분명히 최상의 경우는 O (n)이지만 분명히 최악의 경우는 O (n)이며 이해할 수 없습니다. 해시 테이블을 연결된 목록의 배열로 구현하면 모든 해시가 같은 위치로가는 최악의 경우를 가정합니다.체인을 사용하여 해시 테이블을 채우는 최악의 경우와 가장 좋은 경우?
링크 된 목록에 항목을 추가하는 것이 노드를 맨 앞쪽에 붙이는 문제이므로 각 항목을 여전히 O (1)로 두지 않습니까? 최악의 경우, 빈 버킷과 크기 n의 버켓으로 구성됩니다. 내가 여기서 무엇을 놓치고 있니?
+1 존재 여부를 확인하는 논리를 완전히 잊었습니다. 이것을 언급 해 주셔서 감사합니다! – templatetypedef
아, 맞아요. 여러 번 확인하려면 O (n) 시간이 걸립니다. 그게 그게 틀림 없어. – mavix