본문 바로가기

알고리즘17

13-3. 해슁 3 좋은 해쉬 함수란? - 현실에서는 키들이 랜덤하지 않음 - 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 - 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 게 바람직 - 해쉬함수 값이 키의 특정 부분에 의해서만 결정되지 않아야.. Division 기법 - h(k) = k mod m - 예 : m = 20 and k = 91 -> h(k) = 11 - 장점 : 한 번의 mod 연산으로 계산. 따라서 빠름. - 단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p이면 키의 하위 p비트가 해쉬함수 값이 됨. Multiplication 기법 -.. 2020. 11. 29.

13-1강. 해슁(Hashing) 1 SUHA(Simple Uniform Hashing Assumption) - 각각의 키가 모든 슬롯들에 균등한 확률로() 독립적으로(independently) 해슁된다는 가정 => 사실 현실적이지 않다. - 성능분석을 위해서 주로 하는 가정일 뿐 - hash 함수는 deterministic하므로 현실에서는 불가능하다 - Load factor alpha = n/m: - n : 테이블에 저장될 키의 갯수 - m : 해쉬테이블의 크기, 즉 연결리스트의 깃수 - 각 슬롯에 저장된 키의 평균 갯수 - 연결리스트 T[j]의 길이를 Nj라고 하면, E[Nj] = alpha - 만약 n = O(m)이면 평균검색시간은 O(1) 2020. 11. 24.

12-2강. 레드블랙트리 (3) RB-DELETE(T, z) // T: Binary Search Tree, z : 삭제할 노드 if left[z] == nil[T] or right[z] == nil[T]// 자식이 없거나, 자식이 하나거나 then y 2020. 11. 22.

12-1강. 레드블랙트리(1) 문제 상황 : 현실세계에서는 완벽하게 정렬된 Binary Search Tree는 찾기 힘들다. 오른쪽으로 극단적으로 치우친 경우가 존재할 수 있다. 보완 방법 : 레드블랙트리(Red-Black Tree)는 이를 보완하기 위해 등장했다. 완벽하게 트리의 균형을 맞출 수는 없으나, 어느정도 보완을 가능하게 한다. INSERT, DELETE 알고리즘을 적절하게 수정했다. 레드블랙트리 - 이진탐색트리의 일종 - 균형 잡힌 트리 : 높이가 O(log2n) - SEARCH, INSERT, DELETE 연산을 최악의 경우에도 O(log2n) 시간에 지원한다. - 각 노드는 하나의 키(key), 왼쪽자식(left), 오른쪽 자식(right), 그리고 부모노드(p)의 주소를 저장한다. - 자식노드가 존재하지 않을 경우,.. 2020. 11. 17.

이전 1 2 3 4 5 다음

티스토리툴바