• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

해시의 시간복잡도

23.05.28 07:44 작성 조회수 238

0

강의에서 실무에서는 10~20개의 연결리스트만하기때문에 해시의 O(1)을 갖는다고 하셨는데,

면접에서 물어볼경우는 O(n) 이라고 답하는게 맞을까요

O(1)이라고 하는게 맞을까요?

 

실무에서는 제한을 두지만 여기서는 그런 제한을 두고 물어볼거라는 의도가 있을까? 해서요

답변 1

답변을 작성해보세요.

0

안녕하세요^^

참 이 부분이 애매하긴 한데, 평균 : 0(1), 최악 : O(n)으로 대답하는게 이론적으로 맞다고 생각합니다.

면접에서 해시테이블의 시간복잡도를 물어본다면 저같으면 다음과 같이 대답할 것 같습니다.

"해시테이블의 탐색, 삽입, 삭제의 시간복잡도는 평균적으로 O(1)을 갖지만 충돌이 빈번하게 일어나면 최악의 경우인 O(n)의 시간복잡도로 수렴할 수 있습니다."

실무 얘기를 괜히 해서 헷갈릴 수 있겠네요. 영상을 수정해서 헷갈리지 않도록 하겠습니다.