[알고리즘-2]알고리즘 디자인

2016.09.10 11:25

최한철 조회 수:338

『Disclaimer: 본 글은 대학원의 데이터과학 알고리즘 수업 및 데이터과학 입문서적에 관한 공부 내용을 정리하는 시리즈입니다. 

본 내용은 필자가 전부 직접 요약하여 적은 개인 노트이며, 개인 공부 및 복습이 주목적일 뿐, 상업적 의도는 없습니다. 

Source: Introduction to Algorithms 3rd Ed., by Cormen, Leiserson, Rivest, Stein


2-1. Asymtotic Notation


Asymptotic efficiency는, input size가 한계없이 커질 때 running time이 어떻게 늘어나는가를 말한다.

이 Asymptotic notation을 쓸 때는 어느 running time인지를 명확히 해야한다. (Worst case, best case, ...)


Θ-notation의 정의는 아래와 같다.

어떤 f(n)에 대해, 0 <= c1g(n) <= f(n) <= c2g(n) for all n >= n0로 표현될 수 있는 양의 상수 c1, c2, n0가 존재하면,

f(n)은 Θ(g(n))이라고 한다. 즉 n0 이전값들이 그렇지 않더라도, 어떤 n0값 이후부터 f(n)이 g(n)의 상수변환으로 샌드위치 가능하면 Θ(g(n))이다.

이 때 g(n)은 f(n)의 asymptotically tight bound라고 한다. 이 Θ정의는 f(n)의 모든 멤버가 asymptotically nonnegative일 것을 요구한다.


O-notation의 경우 upper bound를 주고, Ω-notation의 경우 lower bound를 준다. 

즉, 어떤 양의 상수 n0와 c에 대해 n0의 우측 모든 f(n)값이 cg(n) 이하에 있으면 f(n) = O(g(n))이라고 한다.

어떤 책에서는 O-notation과 Θ-notation을 혼용하기도 한다.

1) Θ(g(n)) ⊆ O(g(n)) 이고, Θ(g(n)) ⊆ Ω(g(n))이다.

2) f(n) = Θ(g(n))이면 f(n) = O(g(n))이고 f(n) = Ω(g(n))이다. (필요충분조건)


소문자 o-notation의 경우 O-notation과 비슷하지만 모든 c에 대해 0 <= f(n) < cg(n)을 만족할 때를 말한다.

(대문자 O-notation의 경우 어떠한 c에 대해 0 <= f(n) <= cg(n)을 만족할 때를 말한다)

즉, 2n = o(n^2) 이지만 2n^2 != o(n^2) 이다. 

다시 말해 limn->∞ f(n)/g(n) = 0 이다. 

소문자 ω-notation의 경우, o-notation과 마찬가지다. 

o와 ω의 경우, 각각 asymptotically smaller 혹은 larger라는 표현을 사용할 수 있다.


이 notation들은 아래를 만족한다. N을 어떠한 notation이라고 표기하면,

1) Transitivitiy: f(n) = N(g(n))이고 g(n) = N(h(n))이면, f(n) = N(h(n))이다.

2) Symmetry: f(n) = Θ(g(n))이면 g(n) = Θ(f(n))이다. (필요충분)

3) Transpose symmetry: f(n) = O(g(n))이면 g(n) = Ω(f(n))이고, f(n) = o(g(n))이면 g(n) = ω(f(n))이다. (필요충분)



2-2. 알고리즘 디자인


다양한 알고리즘 디자인 방법들이 있다. Insertion sort에는 'incremental approach'를 사용했다.

이 섹션에서는 'divide-and-conquer'라는 방법을 알아본다. 이 방법의 장점은 worst case running time이 쉽게 계산된다는 것이다.


많은 유용한 알고리즘들은 구조상 recursive한 경우가 있는데, 일반적으로 divide-and-conquer 방식을 따른다.

Divide: 한 문제를 다수의 subproblem들로 나눈다.

Conquer: subproblem들을 recursive하게 푼다. 

Combine: 그 solution들을 합쳐 원래 문제의 solution으로 만든다.


이 방식을 통해 정렬 문제를 풀려면, merge sort 알고리즘을 사용한다.

Divide: n개의 시퀀스를 각각 n/2의 시퀀스 두개로 나눈다.

Conquer: 두개의 subsequence를 merge sort를 이용하여 recursive하게 푼다.

Combine: 두개의 subsequence를 합쳐 sorted 해를 얻는다.


Mergesort의 코드는 다음과 같다.

Mergesort (A, left, right)

if right == left then return

end if

middle = left + [(right - left)/2]

Mergesort (A, left, mid)

Mergesort (A, mid + 1, right)

Merge (A, left, mid, right)


처음 자료를 받아 반으로 나누고, 각 절반에 대해 recursion을 실행하고, 마지막으로 merge를 한다.

아래는 merge 함수의 pseudocode이다.


Merge (A, left, right, mid)

L = A[left, mid]

R = A[mid + 1, right]

Maintain two pointers pL, pR initialized to point to the first elements of L, R, respectively

while both lists are nonempty do

Let x, y be the elements pointed to by pL, pR

Compare x, y and append the smaller to the output

Advance the pointer in the list with the smaller of x, y

end while

Append the remainder of the non-empty list to the output.


L과 R이 sorted라고 가정하고, 각각의 첫번째 수를 비교해서 작은 것부터 차례로 A array에 넣는 함수이다.



2-3. Recurrence의 해


Recurrence의 Θ 혹은 O를 구하는 방법에는 세 가지가 있다.

Substitution method는 bound를 추정 후 수학적 귀납법을 사용해 그 추정이 옳음을 증명한다.

Recursion-tree method는 recurrence를 tree로 바꾼 후 푼다.

Master method는 T(n) = aT(n/b) + f(n) 형식의 recurrences에 bound를 부여한다. (a >= 1, b > 1)

위 형식은 자주 나오는데, 각 1/b 사이즈인 a개의 subproblem을 만들고, divide and combine step이 f(n)시간 걸리는 divide-and-conquer 알고리즘을 표현한다.


가끔 T(n) <= 2T(n/2) + Θ(n)과 같은 부등식이 나오면, 이는 T(n)의 upper bound만 지정해주므로 O-notation로 해를 표현한다.

>= 일 경우에는 그 반대로 Ω로 해를 표현한다.


실제로 recurrences를 풀 때, 작은 n에 대한 컨디션은 생략한다.

즉, n = 1일 경우 T(n) = Θ(1)이고, n > 1 의 경우 T(n) = 2T(n/2) + Θ(n)일 때, 전자는 생략한다.

이는 작은 n에 대해 T(n)은 상수라고 생각하기 때문이다. 

우리가 recurrences를 풀 때 floors, ceilings, 그리고 boundary condition들은 대체로 무시한다.

이들을 무시하고 해를 푼 후 그들이 영향이 있는지를 판단한다. 

그러나 그들이 영향을 준다면 그것을 반드시 알아야 한다.



2-4. Recursion-tree Method


Recursion tree에서, 각 교점(node)는 single subproblem의 cost를 표현한다.

그리고 각 층의 cost를 모두 더해 per-level costs를 구한 후, 모든 per-level costs를 더해 total cost를 구한다.

Recursion tree는 좋은 추정을 얻기 위해 사용하고, 이 추정을 substitution method로 검증해볼 수 있다.


아래는 T(n) = 3T(n/4) + Θ(n2)를 푸는 방식이다.

1.jpg

먼저, floor나 ceiling이 상관없다는 것을 가정하므로 Θ(n2)는 cn2로 대체한다.

그리고 편의를 위해, n이 4의 승수라서 모든 subproblem 사이즈가 정수라고 가정한다.

(a)에서 확장하여 (b)가 되고, T(1)에 도달할 때까지 이를 반복한다.


Depth를 0, 1, 2 순으로 매기면, depth i의 node에서 subproblem의 size는 n/4i 이다.

따라서 subproblem size는 n/4i = 1일 때 마지막에 도달하고, 따라서 i = log4n 이다.

그러므로 level 0을 포함하여 이 tree는 log4n + 1 레벨이 있다.


그 다음, 각 레벨의 cost를 보면 이전 레벨보다 3배로 node가 많으므로 depth i에서 3i개의 node를 가진다.

그리고 subproblem size는 1/4씩 감소하므로, depth i의 개별 node는 c(n/4i)2 이다.

이 둘을 곱하면, 각 층의 cost는 3ic(n/4i)2 = (3/16)in2c 가 된다.

마지막 층은 depth log4n이므로 3^(log4n) = n^(log43)개의 node를 가지며, 각 T(1)의 cost를 가진다.

T(1)는 상수로 가정하므로, 이는 곧 Θ(n^(log43)) 이다.


이제 전체 tree의 cost를 다 더하면, 

2.jpg


위와 같이 정리된다. 마지막 식은 조금 난잡한데, n이 무한히 증가한다고 가정하면 간단히 정리된다.


3.jpg


이제 우리는 T(n)이 O(n2)이라는 결론에 도달했다.

이 결론을 살펴보면, cn2의 coefficient는 decreasing geometric series를 형성하고, 그 합은 상수 16/13이 upper bound임을 알 수 있다.

그리고 root의 total cost에 대한 contribution이 cn2이고, 이는 constant fraction임을 알 수 있다. 즉, cost of root이 tree의 total cost를 dominate 한다.

따라서 Ω(n2)가 lower bound임을 알 수 있고, O(n2)가 upper bound임을 확인하면 Θ(n2)임을 증명할 수 있다.


이제 substitution method를 사용해서 O(n2)가 upper bound임을 확인하려면, 어떤 상수 d에 대해 T(n) <= dn2 임을 증명하면 된다.

4.jpg

그리고 마지막 부분은 d >= (16/13)c 인 한 성립된다.


또 하나의 예로, T(n) = T(n/3) + T(2n/3) + cn 처럼 T가 두 갈래로 나눠지는 예를 보자.

5.jpg

그림에서 보다시피 각 층마다 값을 더하면 cn임을 알 수 있다.

Root에서 leaf으로의 가장 긴 simple path는 n > (2/3)n > (2/3)2n > ... 이고, 

(2/3)in = 1 이려면 k = log3/2n 이므로 tree의 높이는 log3/2n 임을 알 수 있다.

직관적으로, 우리는 이 recurrence의 해의 최대치가 이 높이와 층합을 곱한 cnlog3/2n = O(nlgn)임을 예상할 수 있다.


만일 이 tree가 완벽한 binary tree였다면, leaves의 개수는 2^층수, 즉 2^(log3/2n) = n^(log3/22) leaves를 가진다.

그러므로 모든 leaves의 total cost는 Θ(n^(log3/22))이고, log3/22는 1보다 크므로 Ω(nlgn)임을 알 수 있다.

그러나 이 tree는 완벽한 binary tree가 아니고, T(n/3)이 훨씬 빨리 감소하므로 tree의 아래층에는 많은 node가 빈다.

따라서 O(nlgn)이 성립한다고 추정할 수 있다. (더 엄밀하게 증명가능하지만 스킵하자)


Substitution method를 사용해 O(nlgn)이 upper bound임을 증명하면,

6.jpg

d >= c/(lg3 - 2/3)인 한 위는 성립한다.



2-5. Master Method


Master method는 T(n) = aT(n/b) + f(n) 형식의 recurrence를 푸는데 적합하다.

여기서 a >= 1, b > 1 인 상수들이고 f(n)는 asymptotically positive function이다.

Master method을 사용하기 위해서는 세 가지 케이스를 외워야 한다.

위의 형식은 n size 문제를 각각 n/b size인 subproblem a개로 나누는 걸 표현한다.


아래는 Master theorem의 정의이다. (Source: Introduction to Algorithms 3rd Ed., by Cormen, Leiserson, Rivest, Stein, p.94)

7.jpg

위를 간단하게 풀어쓰자면, T(n) = aT(n/b) + O(nk)일 때 (a, b > 1이고 k >= 0) a와 bk를 비교한다.

Case 1. a > bk면 T(n) = O(n^(logba))

Case 2. a = bk면 T(n) = O(nklogn)

Case 3. a < bk면 T(n) = O(nk)


주의할 점은, Case 1에서 f(n)이 단순히 n^(logba) 보다 작아야하는 것이 아니라, polynomially smaller여야 한다.

즉, theorem 정의에서 보듯이 f(n)은 factor of nε로 n^(logba) 보다 asymptotically smaller여야 한다.

그리고 Case 3에서는 반대로 polynomially larger여야할 뿐만 아니라, regularity condition인 af(n/b) <= cf(n)을 만족해야 한다.

이 regularity condition은 우리가 마주하는 대부분의 polynomially bounded function들에 의해 만족된다.


이 Case들은 f(n)에 대한 모든 가능성을 커버하지 않는다. f(n)이 더 작지만 polynomially 작지는 않거나, 그 반대의 경우가 있다.

이런 경우라던지, Case 3의 regularity condition이 만족되지 않는다면 recurrence를 풀기 위해 master method를 사용할 수 없다.



이제 master method의 사용 예를 보자.

1) T(n) = 9T(n/3) + n

a = 9, b = 3, f(n) = n이므로 n^(logba) = n^(log39) = Θ(n2) 이다. 

ε = 1일 때 f(n) = n^(logba - ε)를 성립하므로, 이것은 Case 1에 해당하며, T(n) = Θ(n2)라고 결론 내릴 수 있다.


2) T(n) = T(2n/3) + 1

a = 1, b = 3/2, f(n) = 1 이고, n^(logba) = 1 이므로 f(n)과 같으며 Case 2다.

따라서 T(n) = Θ(f(n)lgn) = Θ(lgn) 이다.


3) T(n) = 3T(n/4) + nlgn

a = 3, b = 4, f(n) = nlgn 이고, n^(logba) = O(n0.793) 이다.

ε ≒ 0.2일 때 f(n) = Ω(n^log43 + ε)을 만족하므로, Case 3에 해당한다.

충분히 큰 n에 대해 af(n/b) = 3(n/4)lg(n/4)이고, cf(n) = 3/4nlgn 로 두면, lg(n/4) < lgn 이 성립된다.

따라서 regularity condition이 만족되고, 해는 T(n) = Θ(nlgn) 이다.


4) T(n) = 2T(n/2) + nlgn

a = 2, b = 2, f(n) = nlgn이고, n^(logba) = n 이므로 f(n)이 더 크고, Case 3가 해당한다고 착각할 수 있다.

그러나 문제는 polynomially larger하지 않다는 것이다. f(n)/n^(logba) 의 ratio는 nlgn/n = lgn이고, 

이 lgn은 그 어떤 양의 상수 ε에 대해서도 nε보다 asymptotically 작다. 

댓글 0

목록
번호 제목 글쓴이 날짜 조회 수
공지 [공지]데이터 과학 게시판의 운영에 관하여 최한철 2016.04.23 89
22 [일반]데이터 사이언스 공부 사이트 정리 최한철 2018.09.23 35
21 [계량경제학]Nonparametric Smoothing file 최한철 2018.07.13 23
20 [계산통계학]Convex Functions 최한철 2017.02.14 214
19 [머신러닝]Support Vector Machine 최한철 2017.02.13 198
18 [계산통계학]Automatic Differentiation 최한철 2017.01.23 126
17 [시계열분석-8]시계열 모델과 예측 file 최한철 2016.12.04 192
16 [시계열분석-7]자기상관과 AR모델 file 최한철 2016.12.04 920
15 [시계열분석-6]추세의 모델링 file 최한철 2016.12.04 129
14 [회귀분석-5]회귀분석 결과의 해석 file 최한철 2016.12.03 123
13 [회귀분석-4]변수 선택 및 모델의 진단 file 최한철 2016.12.03 688
12 [회귀분석-3]다중 회귀 분석 II file 최한철 2016.10.12 75
11 [회귀분석-2]다중 회귀 분석 file 최한철 2016.10.09 560
10 [알고리즘-7]그래프의 최단 거리 최한철 2016.10.09 86
9 [알고리즘-6]DFS의 응용 file 최한철 2016.09.29 391
8 [회귀분석-1]기본 회귀 분석 file 최한철 2016.09.25 306
7 [알고리즘-5]BFS의 응용 file 최한철 2016.09.19 384
6 [알고리즘-4]그래프 file 최한철 2016.09.18 869
5 [알고리즘-3]Master Theorem file 최한철 2016.09.15 303
» [알고리즘-2]알고리즘 디자인 file 최한철 2016.09.10 338
3 [알고리즘-1]알고리즘의 정의 최한철 2016.09.08 222