[#2-1]분할 정복-예제: 수열의 빠른 합과 행렬의 빠른 제곱

분할 정복의 첫 번째 예제이다. 

책 앞에 분할 정복에 대한 설명은 자세히 설명되어 있으므로 생략하겠다.

 

첫 번째 예제인 수열의 빠른 합과 행렬의 빠른 제곱을 구하는 문제인데 우리는 이 문제를 분할 정복으로 풀기 위해서 1+2+.... N까지의 합을 반으로 쪼갤 것이다. 그러면

반으로 쪼갰다는 의미

이렇게 보기 좋은 식이 나온다.

 

그런데 우리는 분할정복을 해야 하니까 기저 사례로 가서 1로 만나면 분할이 완료가 되었다고 코딩을 해야 하는데 저렇게 되어버리면 ((n/2)+1).....+ N) 부분이 a부터 b까지의 합 형식으로 표현이 되어 있어서 분할 정복으로 사용하기 불편하므로 식을 바꿔주어야 한다.

 

두 번째 수식 바꿔주기

위에 나온 식을 첫 번째 사진 fastSum(x) 형식으로 바꾸어 주면?

 

이렇게 식이 정리되고 밑에 사진처럼 정의할 수 있다.

1 2 3 4 5 6 7 8

int fastSum(int n){     //기저사례     if (n == 1)          return 1;     if (n % 2 == 1)          return fastSum(n - 1) + n; //홀수일경우     return 2 * fastSum(n / 2) + (n / 2) * (n / 2); //짝수일경우 } Colored by Color Scripter

cs

위 식은 짝수를 기준으로 분할 정복을 설립한 거라 홀수일 경우에는 -1을 해준 다음에 마지막에 빼준값을 더 해준다.

위의 재귀 함수 식이 어떻게 흘러가는지 확인해 보면 이렇다

사진을 보면 재귀 호출을 할 때 n의 이진수 자리의 표현이 1이면 0으로 바뀌고 0이면 끝자리가 없어진다는 것을 알 수 있다. 따라서 이 함수의 알고리즘 복잡도는 이진수 표현의 자릿수 첫자리를 제외하고 나타나는 1의 개수가 되고 두 값의 상한은 모두 logn이므로 이 알고리즘의 실행 시간은 O(logn)이다.