자료구조
리스트
- 임의의 순서와 각 값을 연결하는 link가 있다.
- 검색시에 첫번째 요소부터 link를 따라 검색한다.
- 요소 추가시 유리하다.
- 요소의 개수를 미리 모를 경우 유리하다.
배열
- 순서가 있고, 인덱스가 있다.
- 인덱스를 통해 검색이 용이하다.
- 값을 인덱스 중간에 추가시 그 뒤 요소들을 다 밀어내야 한다.
- 배열의 길이를 늘리려면 새로운 배열을 만들어서 값을 넣는다.
- 요소의 개수를 미리 알고, 검색이 잦을 시 용이하다.
해시 ( aka.Dictionary )
- 사전에 비유될 수 있다. ( 색인 - key, 정보 - value )
- 키 값과 value 값이 있어서 키값을 기준으로 값을 찾는다.
- 해시함수는 키 값을 찾는 나름의 방법이다.
- 순서 기준이 아닌 key값을 기준으로 값을 찾기( look up )하기에 좋다.
- 모든 데이터를 잦는 것은 어렵다.
영어 사전을 기준으로 설명할 경우, 알파벳 순으로 정렬된 리스트/배열의 구조 위에 알파벳 첫 글자를 따는 해시로 인덱스(key)를 부여하여 더 빠르게 찾을 수 있는 구조이다. 이렇게 몇몇 자료구조를 조합하여 활용할 수 있다.
트리
- 계층적인 구조를 다루는데 유용하다.
- DOM 트리처럼 계층적인 구조를 다룰때 많이 사용한다.
- Root를 시작으로 여러 node로 구성되어 있다.
- node는 값과 하위 노드를 가르키는 연결고리로 이루어져있다.
- 각 노드마다 연결고리가 최대 2개까지만 있는 트리를 이진트리( Binary tree )라고 한다.
- RDB도 내부적으로 B-tree라는 트리 구조를 활용하여 데이터를 index해 둔다.
계산 복잡도 ( Computational Complexity )
- 공간 복잡도( space complexity )와 시간 복잡도( time complexity )가 있다.
- 공간 복잡도는 얼만큼의 메모리나 디스크 공간을 필요로 하는지를 의미한다.
- 시간 복잡도는 얼만큼 빠르게 처리 가능한지를 의미한다.
- 보통 계산 복잡도를 이야기할 때 시간 복잡도를 이야기한다.
- 시간 복잡도의 표기법으로 빅 오 표기법 ( BIg O notation )을 많이 쓴다.
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < o(2^n) < o(n!)
- 그래프에서 볼 수 있 듯, O(1)가 가장 빠르고 o(n!)으로 갈수록 느리다.
- 배열에서 몇 번째 데이터를 가져오는 연산은 O(1)에 처리할 수 있다.
- 리스트에서는 처음부터 순회해야 하기 때문에 o(n)의 시간이 걸린다.
- 중간에 데이터를 넣는 작업은 배열은 o(n), 리스트는 o(1)의 시간이 걸린다.
- 이런 식으로 시간 복잡도를 표현할 수 있다.
댓글