컴퓨터 알고리즘 중급

1강 컴퓨터 알고리즘 성능분석(1)

1. 컴퓨터 알고리즘 성능분석

- 컴퓨터 알고리즘

컴퓨터 알고리즘의 정의 : 문제를 해결하기 위한 과정을 상세하게 단계적으로 표현한 것으로 입력과 출력으로 문제를 정의

단계	내용
문제정의	현실 세계의 문제를 컴퓨터를 이용하여 풀 수 있도록 입력과 출력의 형태로 정의
알고리즘 설명	문제를 해결하기 위한 단계를 차례대로 설명
정확성 증명	항상 올바른 답을 내고 정상적으로 종료되는지 증명
성능분석	수행시간이나 사용공간에 대한 알고리즘의 성능을 비교하기 위한 분석

- 컴퓨터 알고리즘의 성능분석

특정 기계에서 수행 시간을 측정하는 방법 : 현실적으로 불가능

절대적 시간을 측정하여 비교하는 방법 : 공정한 비교가 불가능

위 두가지를 해결하기 위해 → 점근적 표기법 사용 (Asymptotic notations)

점근적 표기법이란?

O - notation (빅오 표기)

Ω - notation (오메가 표기)

Θ - notation (쎄타 표기)

→ "T(n)으로 표현하고 최고차 항만 고려"

- 재귀함수에 대한 성능분석

T(n) =	Θ(1)              if n=1
	2T(n/2)+Θ(n)   if n>1

→ "T(n)에 대한 수식으로 표현하는 것이 쉽지 않음."

그래서 아래와 같은 방법이 나왔음.

대체법 (Substitution Method) : T(n)이라고 하는 함수에다가 생각하는 값을 집어넣어서 확인하는 방법

리컬젼 트리 매소드 (Recursion-tree Method) : 재귀 함수를 트리형태로 그려보고 트리에 나오는 값을 확인하는 방법

마스터 매소드 (Master Method) : 함수의 값이 aT(n)+b 와 같이 나왔을 때 a와 b의 값을 통해 값을 확인하는 방법

2. 대체법(Substitution Method)

- 대체법(Substitution Method)을 통한 성능분석 : 해답의 형태를 추측 → 수학적 귀납법을 이용하여 추측한 해답이 맞음을 증명

Question:) 다음 재귀식에 대한 점근적 상한의 시간복잡도를 구하시오.

→ T(n) = 2T( [n/2] ) + n

→ 추측 : T(n)=O(n lg n)

→ 증명 : T(n) <= cn lg n 적절한 상수 c를 설정

T( [n/2] ) <= c[n/2] lg( [n/2] )에 대해 성립하는지 증명 (T(n)<=cn lg n이라고 추측했었음 )

T(n) <= 2(c[n/2] lg( [n/2] )) + n

<= cn lg(n/2) + n (log의 성질을 통해 lg(n/2)일 경우 lg n - lg 2로 표현할 수 있음)

  = cn lg n - cn lg 2 + n (여기에 나온 lg2는 밑수가 2인 로그이기 때문에 1이 된다.)

  = cn lg n - cn +n (cn이큰지? n이큰지 비교할 때 c를 상수라고 생각을 하면 해당 공식은

    cn lg n보다 작거나 같다는 것을 알 수가 있다.)

<= cn lg n             

(as long as c>=1)

적절한 c를 설정 

T(n) = cn lg n

n=1, T(1) = c1 · lg1 = 0 (판단하기가 힘들다)

n=2, T(2) = c2 · lg2 = 2c    <= 4 (c가 2라고 생각했을 때 4보다 작다)

n=3, T(3) = c3 · lg3 = 4.8c  <= 5 

n=4, T(4) = c4 · lg4 = 8c    <= 8

남은 것은 n0이가 어디냐? 즉 시작점은 어디인지, 이때 만족하는 c값을 설정해주면 된다.

학습정리 컴퓨터 알고리즘 성능평가 : 문제를 해결하는 알고리즘은 여러 종류가 있을 수 있는데 이 중에서 가장 적합한 것을 고르기 위해서는 성능 평가와 비교가 필요하며 이를 위해서 상대적 평가를 할 수 있는 점근적 표현법이 사용됨 대체법(Substitution Method) : 재귀알고리즘은 T(n)으로 간단히 계산하기가 쉽지 않기 때문에 추측을 통해 대체법을 이용하여 수학적 귀납법을 증명하는 방법을 이용함.

2강 컴퓨터 알고리즘 성능분석(2)

1. 재귀 함수와 재귀 트리

  재귀트리를 이용하는 방법은 먼저 주어진 함수에 값을 추측하고, 추측한 값을 대체법을 이용하여 증명하는 방법이다.

- 재귀 함수에 대한 성능 분석

재귀 함수라는 것은 일반적으로 점근적 표기법(Asymptotic notations) 으로 표현할 수 없는 경우가 많다 그 이유는 아래의 표와 같이 T(n)이 자기자신의 입력값만 바뀌로 자기자신을 호출하기 때문이다. 그래서 이것을 일반적인 다차식으로 변환하는 과정이 필요한데 그 방법이 대체법 (Substitution Method), 리컬젼 트리 매소드 (Recursion-tree Method), 마스터 매소드 (Master Method)이다.

T(n) =	Θ(1)              if n=1
	2T(n/2)+Θ(n)   if n>1

재귀 함수의 성능 분석을 위해 재귀 트리를 이용할 때는 적절한 해답을 찾기 위해 좋은 추측을 하는 것

좋은 추측은 대체법을 통해 증명하고, 재귀함수의 성능을 분석

Question) T(n) = 3T ( [n/4] ) + Θ(n제곱)

→ T(n) = O(n제곱) 임을 보이시오.

→ 재귀 함수를 이용한 추측

→ 대체법을 이용한 증명

- 트리에서 각 노드는 각 하위 문제에 대한 비용을 표현

- 트리에서 레벨에 속한 노드들의 합은 레벨의 총비용을 표현

- 트리의 각 레벨의 비용을 모두 더하면 재귀 트리 전체의 비용

T(n) = 3T ( [n/4] ) + Θ(n제곱) 해당 식은 

T(n) = 3T ( [n/4] ) + c(n제곱) 이며 아래와 같이 트리로 표현할 수 있다. 

c(n제곱)
/	|	＼
T(n/4)	T(n/4)	T(n/4)

이 식에서 n대신에 (4/n)을 집어 넣으면 T(n/4) = 3T( n/(4제곱) ) + ( (n/4)제곱 )이나오고 다시 트리로 표현하면 이와 같이 나온다.

c(n제곱)
/			|			＼
T(n/4)			T(n/4)			T(n/4)
/	|	＼	/	|	＼	/	|	＼
T(n/16)	T(n/16)	T(n/16)	T(n/16)	T(n/16)	T(n/16)	T(n/16)	T(n/16)	T(n/16)

이 작업을 반복을 하면 root는 c(n제곱)이고 그의 자식들은 계속 1/4씩 나누어 지면서 뻗어나간다.

해당 그림에서 각 노드들은 cost 이고, cost들을 합한 것이 level당 cost 값이며, 각 level 들의 합은 전체 트리의 cost 값이다. 그러면 첫 번째로 해야할 것은 각노드들의 값이 나왔으니 각 level들의 값을 구해야 한다. 그러면 총 몇 level인지를 살펴봐야 한다.

- Subproblem size for a node at depth i : n/(4의 i승) 

(level이 i라고 했을 때 node 하나의 크기는 얼마인가? level이 하나씩 늘어날 때마다 1/(4의i승)씩 늘어난다.)

- The number of nodes at depth i : 3의 i승

(level이 늘어남에 따라 node의 갯수는 3의 배수로 늘어난다 [ 3T(n/4) ] )

- The number of levels : log4의 n + 1 (총 높이는 몇개인가?)

(level의 갯수는 몇개인가? n이 1이 될 때까지의 값을 구하면 되기 때문에, h = (4의i승)에 로그를 취하면 log4의 n + 1이 나오고 여기서 1은 최소에 n이 전체 입력으로 주어졌을 때이다, 즉 t(n)일 때 때문에 1을 더해준다. )

- The number nodes at the last level : n의 (log4의 3)승

(마지막단, 즉leaf단 에서 leaf node는 총 몇개 인가를 구하는 것이다. 매번 3개씩 증가하면서 1/4만큼 값이 감소하기 때문에 값이 n의 (log4의 3)승 이 나온다)

- 각층의 값을 구하면 leaf 단의 값은  n의 (log4의 3)승 높이는 log4이다.

제일 높은 층의 값이 c(n제곱)

두번 째 층의 값이 3c(n/4)제곱

세번 째 층의 값이 9c(n/16)제곱이며 이는 층을 내려갈 수록 (3/16)를 곱해나가기 때문에

제일 높은 층의 값 c(n제곱) →  c(n제곱)

두번 째 층의 값 3c(n/4)제곱  →  (3/16) c(n제곱)

세번 째 층의 값 9c(n/16)제곱  →  ( (3/16)의 제곱 ) c(n제곱) 으로 표현할 수 있으며

leaf 노드까지 가면 상단에 구한 Θ(n의 (log4의 3)승) 값을 더해주면 된다.

- 그러므로 T(n) =  c(n제곱) + (3/16) c(n제곱) + ( (3/16)의 제곱 ) c(n제곱) + … + Θ(n의 (log4의 3)승)     으로 표현할 수가 있다.

- 위기 식은 (3/16)의 등비수열이기 때문에 T(n) = [ log4의 (n-1) 시그마 i=0 ] + Θ(n의 (log4의 3)승) 

    으로 표현할 수가 있다.

- 처음에 문제에서 구하라는 값이 T(n) = O(n제곱) 임을 보이시오. 이기 때문에

     [ log4의 (n-1) 시그마 i=0 ] 식이 어느만큼 커질 것인가를 생각하면 된다.

|x|<1, [∞ 시그마 k=0] X의 k승 = 1 / (1 - x)

x의 절대값이 1보다 작다고 했을 때 x의 지수승을 모두 무한대로 더하면 결국 1 / (1 - x) 이라는 등비수열의 합공식과 같게 된다.

- T(n) = [ log4의 (n-1) 시그마 i=0 ] + Θ(n의 (log4의 3)승)  (주어진 식 정리를 하자면)

빅오를 구하는 것이기 때문에 시그마가 무한대로 가도 된다. 그러므로

[ log4의 (n-1) 시그마 i=0 ]는 (1 / ( 1- (3/16)))c(n의제곱)이며

  =  (1 / ( 1- (3/16)))c(n의제곱) + Θ(n의 (log4의 3)승)

  = (16/13)c(n의제곱) + Θ(n의 (log4의 3)승)

여기서 최고차항만 따지면 앞은 2고 뒤는 1이기 때문에

  = O(n의제곱) (이라고 할 수 있다.)

- 여기까지 했으면 해당식이 O(n의 제곱)이라고 리컬젼 트리 매소드 (Recursion-tree Method)을 통해서 추측만 한 것이기 때문에 대체법(Substitution Method)으로 증명을 시작하면 된다. 그럼 지금까지 무엇을 한거냐고 물어본다면 해당식을 트리방식으로 만들어서 각 노드들의 합을 구한 후 노드들의 합인 level의 합을 구해서 해당값이 O(n의제곱)이랑 같을 것이다라고 좋은 추측을 할 수 있다는 것을 알게 된 것이다.

- T(n) = 3T ( [n/4] ) + Θ(n제곱) 해당식이 O(n의제곱)이라는 것을 증명하려면 

T(n)<=d(n의제곱) (d>0, c>0) 라는 것을 생각할 수가 있다.

- T(n) <= 3T ( [n/4] ) + Θ(n제곱) 여기에 3T ( [n/4] )는 3d( [n/4]의제곱 )으로 

Θ(n제곱은 c(n제곱) 바꿔서 증명을 시작한다.

  <= 3d( [n/4]의제곱 ) + c(n제곱)

  <= 3/16d(n의제곱) + c(n제곱) (단순한 수학적인 계산을 하였음)

  <= d(n의제곱) (여기서 d(n의제곱)라고 말할 수 있는 이유는 d가 c보다 크기 때문이며)

더 정확하게 가려면 d>=(16/13)c을 만족할 때 T(n) <= d(n의제곱) 이 성립된다고 할 수가 있다.

학습정리 재귀 트리를 이용한 성능 분석 : 재귀 함수의 성능 분석을 위해 재귀 트리를 그려 해답을 추측하고, 이를 대체법을 이용하여 증명하는 방법이 있음

3강 확률분석(1)

1. Hiring 문제를 이용한 확률분석

- Hiring problem의 정의 : 지원자 중 가장 뛰어난 직원을 고용하려고 할 때, 최소의 비용을 계산하는 문제

1. 지원자를 매일 1명씩 인터뷰

2. 면접 후에 지원자 고용여부를 즉시 판단

3. 지원자를 고용하면 기존의 직원은 해고

→ 지원자를 인터뷰 할 때마다 인터뷰 비용 지불 Ci

→ 지원자를 고용할 때마다 고용 비용 지불 Ch

- Hiring problem의 수도코드

HIRE-ASSISTANT(n) (n은 인터뷰의 숫자)

best ← 0 (candidate 0 is a least-qualified dummy candidate) (가장 좋은 사람이 제일 처음에는 0값으로 설정이 되어 있어야 그 다음으로 오는 사람들이 best로 설정이 되어서 가장 좋은 사람들을 쉽게 선택할 수 있다. 그리서 가장 least-qualified를 뽑게 된다. )

for i ← 1 to n

do interview candidate i

if candidate i is better than candidate best

then best ← i (candidate i is better than candidate best) (best보다 더 좋은 best가 오면 그사람을 고용을 한다.)

hire candidate i

- Hiring problem의 비용계산

	인터뷰	고용
횟수	n	m
1회 비용	Ci	Ch
전체 비용	n·Ci	m·Ch

- 인터뷰 비용 Ci는 고용비용Ch에 비해 매우 낮음

인터뷰 횟수는 n번 → 고정

고용 횟수 m번 → 변동

→ 고용비용 m·Ch를 최소로 만들면 전체 비용이 최소됨

- 최악의 경우는 ①모든 인터뷰어를 고용하는 경우로

m=n이고 비용은 m(Ci + Ch)

②인터뷰를 받으러 오는 사람들이 뒤쪽으로 갈수록 점점 더 우수한 사람들인 경우로 오름차순으로 정렬된 경우 

→ 이런 경우가 발생할 수 있지만 확률은 매우 낮음

→ n명의 후보자들이 오름차순으로 정렬될 확률은 1/n

- 평균적인 경우에 대한 확률적 분석이 필요

- 가장 우수한 사람이 첫 번째 오는 경우의 수 x 비용

- 가장 우수한 사람이 두 번째 오는 경우의 수 x 비용

- 가장 우수한 사람이 세 번째 오는 경우의 수 x 비용

       ... ...

- 가장 우수한 사람이 n 번째 오는 경우의 수 x 비용

- Indicator Random Variables

X를 고용횟수의 m에 대한 변수라고 하고

x를 경우의 수, Pr{X=x}를 각 경우의 확률이라고 하면

x의 범위는 1부터 n이므로 기대값 E[X]는 다음과 같다.

E[X]= [n 시그마 x=1] x Pr {X =x } 

위의 식은 X 모든 고용횟수에 대한 기대값이라는 것은 각각의 경우의 수에다가 확률 값을 곱하고 그 경우가 1번 부터 n번까지 모두 올라가는 경우라고 볼 수 있다.

여기까지는 Indicator Random Variables가 적용된 것이 아니며 위의 식은 → 계산이 쉽지 않다

Indicator Random Variables를 적용하기 위해서 Xi를 정의를 하고

Xi는 i번째 인터뷰가 고용되는 경우에 대한 indicator random variable이라고 하면

Xi = I{candidate i is hired}	{	1 if candidate i is hired,	}
		0 if candidate i is not hired,

i번째 사람이 고용이 되면 1 그렇지 않으면 0

그러므로 우리가 찾고자 하는 인터뷰에 대한 고용횟수를 구하는 식인

X = X1 + X2 + X3 + ... + Xn  이 나온다.

- i번째 인터뷰이가 고용되는 경우는 1번째부터 i - 1 번째 인터뷰이가 i 번째 인터뷰이 보다 우수하지 않은 경우이므로 확률은 1/i   즉, E[Xi] = Pr { candidate i is hired } = 1/i