01.26(화)
연결 리스트, 해시 테이블 공부 -> 포스팅 진행중
01.28(목)
연결리스트, 해시테이블 블로깅을 진행하였다... 직접 구현도 하다보니 진짜 오래걸렸다...
01.29(금)
시간복잡도
영상 복습 진행
Array
| 삽입 | 제거 | Lookup(position) | Find(value) | 할당 |
|---|---|---|---|---|
| O(n) | O(n) | O(1) | O(n) | O(1) |
삽입, 제거가 O(n)인 이유는 삽입, 제거 후 뒤의 요소들을 앞으로 한칸씩 당기거나 밀어야하기 때문
LinkedList
단일연결리스트
| 삽입 | 제거 | Lookup(position) | Find(value) | 할당 |
|---|---|---|---|---|
| O(1) | middle: O(n) or head: O(1) | O(n) | O(n) | O(n) |
연결 리스트는 인덱스가 존재하지 않아 head부터 찾아야 한다.
삽입과 제거는 내가 넣고, 삭제 하고싶은 위치를 안다는 가정하에 삽입은 O(1)이고 삭제를 중간에서 진행할 경우에는 이전 노드를 찾아야 하기 때문에 O(n)의 시간 복잡도를 갖는다.
이중연결리스트
| 삽입 | 제거 | Lookup(position) | Find(value) | 할당 |
|---|---|---|---|---|
| O(1) | O(1) | O(n) | O(n) | O(n) |
Tree
트리
| Find(value) |
|---|
| O(n) |
이진탐색트리
| Find(value) |
|---|
| O(log n) 최악의 경우: O(n) |
최악의 경우 -> 이진 탐색 트리임에도 밸런스가 무너져 링크드 리스트와 비슷한 경우
최악의 경우를 해결하기 위해서는 노드를 추가할 때마다 왼쪽 서브트리와 오른쪽 서브트리의 마지막 노드 깊이가 1이상 차이가 나지 않는 트리로 변경해준다.
+) 면접 질문 예상 리스트
안정성, 확장성 있는 서버를 구축하고 가꾸는 개발자를 목표로 공부하고 있습니다. 🤔🤔🤔🤔 부족하기에 맞지 않는 내용이 있을 수 있습니다. 가감없이 피드백 해주시면 정말 감사하겠습니다..🙏