해시의 시간복잡도
395
작성한 질문수 12
강의에서 실무에서는 10~20개의 연결리스트만하기때문에 해시의 O(1)을 갖는다고 하셨는데,
면접에서 물어볼경우는 O(n) 이라고 답하는게 맞을까요
O(1)이라고 하는게 맞을까요?
실무에서는 제한을 두지만 여기서는 그런 제한을 두고 물어볼거라는 의도가 있을까? 해서요
답변 1
0
안녕하세요^^
참 이 부분이 애매하긴 한데, 평균 : 0(1), 최악 : O(n)으로 대답하는게 이론적으로 맞다고 생각합니다.
면접에서 해시테이블의 시간복잡도를 물어본다면 저같으면 다음과 같이 대답할 것 같습니다.
"해시테이블의 탐색, 삽입, 삭제의 시간복잡도는 평균적으로 O(1)을 갖지만 충돌이 빈번하게 일어나면 최악의 경우인 O(n)의 시간복잡도로 수렴할 수 있습니다."
실무 얘기를 괜히 해서 헷갈릴 수 있겠네요. 영상을 수정해서 헷갈리지 않도록 하겠습니다.
백준 서비스 종료인데 도전 과제 프로그래머스 문제로 올려주실수 있으신가요
0
83
2
도전과제 질문있습니다
0
77
2
안녕하세요 강사님 파이썬 커리큘럼 문의드립니다..
0
91
2
두수의합 sorting 질문
0
146
1
두수의합 Counter 사용
0
165
2
[문제3번] 두수의 합 : O(nlogn)
0
143
1
set을 활용한 중복제거
0
201
2
[문제 5번] 중복제거
0
156
1
최소값의 위치
0
145
1
백준 사용 시 채점 언어
0
180
1
백준 10546 배부른 마라토너
0
158
1
고정된 숫자 문제 질문
0
214
2
답은 맞는거같은데 틀렸어요
0
209
1
강의 커리큘럼 질문있습니다.
0
243
1
배열리스트 문제 5번 <중복 제거> 질문입니다.
0
281
1
체크배열을 set 으로 사용해도될까요?
0
253
1
연결리스트의 삽입과 삭제에서 시간복잡도.
0
359
1
내장 함수들의 시간복잡도는 외워둬야하나요?
0
241
1
중복 제거
0
346
1
카드 점수 정확성 테스트 경우의 수 문의
0
193
1
완강 후 후속 강의, 공부법 질문..
0
378
2
cnt = 1 과 nums.sort() 의 순서가 바뀌어야하지 않나요?
0
280
2
nums 조건오류인가요?
2
309
1
최솟값의 위치
0
253
2