알고리즘 기초 (Foundation of Algorithms) 5판, 3장 연습문제

소개

연습문제 2, 4, 5, 6, 13, 15, 17, 20, 22, 26, 28, 36

목차

없음

본문내용

2) 등식(3.1)을 기초로 하여 이항계수문제(알고리즘 3.1)를 푸는 분할정복 알고리즘은 를 구하는데 개의 항을 계산함을 n에 관한 귀납법으로 증명하시오.

T 함수를 몇 개의 항이 계산되었는지 알려주는 함수라고 가정한다.
귀납 기초 :
귀납 가정 :
귀납 절차 : 임을 증명한다.

이항 계수는 위와 같은 특성을 가지기 때문에 아래와 같은 수식이 도출됨을 알 수 있다.

귀납 가정에 의하여

이고, 증명이 완료되었다.

4) 알고리즘 3.2(동적계획법으로 이항계수 구하기)를 인덱스가 0부터 k까지인 배열 하나만 사용하도록 수정하시오.

int combi(int n, int r) {
int i, j;
int B[0..r+1];
int C[0..r+1];
for (i=0; i<=n; i++) {
B[i] = 1;
}
for (i=1; i<=n-1; i++) {
C = B;
for (j=1; j<=i; j++) {
B[j+1] = C[j+1] + C[j];
}
}
return B[k+1];
}

<중 략>

15) 본문의 식(3.5)를 기초로 작성한 분할정복 알고리즘은 지수 시간복잡도를 가짐을 증명하시오.

M[i][j] 에 대해서 i<= k <= j 까지 에서의 최소값을 비교하는 연산을 단위연산으로 볼 수 있다.
여기서 1 <= i <= j <= n 이라는 가정이 있기 때문에, i 는 1 부터 n 까지 루프를 돌 것 이고 그 루프 안에서 j 가 i 부터 n까지 루프를 돌 면서 그 루프 안에서 k 가 i 부터 j-1 까지 최소값을 비교한다.
대입을 이용하여 표현해보면
i = 1 일 때
j = 1 , 2 , 3 , ... , n
k = j가 1 일 때 1번 2 일 때 2번 ,... n 일 때 n번

i = 2 일 때
j = 2 , 3 , ... , n
k = j 가 2일 때 1번 , 3일 때 2번 , .... n 일 때 n-1 번

...

i = n 일 때
j = n
k = j 가 n 일 때 1번

k 루프 가 단위 연산 이므로 k 루프 시행 횟수를 계산해보면
1이 n 번 2 가 n-1 번 ... n 이 1번 나오므로
k(n-k) 식이 성립 한다. 이것을 합공식을 써주면

그러므로 T(n) 이 성립 된다.

참고자료

· 없음