해시 콜리 전 선형 검사 실행 시간

Question

친구와 함께 숙제를하려고하는데 선형 프로브 방법의 검색, 추가 및 삭제의 평균 실행 시간을 묻습니다. O (n)이라고 생각합니다. 추가 할 공개 노드가 발견 될 때까지 특정 노드 수를 확인해야하기 때문입니다. 검색은 원래 색인에서 시작하여 원하는 번호를 찾을 때까지 이동합니다. 하지만 내 친구들은 그것이 O (1)라고 말합니다. 어느 것이 옳은가?

Answer 1

우리가 점근선 복잡성에 대해 말할 때 우리는 일반적으로 매우 큰 n을 고려합니다. 이제 해시 테이블에서의 충돌 처리에 대해 메소드 중 일부는 연속 해싱 & 선형 프로빙입니다. 두 경우 모두 두 가지 일이 발생할 수 있습니다 (이는 질문에 답하는 데 도움이됩니다). 1. 해시 테이블이 가득 차서 크기 조정이 필요할 수 있습니다. 2. 충돌이 발생할 수 있습니다.

최악의 경우, 해시 테이블을 어떻게 구현했는지에 따라 달라집니다. 선형 프로빙에서는 번호를 찾지 않고 계속 이동하고 찾고 있던 번호는 끝에 있습니다. 여기에 O (n) 최악의 경우 실행 시간이옵니다. 쇠사슬로 묶인 해싱 기법을 사용할 때 충돌이 발생하면 균형있는 이진 트리에 키를 저장하므로 최악의 실행 시간은 O (log n)가됩니다.

이제는 실행 시간이 가장 좋은 상황에 이르렀는데 어느 경우에도 O (1)이 될 혼란이 없다고 생각합니다.

O (n)은 최악의 경우에 발생하며 좋은 설계된 해시 테이블의 평균적인 경우에는 발생하지 않습니다. 평균 해시 테이블에서 일어나는 일이 시작되면 해시 테이블은 평균적으로 균형 잡힌 나무가 O (로그 n)를 항상주고 그 위에 너무 순서를 유지하기 때문에 데이터 구조에서 자리를 찾지 못할 것입니다.

유감스럽게도 유감스럽게도 친구가 맞습니다. 최악의 시나리오에서 사례가 발생할 수 있습니다.

또한 즉 상각 실행 시간이 더 많은 정보를 물건 이쪽을 봐 : 나는 Yavar 응답에 추가 할 Time complexity of Hash table