-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
해시의 시간복잡도
23.05.28 07:44 작성 조회수 238
0
강의에서 실무에서는 10~20개의 연결리스트만하기때문에 해시의 O(1)을 갖는다고 하셨는데,
면접에서 물어볼경우는 O(n) 이라고 답하는게 맞을까요
O(1)이라고 하는게 맞을까요?
실무에서는 제한을 두지만 여기서는 그런 제한을 두고 물어볼거라는 의도가 있을까? 해서요
답변을 작성해보세요.
0
김태원
지식공유자2023.05.28
안녕하세요^^
참 이 부분이 애매하긴 한데, 평균 : 0(1), 최악 : O(n)으로 대답하는게 이론적으로 맞다고 생각합니다.
면접에서 해시테이블의 시간복잡도를 물어본다면 저같으면 다음과 같이 대답할 것 같습니다.
"해시테이블의 탐색, 삽입, 삭제의 시간복잡도는 평균적으로 O(1)을 갖지만 충돌이 빈번하게 일어나면 최악의 경우인 O(n)의 시간복잡도로 수렴할 수 있습니다."
실무 얘기를 괜히 해서 헷갈릴 수 있겠네요. 영상을 수정해서 헷갈리지 않도록 하겠습니다.
답변 1