5/31 / Data Structures , big O notation , time complexity

체크포인트 

 

big O notation / time complexity

 

O(1)  - Constant
O(log n)  -  Logarithmic
O(n)  -  Linear
O(n^2)  -  Quadratic

오답 정리.

 

Array 특정 인덱스 값을 remove 할 때 , 시작 부분에 값을 삽입할 때

O(n)   /  특정 인덱스를  알거나 시작 부분처럼 정해진 인덱스의 경우 O(1) 이라고 생각했다.

그렇지만 다른 배열들이 자리를 재배치 받게 되어서 O(n).

 

Linked list 에서 이미 한 번 주소값에 연결된 경우, index + 1 에 새 노드를 삽입할 때

O(1)   /  linked list 는 주소 값을 알면 한 번에 접근 가능.

 

Array

Insert	Lookup(position)	Assign	Remove	Find
O(n)	O(1)	O(1)	O(n)	O(n)

Linked Lists

Insert	Lookup	Assign	Remove	Find
O(1)	O(n)	O(n)	O(1)	O(n)

 

Doubly-Linked lists

Insert	Lookup	Assign	Remove	Find
O(1)	O(n)	O(n)	O(1)	O(n)

 

각 data structure 가 사용되는 예시

 

 

 

How Hash tables work

 

데이터를 관리 / 유지하는 구조.

 

hash function 은 입력값이 일정 규칙을 거쳐서 hash table 에 인덱스(key)를 저장  / 해시값(value)

 

key 와 value가 있음.

 

정보를 array 에 저장.

해쉬함수를 거쳐 key 를 숫자로 변경하고 그 숫자에 해당하는 array[index] 에 배치한다. 

겹칠 경우 linked list 로 저장.

 

 

 

후기.

 

오늘 정말 12시 반까지 페어님과 함께 불 태웠다.. 다 끝낼 때까지 집에 못 간다는 긍정적인 약속?을 지켜냈다.

다 이해하고 풀어내긴 했지만 다시 한 번 쭉 훑으면서 어떻게 작성했는 지 꼭 다시 봐야겠다. 앉은 자리에서 12시간 넘게 

진행했다. 끈기도 집중력도 별로인 나지만 누군가와 함께 코드를 적어나가면서 토론하고 왜? 에 대해서 생각하니 
시간이 정말 빠르게 지나갔다.. 벌써 주말이라니.. 주말 아닌 주말이지만 ㅠㅠ