해시 테이블 자료구조에서 리해싱 작업의 시간 복잡도가 O(N^2)이 아니라 O(N)인 이유가 궁금합니다

Question

해시 맵 자료구조에서 로드 팩터가 0.7~0.8 정도 되면 버킷을 동적 확장 하는데이 경우 리해싱 작업이 일어나고 각 데이터에 대해 새로 해싱작업이 일어납니다그러면 리해싱 과정은 O(n^2)인 것으로 생각되는데 찾아보니 O(n)이라고 나와 있네요각 데이터 별로 리해싱시 충돌 가능성으로 O(n)의 시간 복잡도를 가지니 O(n^2)이 아닌가 생각하는데 잘못 생각하고 있는 걸까요?

해시 테이블 자료구조에서 리해싱 작업의 시간 복잡도가 O(N^2)이 아니라 O(N)인 이유가 궁금합니다

0개의 답변

기타 목록