분할 정복에 관한 메모

 

백준 1629번을 통하여 알아낸 것

결론적으로 위와같이 나누기를 하여도 값은 동일하다.

 

 

그리고 분할정복을 할 때 아래와 같은 트리의 형태로 볼 수 있다.

몇단계까지 분할될지는 어떻게 알 수 있을까?

아래의 트리는 4단계로 나누어져있다. 

만약 최상위 루트 N이 16이라면 간단히 logN으로 단계를 구할 수 있다.

 

.

 

0단계: 1 * O(N)

1단계: 2 * O(N/2)

2단계: 4 * O(N/4)

m단계: 2^m * O(N/(2^m)) = O(N)

 

그리고 위에서 말했듯이 단계를 구하는 식은 O(logN)

이를 곱해서 O(NlogN)이라는 시간복잡도를 구할 수 있다.