[Algorithm] 분할 정복법(Divide Conquer)

>분할 정복법

최종 해를 구하기 위해서 최종 해의 절반씩 분할해가며 값을 구하는 방법

>거듭 제곱 구하기에 응용

Math.pow를 사용하지 않고 거듭제곱을 구하려면, 기본적으로 반복문을 exponent만큼 실행시켜 base를 곱해주면 될 것이다. 따라서 시간 복잡도는 O(n)이 될 것이다.

하지만 분할 정복법을 응용하여 문제를 해결한다면 시간 복잡도를 O(lonN)으로 획기적으로 단축시킬 수 있다.

 

>그림 설명

아래 처럼 지수가 홀수일 때, 짝수일 때로 경우가 나뉠 수 있다.

기본적으로는 최종 해의 지수의 절반인 해를 두 개 구하는 것이다. (분할 정복법)

이를 구현하기 위해서는 재귀 함수가 적합할 것이다.

참고 링크
https://about-tech.tistory.com/entry/Algorithm-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5-%EA%B1%B0%EB%93%AD%EC%A0%9C%EA%B3%B1-%EB%B6%84%ED%95%A0%EC%A0%9C%EA%B3%B1-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Javascript