CH06 : Dynamic Sets and Searching 1 - Amortized Analysis, Array Doubling

Dynamic sets는 동적인 원소 집합으로, 시간의 흐름에 따라 원소의 개수가 변화하는 집합을 말한다. 이러한 dynamic sets의 구현에서 필요한 array doubling에 대해 알아보고, array doubling을 합리적으로 분석할 수 있는 기법인 amortized analysis(분할 상환 분석)에 대해 알아보려고 한다. Array DoublingArray Doubling이란? array는 사용할 크기를 미리 결정한다는 특성이 있다. 이에 따라 임의의 index에 상수 시간 접근이 가능하다는 장점이 있지만, array의 size가 불필요하게 많이 남거나 필요한 공간보다 부족한 상황이 발생할 수 있다는 단점도 있다. Array Doubling은 array size가 부족할 때 기존 arr..

CH04 : Sorting 5 - Radix Sort

Radix Sort(기수정렬)은 입력의 제한사항으로 인해 문제의 복잡도가 $\Omega (n)$으로 내려간 경우의 정렬 알고리즘이다. (원래 정렬문제 복잡도는 $\Omega (n \log n)$) → Radix Sort는 특수한 상황에서 정렬을 $O(n)$ time에 수행하는 정렬 알고리즘이다.Radix Sort의 Input 기존 정렬 문제와 달리, radix sort 상황에선 다음과 같은 input에 대한 추가 정보가 주어진다.key값은 1부터 임의의 정수 m 사이의 정수이다.key값의 자릿수가 제한돼 있다. (ex. key값은 다섯자리 이하 정수)각 자릿수의 값 범위가 제한적이어야 한다. (ex. 10진수 → 자릿수당 가능한 값 10개(0~9)) 즉, radix sort는 '자릿수 기반으로 정렬 가능..

기존 heap sort는 $W(n) = 2n \log n + O(n)$ time이 걸린다. Acclerated heap sort의 경우 이를 $n \log n$으로 단축시킬 수 있다. (2배 speedup) fixHeap을 fixHeapFast로 개선한다. Acclerated Heap Sort아이디어 binary search에선 중앙값과 K의 비교를 통해 앞으로 살펴볼 영역의 절반을 없앤다. 즉 수평적으로 divide and conquer 전략을 사용한다. acclerated heap sort에선 수직적으로 divide and conquer 전략을 사용한다.전략 현재 heap의 height h에 대하여, $\frac {h}{2}$가 될 때까지 vacant의 위치를 내린다.현재 vacant의 key값과 부..

Heap Heap의 조건 Heap이 되기 위한 조건은 다음의 두 개이다.구조조건 : complete binary treeheight h에 대하여, h-1까지는 complete tree (꽉 찬 트리)모든 leaves는 depth h나 h-1에 위치, depth h의 leaves는 왼쪽부터 채워진다.순서조건 : partial order tree propertymaxheap 기준, parent의 key 값이 나보다 크거나 같아야 한다. minheap일 땐 parent의 key 값이 나보다 작거나 같아야 한다.  아래는 heap인지, 아닌지를 구분하는 예시이다.Heap ADT 삽입 : insert()삭제 : deleteMax()*max heap 기준탐색 : getMax()*max heap 기준W(n)$O( \..

Merge sort는 sorting(정렬) 문제의 optimal 알고리즘으로, $O \left(n \log n\right)$ time을 필요로 한다.Merge에 대하여 - 정렬된 sequences의 mergeMerge 문제 오름차순으로 정렬된 sequence A, B에 대하여, A, B를 합하여 하나의 정렬된 sequence C를 만들어라. 전략 A의 첫 원소와 B의 첫 원소 중 최솟값으로 C의 첫 원소를 구한다. 이가 A의 원소였다고 가정하자. 그럼 문제는 A의 나머지 원소와 B의 원소를 merge하는 것으로 재정의된다.  만약 A 혹은 B가 empty하다면, 남은 배열의 원소들을 C의 뒷부분에 붙인다. Algorithm & Analysis Algorithmmerge(A, B, C)//A or B가 e..

정렬 문제에서의 Optimal SolutionUnsorted data에서 key를 비교해 탐색하는 경우, optimal solution은 $\theta \left( n \right)$를 필요로 한다. Sorted data에서 key를 비교해 탐색하는 경우, optimal solution은 $\theta \left( \log n \right)$를 필요로 한다. 즉, input의 형태에 따라 문제의 복잡도는 변화한다.Insertion Sort (삽입정렬)Strategy n개의 원소를 가진 배열에 대하여 index 1부터 n-1의 원소까지가 삽입되듯이 동작한다. 삽입된 해당 원소가 swap을 이용해 적절한 위치로 이동한다. Example회색 영역은 정렬된 원소들, 검은색 영역은 현재 삽입되어 정렬될 원소,..