검색 알고리즘 비교( 실행시간 비교 )

insert : 삽입을 하는 동작에서만의 시간

remove : 삭제를 하는 동작에서만의 시간

O(1) = 상수시간

[ArraySequenceMap] = 배열 => 검색이 O(N) 이 걸리는 이유는 첫번째 부터 찾을때까지 각 배열에 대해 맞는 것을 찾으려니 선형적으로 걸린다

[ListSequenceMap] = 리스트

BinMap(Binary) =이분검색

=> 트리를 이용하지 않는다!!!

=> 자료집합은 정렬 되어 있어야 한다, 정렬이 되어 있는 상태에서만 작동 가능

=> 삽입될때 만약 배열에 자료들에 배열에 들어가 있는 상태라면 정렬된 상태를 유지하기 위해서 들어갈 이후의 값들이 모두 뒤로 이동 되어야 한다

itpMap(interpolation) = 비례식에 의한 찾기 방식으로 검색은 자료가 선형적으로 있을때 빠른 속도를 보인다 , 수치자료에서만 사용 가능

하지만 O(loglogN) 삽입삭제는 역시 느리다

BinTreeMap(바이너리트리맵)

=> 이진 트리를 이용한 검색방법이다

=> 균형이 맞으면 O(logN) 의 성능을 보이지만 삽입시 균형이 맞지 않으면 한쪽으로 치우치는 최악인 경우 O(N) 의 성능을 보인다

=> chain 은 중복처리를 리스트에서 하기 때문에 저장공간이 자료수보다 큰 필요는 없다

[HashMap,ChainMap 은 상수 시간에 찾기 삽입, 지우기가 끝난다]

=> 관건은 해쉬 펑션을 어떻게 정의 하느냐 이고, 보통 Hash 는 입력 자료수의 2배 만큼의 공간으로 잡을때 성능이 좋다

HashMap(정적인 상황에 적합)

ChainMap (연결 법) => 해쉬 테이블에 이중리스트로 연결하여 데이터를 추가( 동적인 상황에 적합) , 최신 데이터를 리스트의 앞에 넣어줌으로서

노드의 뒤쪽으로 이동하는 시간을 줄일 수 있다

(=>chainmap 은 중복된 값을 리스트에 넣는 것이므로 값을 최근 헤드에 연결된 것을 리턴해 주면 됨으로 검색도 상수시간이다)

[radix tree,radix trie 둘다 자료가 비트로 표현될 수 있어야 한다]

이진트리에서의 한쪽으로 치우치는 현상을 방지된 구조가 된다 => 비트에 의해 좌,우가 결정 됨으로

그래서 검색,삽입,삭제 가 O(logN) 의 성능을 보인다

Radix Tree => 모든 노드가 정보노드

Radix Trie => 정보노드는 leaf 에, 내부(중간)노드는 분기노드

[B-Tree : 하나의 노드에 여러개의 자료가 들어 갈 수 있으면서 균형을 맞추는 구조]

O(logN) 의 성능을 보인다

[RB-Tree : 벨런슬르 자동으로 맞춰주면서 이진트리 구조의 형태를 지닌다]

find 도 O(logN) 이며 insert ,remove 도 O(logN) 이지만 실제 다른 logN 의 성능을 가진 것보다 상당히 빠른 속도를 보인다

검색 : 이진트리 검색과 동일

삽입 : 칼라상향변환 + 회전

삭제 : 칼라하향변환 + 회전

으로 이루어진다

[모든 벨런스 트리는 기본적으로 중복이 불가능하다]

chain, 이나 hash 가 가장 빠르다