왜 항상 두 개씩 틀리는 걸까요? 본 수업 시작하기 전에 오답 노트를 작성해 봅니다. 소크라티브 문제가 다음 챕터로 넘어가 있어서 틀렸던 문제 생각하려고 뇌를 쥐어짰습니다.
- Hash Table의 삽입 연산을 시간 복잡도 BigO 표기법으로 표기하면 어떤 게 나올까? (일반적인 상황에서)
답> O(1)
내가 쓴 답> O(log n)
O(log n)을 쓴 이유: 솔직하게 말하자면 BST랑 헷갈렸습니다. ㅋㅋㅋ 해시 테이블은 해시 함수를 사용하여 빠르게 넣고, 빠르게 찾는 게 가능한 O(1)의 시간 복잡도를 가지고 있고, 이게 해시 테이블의 제일 대표적인 장점인데도 불구하고 마지막에 배운 게 BST라서 헷갈렸습니다. 해시 충돌이 일어나게 되면 O(n)으로 바뀌지만 어쨌든 O(1)이라는 거. BST는 O(log n)이죠. 전체를 탐색해야 되는 과정에서 반을 계속 쪼개어 절반을 탐색하지 않아도 되게 하니까요.
- linked-list의 BigO 표기법을 잘못 쓴 것은?
- search: O(n) 2. insert: O(1) 3. access: O(1) 4. delete: O(1)
답> 3. access: O(1)
내가 쓴 답: 4. delete: O(1)
4번을 쓴 이유: linked-list는 현재 요소 뒤의 요소를 모르기 때문에 순환을 해서 내 요소 뒤의 요소에 접근을 한 다음에 지우는 거라 O(n)이라고 생각을 했는데, 문제가 요했던 건 linked-list의 대표적 특성을 물었던 것 같다. del이나 insert는 연결 고리만 끊어 주면 되니까 O(1)의 시간 복잡도를 가지고, 탐색하는 search나 access 같은 경우엔 특정 인덱스를 알아도 전체를 한 번씩 다 돌아야 되기 때문에 O(n)의 시간 복잡도를 갖는다.
커신이 고칼로리