[알고리즘] 분할 정복을 사용할 수 없을 때 (When not to Use Divide and Conquer)

가능하다면 다음 두 가지 경우에 대해서는 분할 정복을 피해야 합니다.

• instance of size N is divide into two or more instances each almost size n.
  • 크기가 n인 사례가 거의 n에 가까운 두 개 이상의 사례로 분할될 때
  • 이렇게 분할하면 지수 시간 알고리즘이 나옵니다.
• instance of size N is divied into almost n instances of size n/c, where c is a constant
  • 4개로 쪼갰는데, 다시 4번의 재귀할 때, 혹은 2개로 쪼갰는데, 2번 재귀할 때
  • 이렇게 분할하면 \(n^{\Theta(nlgn)}\)의 알고리즘이 나옵니다.

 

만약 피보나치수열을 재귀적인 방법 즉, 분할 정복을 이용해서 문제를 해결했다면, 지수 시간 알고리즘이 나옵니다.

왜냐면 n-1과 n-2로 또 분할해서 계산하기 때문입니다.

이럴 때는 분할 정복을 사용하면 안 됩니다.

 

하지만 반복문을 이용한다면 1차식입니다.

 

반면에 때로는 지수 시간으로 풀어도 괜찮은 문제들이 있습니다.

 

대표적인 예로 하노이 탑입니다.

하노이 탑 문제는 본질적으로 지수 시간 알고리즘입니다.

이를 intrinsically exponential algorithm이라고 합니다.

지수 시간 이하로 시간을 줄일 수 없다는 뜻입니다.

 

아무튼 위의 경우에는 분할 정복을 피하고 다른 알고리즘을 적용해야 합니다.

 

감사합니다.

 

 

 

지적 환영합니다.