[컴퓨터알고리즘] 4장 - (2) 분할정복기법

재귀적인 탐색.
 
Binary Search: (1) 분할 (2) 정복 (3) 결합
- 피보나치 수열
 
Binary Search Tree: 문제는 하나, 부분 문제들로 잘려진다.
- 매 단계마다 찾는 key값과 중간값이 같은지 본다. (상수번 반복이라 Θ(1))
- (1) 같 = stop (2) 작 = 왼 sub arr, (3) 큼 = 오 sub arr
- 시간복잡도 Θ(lgn)
 
BST의 점화식
T(n) = T(n/2) + Θ(1)
- 부분 문제의 개수 1개므로 a=1.
- 부분 문제의 크기 n/2이므로 b=2
- 결합의 시간복잡도 Θ(1)
마스터정리 case 2.  Θ(lgn)

# 수도 코드
BinarySearch(A[1..N], value) {
    if (N == 0)
    	return -1; // not found
  mid = (1+N)/2;
    if (A[mid] == value)
    	return mid; // found
    else if (A[mid] > value) // 작은 쪽을 탐색
    	return BinarySearch(A[1..mid-1], value);
    else
    	return BinarySearch(A[mid+1..N], value); // 큰 쪽을 탐색
}

 
지수함수 a^n
- n이 짝수면 a^(n/2) * a^(n/2)
- n이 홀수면 a^(n/2) * a^(n/2) * a
지수함수의 점화식: T(n) = T(n/2) + Θ(1). 시간복잡도 Θ(lgn)

Power (x,n)
    if n == 0
    	return 1
    else if n % 2 == 0
    	return Power(x*x, n/2)
    else
    	return x * Power(x*x, (n-1)/2)
        
/* // c언어
int Power (int x, int n) {
    if (n == 0)
    	return 1;
    else if (n % 2 == 0)
    	return Power(x*x, n/2);
    else
    	return x * Power(x*x, (n-1)/2);
}
*/

 
피보나치 수열
Fn = { 0   // n=0
          1   // n=1
          F(n-1) + F(n-2) // n>=2
 
프로그램 분할정복으로 작성하면 안 된다!
C언어로 작성

// 동적 계획법
int dFib(int n)
{
    if (n==0) return 0;
    if (n==1) return 1;
    int pp = 0;
    int p = 1;
    int current;
    for (int i = 2; i <= n; i++)
    {
    	current = p + pp;
        pp = p;
        p = current;
    }
    return current;
}

// 캐시 메모리
int memo[100] = {0};

int mFib (int n)
{
    if (memo[n] != 0)
        return memo[n];
    if (n==1 || n==2)
    	memo[n] = 1;
    else
    	memo[n] = mFib(n-1) + mFib(n-2);
    return memo[n];
}

 
행렬곱
cij = (k는 1부터 n까지) aik * bkj
일반 분할정복: T(n) = 8T(n/2) + Θ(n^2) -> 시간복잡도 Θ(n^3)
스트라센 방법: 7개 행렬을 계산.T(n) = 7T(n/2) + Θ(n^2) -> 시간복잡도 Θ(n^(lg7))