분할정복은 알고리즘 중에서 꽤 강력한 알고리즘이라 할 수 있다.
예를 들어, 2^(2^100)을 구한다고 가정하자. (참값)
2를 2^100번 곱하는 과정을 모두 하는 것은 미친짓은 하지 말자.
컴퓨터로 구하겠다고 하더라도 적당한 수준에서 오버플로가 난다던지 하는 사고가 발생하기도 하고, 무엇보다 시간이 너무 오래 걸린다. 오버플로가 일어나지 않게 잘 정의된 구조라고 할지라도 1000억제곱이라던가하는 큰 수 만큼의 거듭제곱은 하나씩 계산하게 되면 분단위, 시간단위의 시간이 걸린다.
이때 간단하게 해결가능한 알고리즘이 분할정복이다.
예를 들어, 2^8을 계산할 때 2^8=2^4*2^4임을 알고 있다면 2^5, 2^6, 2^7의 참값을 몰라도 2^8을 계산할 수 있다.
2^(2^100)을 구할 때에는 2^(2^99), 2^(2^98), 2^(2^97), ... , 2의 참값만 구하면 된다.
2를 2^100번 곱할 때에는 2^100개의 참값을 알면 됐지만, 분할정복할 때에는 100개의 참값이 필요한 것이다.
일반적으로, k^n제곱을 구할 때 k를 n번 곱할때는 n개의 참값을 구해야 하지만, 분할정복을 이용하면 log n개의 참값만을 구하면 충분하다.
실제로, 5*5보다 작은 정사각행렬은 10^11제곱 이내라면 각 성분이 2^32 이하일 때 1초 내외의 시간으로도 충분하다.
2^31 이하의 a,b에 대해 a^b를 구하는 경우도 0.5초 이내로 충분하다.
실제로 한단계씩 곱하는 알고리즘을 사용하면 1초는 턱도 없이 부족함을 쉽게 알 수 있다.
홀수차수인 경우에는 어떻게 해결할까 하는 문제도 있다.
예를 들어 2^15의 경우에는 2^7*2^7*2로 계산하는것이 실제로 더 효과적이다.
왜그런지는 스스로 알아보자
