In this post, 05 Algorithm lecture is introuduced.

CLRS chater 5.1 ~ 5.3, 6.1 ~ 6.5 의 내용을 다룬다.

5.1 The hiring problem

Hiring Problem의 의사 코드는 다음과 같다.

HIRE-ASSISTANT(n)
best = 0
for i = 1 to n
	interview candidate i
	if candidate i is better than candidate best
		best = i
		hire candidate i

이 알고리즘의 cost는 1명의 hire 될 때의 비용을 $c_h$, 1명을 interview할 때의 비용을 $c_i$ 라고 하고, $m$ 명이 hire 되었다고 하면 $O(c_in+c_hm)$ 이다. 여기서 우리는 average-case running time과 expected running time의 차이를 이해해야 한다.

average-case running time

입력이 어떠한 분포를 따른다는 가정하에 (Ex. 후보자들이 random permutation으로 온다) 가능한 input의 distribution에 대해 output의 average를 구하는 방식이다. 예를 들어, 위 예시에서 후보자들의 순위를 1~n까지 매긴 순열이 $1/n!$ 의 확률로 input으로 온다고 가정하고 average output을 구한다. 이런 접근을 probabilistic analysis 라고도 한다.

expected running time

Hiring problem에서 우리는 후보자들이 랜덤순서로 온다고 가정하지만(우리는 이러한 상황을 풀고 싶은 것이다) 실제로 분석을 위해 몇 개의 인풋을 구했더니 운이 나쁘게도 worst-case들만 들어올 수도 있다. 이때 우리는 randomized algorithm 을 이용하는데 1~n의 순열이 input으로 들어오면 알고리즘 내부적으로 랜덤하게 수를 하나씩 뽑아 그 순서대로 interview를 진행하는 것이다. 이렇게 인풋과 더불어 알고리즘 내부의 random-number-generator에 의해 행동이 결정되는 알고리즘을 randomized algorithm이라 한다. 이렇게 random number generator의 분포에서 나온 output(running time)의 기댓값을 구한 것이 expected running time 이다.

5.2 Indicator random variables

Indicator random variable이란 표본공간 S의 사건 A에 대해 정의되는 확률변수로, 사건 A가 발생하면 1, 발생하지 않으면 0의 값을 갖는다.

이 때, 다음의 중요한 lemma가 성립한다.

$E[X_A]=Pr(A)$ 이 때, $X_A$ 는 사건 A에 대한 Indicator random variable 이다.

Hiring problem에서 hiring 횟수($X$)에 대한 expected number를 기댓값의 정의에 의해 곧바로 구하는 것은 쉽지 않다. 하지만 Indicator variable을 이용하면 $X=X_1+X_2+…+X_n$ 이고, $E[X]=E[\sum X_i]=\sum E[X_i]=\sum Pr(X_i)=\sum 1/i=logn +O(1)$ 임을 쉽게 구할 수 있다.

이는 input이 랜덤하게 들어온다는 가정을 바탕으로 한 것으로, 위에서 average-case running time에 해당한다.

물론, hiring problem에서 randomized algorithm을 적용하여 주어진 지원자들의 입력 순서를 랜덤하게 바꾼 뒤에 계산한 expected running time도 위와 동일하게 나온다. 이 때, 다음 두 표현의 차이를 생각해보자.

• 지원자가 무작위 순서로 온다고 할 때 HIRE-ASSISTANT 알고리즘은 총 $O(c_h logn)$ 의 average-case total hiring cost 가 든다.
• RANDOMIZED-HIRE-ASSISTANT 알고리즘은 $O(c_h logn)$ dml expected hiring cost 가 든다.

전자는 입력에 대한 가정을 했지만, 후자는 입력을 랜덤화하기 위해 약간의 추가 시간이 필요하지만 입력에 대해선 어떠한 가정도 하지 않았다.

❗Randomize를 하거나 아니면 무작위 가정을 함으로써 우리는 indicator random variable을 도입했을 때 Expectation을 확률로 계산하는데, 이 때 그 확률이 매우 간단하게 구해진다.

5.3 Randomized Algorithms

많은 randomized algorithm에서 주어진 input array를 permuting 함으로써 input을 randomize 하는 방식을 사용한다. (다른 randomize 방식도 있다). input array를 permute 할 수 있는 2가지 방법을 알아보자.

PERMUTE-BY-SORTING(A)
n = A.length
let P[1..n] be a new array
for i = 1 to n
	P[i] = RANDOM(1, n^3)
sort A, using P as sort keys

여기서 RANDOM 함수 자체는 잘 만들어져있다고 생각하자. $n^3$ 을 사용하는 이유는 P가 중복되는 값을 가질 확률을 낮추기 위해서이다. 이제 이렇게 permute 했을 때 우리는 이 알고리즘이 uniform random permutation 을 보장하는 이유를 알아보아야 한다.

다른 permute 방법은 아래와 같다.

RAMDOMIZE-IN-PLACE(A)
1 n = A.length
2 for i = 1 to n
3 	swap A[i] with A[RANDOM(i,n)]

$pf)$ Loop invariant를 이용한다. 우리의 Loop invariant 는 아래와 같다.

i번째 iteration이 수행되기 전, n개의 element에 대해 가능한 (i-1)-permutation에 대해 A[1:i-1] 이 이 (i-1)-permutation을 포함할 확률이 $(n-i+1)!/n!$ 이다.

Initialization : i=1일때, A[1:0] (empty array) 는 0-permutation을 1의 확률로 포함하므로 성립.

Maintenance : (시간나면 보기, 127pg)

Termination : (시간나면 보기, 128pg)

6.1 Heaps

Heap 은 heap property (max-heap, min-heap property)를 만족시키는 complete binary tree 이며, array로 표현할 수 있다.

❗Heap은 nearly complete tree이기 때문에 tree를 나타날 때 포인터를 이용하여 parent-child를 linking 할 필요 없이, array 집어 넣어 왼쪽부터 오른쪽까지 빽빽하게 채울 수 있다. parent와 child 관계가 포인터없이 index로만 접근 가능하며 따라서 매우 efficient 하다. 그렇기 때문에 Heapsort가 efficient 할 수 있다.

6.2 Maintaing the heap property

array A와 인덱스 i에 대하여 MAX-HEAPIFY(A, i) 프로시저는 Left(i), Right(i)가 각각 Heap 이지만, A[i] 로 인해 Heap 이 아닌 상황에서 $O(h)$ 의 시간 복잡도로 Heap을 만들어준다. (h는 노드 i의 height)

MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size and A[l] > A[i]
	largest = l
else largest = i
if r<= A.heap-size and A[r] > A[largest]
	largest = r
if largest != i
	exchange A[i] with A[largest]
	MAX-HEAPIFY(A, largest)

A[i]를 A[i] 보다 큰 자식 노드 중 (2개 다 더 크다면) 더 큰 노드와 바꾼다음 바뀐 노드 위치에서 MAX-HEAPIFY를 재귀적으로 호출하는 방식으로 이루어진다. MAX-HEAPIFY 알고리즘에서 시간 복잡도는 A[i], A[Left(i)], A[Right(i)]의 관계를 결정하는 시간 $\theta (1)$ 과, 자식 중 하나를 루트로 하는 서브 트리에서 MAX-HEAPIFY를 실행하는 시간을 더한 것이다. 자식들의 서브 트리는 최대 크기가 $2n/3$ (연습문제 6.2-2) 이므로, 수행 시간은 다음과 같이 나타낼 수 있다.

$T(n) \leq T(2n/3) + \theta(1)$

마스터 정리를 이용하면 $T(n)=O(lgn)=O(h)$ 이다.

6.3 Building a heap

unsorted 된 array A를 Heap으로 만드려면 leaf node인 $A[\lfloor n/2 \rfloor+1]$ ~ $A[n]$ 을 제외하고 가장 아래 노드인 $A[\lfloor n/2]$ 부터 루트 노드인 $A[1]$ 까지 순차적으로 MAX-HEAPIFY를 수행한다.

BUILD-MAX-HEAP(A)
1 A.heap-size = A.length
2 for i = floor(A.length/2) downto 1
3 	MAX-HEAPIFY(A,i)

이 프로시저의 correctness를 loop invariant로 보이자.

Loop invariant : line 2-3의 iteration 시작 전에, node i+1, i+2, … n은 max-heap의 root 이다.

Initialization : leaf node는 max-heap

Maintenance : iteration 시작 전에, node i+1, i+2, … n은 max-heap의 root 임을 가정하자. 그러면 MAX-HEAPIFY(A, i)에서 i의 두 자식 노드는 모두 max-heap의 root이므로 MAX-HEAPIFY가 제대로 수행될 수 있는 조건을 갖추었고 그 결과 node i, i+1, … n은 max-heap의 root가 되며 이는 다음 iteration i가 i-1이 될때까지 유지된다.

Termination : i=0 일때, node 1(root)가 Max-heap의 root이므로 만족.

n-element heap의 height 는 $\lfloor lgn \rfloor$, height가 h인 heap에는 최대 $\lceil n/2^{h+1} \rceil$ 개의 노드가 있다는 특성과 MAX-HEAPIFY의 시간복잡도가 $O(h)$ 임을 이용하면, 위 프로시저의 시간복잡도가 $O(n)$ 임을 증명할 수 있다.

6.4 The heapsort algorithm

unsorted 배열 A가 있을 때, heapsort algorithm에서는 우선 BUILD-MAX-HEAP을 한다. 그러면 A[1] 이 최대 원소임이 보장되므로 A[1]을 A[n]과 교환한다. A[1:n-1]은 다시 HEAPIFY 조건을 만족하므로 (A[2], A[3] 가 Heap의 루트) 다시 MAX-HEAPIFY를 하고 이 과정을 반복한다.

HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.length downto 2
3 	exchange A[1] with A[i]
4		A.heap-size = A.heap-size - 1
5 	MAX-HEAPIFY(A, 1)

Hearsort의 수행시간은 $O(nlogn)$ 이다.

6.5 Priority queues

Priority queue 는 key라는 value를 가진 element들로 이루어진 set S로, 다음의 ADT를 수행하는 자료구조이다.

• INSERT(S, x) : element x를 set S에 추가
• MAXIMUM(S) : largest key를 가진 element를 return
• EXTRACT-MAX(S) : largest key를 가진 element를 return 하고 remove
• INCREASE-KEY(S, x, k) : x의 key를 k로 update. 단, k가 현재 x의 key보다 클 때만.

set S를 Heap으로 관리하면 다음의 프로시저를 간단하게 구현할 수 있다.

HEAP-MAXIMUM(A)
return A[1]

HEAP-EXTRACT-MAX(A)
if A.heap-size < 1
	error
max = A[1]
A[1] = A[n]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
return max

위 프로시저의 시간복잡도는 $O(lgn)$

HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
	error
A[i] = key
while i > 1 and A[i] > A[PARENT(i)]
	exchange A[i], A[PARENT(i)]
	i = PARENT(i)

위 프로시저의 시간복잡도는 $O(lgn)$

MAX-HEAP-INSERTo(A, key)
A.heap-size++
A[A.heap-size] = -Infinite
HEAP-INCREASE-KEY(A, A.heap-size, key)

위 프로시저의 시간복잡도는 $O(lgn)$