Tree, map 시간복잡도
2022. 12. 18. 17:15ㆍ카테고리 없음
Tree?
- 트리란 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다.
- 실제로 어디에 많이 사용되나?
- 트리 중 이진트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.
이진 트리와 이진 탐색 트리
주로 트리에서는 이진트리를 사용한다고 볼 수 있다.
이진트리와 이진 탐색 트리 라고 해서 두가지가 존재하는데, 각각 비슷해보이지만 다르다.
- 이진 트리: 노드의 최대 Branch가 2인 트리
- 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
- 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
- 이진트리는 단순하게 Branch가 2인 트리라면, 이진 탐색 트리는 삽입, 탐색, 삭제 시에 크기 비교를 통해 작동을 한다는 것이 다르다.
- 그래서 이진탐색트리의 시간복잡도는 O(log n) -> 트리의 깊이
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함
단점
- O(log n) 이지만, 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
- , 최악의 경우는 링크드 리스트등과 동일한 성능을 보인다.
Hash Table ?
- 배열과 링크드 리스트로 이루어진 저장 공간이다.
- 인덱스를 안다면 O(1)의 시간 복잡도로 접근이 가능한 배열의 장점을 사용하기에 원하는 key값에 해당하는 데이터에 빠른 탐색 , 삭제 , 추가가 가능하다.
- 해시 코드가 중복되는 것을 충돌이라고 하고는데 그것을 해결하기 위해 linkedList를 사용한다.
HashMap은 사람이 알아 볼수 있는 Key값을 배열의 index처럼 변환하여 빠른 접근이 가능하도록 구현된 자료구조이다.
해시 코드 충돌로 인한 경우는 O(n)으로 링크드 리스트를 tree구조로 변경하기도 합니다.
단점:
먼저 hash 값들을 저장할 공간(bucket)을 지정해야하므로 일반적으로 저장 공간이 많이 필요 합니다.
또한 여러 key 에 해당하는 hash(주소)가 동일한 경우 해시 충돌 (Hash Collision) 이 발생합니다.
가장 관건은 중복되지 않으면서도 빠른 성능을 내는 Hash Function의 구현과,
충돌 문제애 대한 해소 방법이 HashMap의 성능을 좌우한다고 할 수 있겠습니다.
<Hash와 tree 시간 복잡도 정리 >
tree같은 경우는 데이터를 넣어서 검색을 많이 해야 할때 사용한다.
Hash는 방식으로 검색을 한다고 하면 O(1)이고 tree는 O(long n)이다 . 해시를 사용한다고 가정한다면 1.1 과 1이 있다 서로 인접해 있는가? 해시값을 본다면 순서와 관계 없이 무작위한 값이 나온다. 인접해 있지 않을 가능성이 높다. 2보다 작은 실수중에 갖고 있는 데이터를 찾고 싶다면 hash를 썼을때 어떻게 해야 하는가? 해시함수를 돌려봐야 한다. 소숫점 몇쨰 자리 까지인지 알고 할수 없다. tree는 정렬이 되어있다, 해쉬는 정렬이 안되어 있어서 차이가 크다. ex)가격대를 150-200만원 검색 할수 있다면 이때는 hash가 유리한가 tree가 유리 한가? 해시는 모두다 해시 함수로 돌려서 나온 값을 보여 줘야 하다보니 , 소숫점 까지 경우의 수 까지 계산해서 생각 해야 한다. 시간 복잡도상 tree로 검색하는게 더 빠를 것이다. 정렬이 필요없으면 hashMap를 사용하면 되고 정렬이 필요하면 treeMap을 사용해야 한다.