The divide and conquer method works as follows, divide big problem into smaller sub problems; conquer each sub problem separately; merge the solutions of the sub problems into the solution of the big problem.
Usually, better running times are obtained when the size of the subproblems are roughly equal. To write a recursive algorithm, find how the problem can be broken up into smaller problems of the same nature. Remember the base case!
Scope: Divide and conquer is used to solve difficult problems, such as the classic Tower of Hanoi puzzle, sorting, calculation of the FFT(Fast Fourier Transformation), DSP(Digital Signal Processing) where you need parallelism for math calculations, other parallelism applications, to make efficient use of memory caches (the reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory).
Fast power calculation: For example to calculate the power of some number normally we would multiply it each time with itself, so a^5=a*a*a*a*a. There is a much faster divide-and-conquer method, using the simple formula a^n=a^(n/2) * a^(n/2). What makes this approach more efficient is that once we compute the first factor a^(n/2), we can compute the second factor a^(n/2) using at most one more multiplication.
using namespace std;
int FastPower(int a, int power) //the extra fast power calculation routine
{
if(power==1) //if power equals 1 then return just a
return a;
else
{
int x=FastPower(a,power/2); //else call the same routine, on the divded power by 2
if(power%2) //if it is odd then return x*x*a
return x*x*a;
else //else if it is even then return x*x
return x*x;
}
}
int main()
{
cout<< FastPower(2,11) << endl; //call the routine for the extra fast power
}
No Responses to “The Divide and Conquer algorithm/method”
Please Wait
Leave a Reply