[알고리즘] 점화식과 점근적 복잡도 분석

점화식

어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다.

예시

an = an-1 + 2

f(n) = n f(n−1)

f(n) = f(n−1) + f(n−2)

f(n) = f(n/2) + n

 

점화식의 점근적 분석 방법 (반복 대치, 추정 후 증명, 마스터 정리)

반복 대치

더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법이다.

 

기본 개념

T(n) = T(n−1) + c

T(1) ≤ c

T(n) = T(n−1) + c

= (T(n−2) + c) + c = T(n−2) + c + c

= (T(n−3) + c) +  c + c = T(n−3) + c + c + c

…

= T(1) + (n −1)c

≤ c + (n −1)c

= cn

 

예시1

T(n) = T(n−1) + n

T(1) = 1

 

T(n) = T(n−1) + n

= (T(n−2) + (n−1)) + n

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

…

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

= 1 + 2 + … + n

= n(n+1)/2

= Θ(n^2)

 

예시2

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

T(1) = 1

 

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

= 2(2T(n/2^2) + n/2) + n = 2^2T(n/2^2) + n + n 

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

…

= 2^kT(n/2k) + kn    (n = 2^k로 가정, k = log_2 n)

= n + nlogn

= Θ(nlogn)

 

[예제1] 반복대치로 재귀식의 닫힌 형태를 구하시오

W(1) = 1, W(n) = W(n/2) + 1

W(1) = 3, W(n) =  2W(n/2) + n – 1

W(1) = 5, W(n) =  W(n-1) + n - 1

 

T(1) = 1, T(n) =  8T(n/2) + 4(n/2)2

 

 

※Tip

입력의 개수 n이 2^k라고 가정하고 점근적 복잡도를 계산해도 되는가?
입력의 개수 n이 3^k라고 가정하고 점근적 복잡도를 계산해도 되는가? 
일반적인 n에 관한 점근적 복잡도와 2^k인 n에 관한 점근적 복잡도는 같은가? 
일반적인 n에 관한 점근적 복잡도와 3^k인 n에 관한 점근적 복잡도는 같은가? 

1. 아무 n이든지 n에 관한 점근적 복잡도와 2n에 관한 점근적 복잡도는 같다. (점근적 복잡도가 다항식이라는 가정 필요)
예를 들어 n에 관한 점근적 복잡도가 O(n^3)이면 2n에 관한 점근적 복잡도는 O(8 n^3)이다. 
예를 들어 n에 관한 점근적 복잡도가 O(n^r)이면 2n에 관한 점근적 복잡도는 O(2^r * n^r)이다. 
2. 아무 n이든지 n<=2^{k}<2n 인 k를 찾을 수 있다. 
3. 아무 n이든지 n에 관한 점근적 복잡도와 2^k에 관한 점근적 복잡도와 2n에 관한 점근적 복잡도는 같다

 

추정후 증명

결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법이다.

 

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

<추정> T(n) = O(n log n), 즉 T(n) ≤ cn log n

<증명>

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

≤ 2c(n/2) log(n/2) + n

= cn logn − cn log2 + n

= cn logn + (−c log2 + 1)n

≤ cn logn (만족하는 c 존재)

 

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

<추정> T(n) = O(n), 즉 T(n) ≤ cn

<증명>

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

≤ 2c(n/2)  + 1

= cn  + 1 (추정에 맞지 않음)

 

<추정> T(n) ≤ cn - 2

<증명>

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

≤ 2(c(n/2) - 2) + 1

= cn  – 3

≤ cn  – 2 (만족하는 c 존재)

 

마스터 정리

형식에 맞는 점화식의 복잡도를 바로 알 수 있다.

T(n) = aT(n/b) + f (n)와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 결과를 알 수 있다

n^(log_b a) = h(n)이라 할 때

① 어떤 양의 상수 ε에 대하여 f(n)/h(n) = O(1/n^ε)이면, T(n) = Θ(h(n))이다.

② 어떤 양의 상수 ε에 대하여 f(n)/h(n) = Ω(n^ε)이고, 어떤 상수 c(< 1)와 충분히 큰 모든 n에 대해 af(n/b) ≤ cf(n)이면 T(n) = Θ(f(n))이다.

③ f(n)/h(n) = Θ(1)이면 T(n) = Θ(h(n) logn)이다.

 

직관적 의미

① h(n)이 더 무거우면 h(n)이 수행 시간을 결정한다.

② f(n)이 더 무거우면 f(n)이 수행 시간을 결정한다.

③ h(n)과 f(n)이 같은 무게이면 h(n)에  logn을 곱한 것이 수행 시간이 된다.

 

기본개념

다음 두 문제가 해결되는 과정을 그림과 같이 설명한다. (리프 노드의 문제 크기가 1이 될때까지 해결한다)

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

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

정리하면 T(n) = aT(n/b) + f(n) 이라는 점화식은 한 레벨을 내려올때마다 1/b로 줄어든, 자식이 a개인 T(n/b)로 이루어진다. 총 비용에서 Θ(n^logb(a)는 리프 노드 Θ(1)을 모두 더한 결과이며 Σ(j=0 -> logb(n-1)의 a^j*f(n/b^j)는 f(n)부터 리프 노드의 바로 위의 문제까지 더한 결과이다. 따라서 이 두 비용 중 더 큰 값이 시간복잡도로 결정되며 두 비용이 비슷하다면 logb(n)을 곱한 값이 시간복잡도가 된다.

 

정리 적용

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

a=2, b=3, h(n) = n^(log_3 2), f(n) = c

T(n) = Θ(n^(log3 2))

 

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

a=2, b=4, h(n) = n^(log_4 2), f(n) = n

T(n) = Θ(n)

 

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

a=b=2, h(n) = n^(log_2 2) = n, f(n) = n

T(n) = Θ(nlogn)

 

마스터 정리를 적용한 추정후 증명 예상문제1

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

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

T(n) = 8T(n/2) + n^2

T(n) = 7T(n/2) + 4.5n^2

T(n) = 4T(n/2) + 50n^2 

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

 

마스터 정리를 적용한 추정후 증명 예상문제2

sample(A[], n) {
	if (n = 0 or n = 1) return 1;
    return (n + sample(A, n-2));
}

T(n) = T(n-2) + c로 하는게 맞지만 편의상 +1로 해도 됩니다. 영향 없습니다.

sample(A[], n) {
	if (n = 1) return 1;
    sum <- 0;
    for i <- 1 to n
    	sum <- sum + A[i];
    tmp <- sum + sample(A, n-1);
    return tmp;
}

sample(A[], n) {
	if (n = 1) return 1;
    sum <- 0;
    for i <- 1 to n
    	sum <- sum + A[i];
    tmp <- sum + sample(A, n/3);
   	return tmp;
}

sample(A[], p, r) {
	if (p = r) return 1;
    sum <- 0;
    for i <- 1 to n
    	sum <- sum + A[i];
    q <- ⌊(p+r)/2⌋;
    tmp <- sum + sample(A, p, q) + sample(A, q+1, r);
    return tmp;
}

sample(A[], p, r) {
	if (p = r) return 1;
    q <- ⌊(p+r)/2⌋;
    tmp <- sample(A, p, q) + sample(A, q+1, r);
    return tmp;
}

sample(A[], p, r) {
	if (p = r) return 1;
    q <- ⌊(p+r)/2⌋
    tmp <- sample(A, p, q);
    if (random(1, 100) <= 50) then tmp <- tmp + sample(A, q+1, r);
    return tmp;
}

sample(A[], p, r) {
	if (n=1) return 1;
    q <- ⌊(r-p+1)/3⌋;
    tmp <- sample(A, p, p+q-1) + sample(A, p+q, p+2q-1) + sample(A, p+2q, r);
    return tmp;
}

sample(A[], p, r) {
	if (p >= r) return 1;
    sum <- 0;
    for i <- p to r
    	sum <- sum + A[i];
    q <- ⌊(r-p+1)/3⌋;
    tmp <- sum + sample(A, p, p+q-1) + sample(A, p+2q, r);
    return tmp;
}

int sample(n) {
	if (n <= 1) then return 2;
    else {
    	tmp = 0;
        for = 1 to n
        	{ tmp++; }
        return (sample(n/3) + sample(n/3) + sample(n/3));
    }
}