|
4.1 Divide and Conquer
There are a number of general and powerful computational strategies that are repeatedly used in http://www.vyomworld.com/gate/cs/ada/4.1.asp# -
The most widely known and often used of these is the divide and conquer strategy.
The
basic idea of divide and conquer is to divide the original problem into
two or more sub-problems which can be solved by the same technique. If
it is possible to split the problem further into smaller and smaller
sub-problems, a stage is reached where the sub-problems are small
enough to be solved without further splitting. Combining the solutions
of the individuals we get the final conquering. Combining need not
mean, simply the union of individual solutions.
Divide and Conquer involves four steps
- Divide
- Conquer [Initial Conquer occurred due to solving]
- Combine
- Conquer [Final Conquer].
In precise, forward journey is divide and backward journey is Conquer. A general binary divide and conquer algorithm is :
Procedure D&C (P,Q) //the data size is from p to q
{
If size(P,Q) is small Then
Solve(P,Q)
Else
M ¬
divide(P,Q)
Combine (D&C(P,M), D&C(M+1,Q))
}
Sometimes,
this type of algorithm is known as control abstract algorithms as they
give an abstract flow. This way of breaking down the problem has found
wide application in sorting, selection and searching algorithm.
4.1 Binary Search:
Algorithm:
m¬
(p+q)/2
If (p £
m £
q) Then do the following Else Stop
If (A(m) = Key Then ‘successful’ stop
Else
If (A(m) < key Then
q=m-1;
Else
p¬
m+1
End Algorithm.
Illustration :
Consider the data set with elements {12,18,22,32,46,52,59,62,68}. First let us consider the simulation for successful cases.
Successful cases:
Key=12 P Q m Search
1 9 5 x
1 4 2 x
1 1 1 successful
To search 12, 3 units of time is required
Key=18 P Q m Search
1 9 5 x
1 4 2 successful
To search 18, 2 units of time is required
Key=22 P Q m Search
1 9 5 x
1 4 2 x
3 4 3 successful
To search 22, 3 units of time is required
Key=32 P Q m Search
1 9 5 x
1 4 2 x
3 4 3 x
4 4 4 successful
To search 32, 4 units of time is required
Key=46 P Q m Search
1 9 5 successful
To search 46, 1 unit of time is required
Key=52 P Q m Search
1 9 5 x
6 9 7 x
6 6 6 successful
To search 52, 3 units of time is required
Key=59 P Q m Search
1 9 5 x
6 9 7 successful
To search 59, 2 units of time is required
Key=62 P Q m Search
1 9 5 x
6 9 7 x
8 9 8 successful
To search 62, 3 units of time is required
Key=68 P Q m Search
1 9 5 x
6 9 7 x
8 9 8 x
9 9 9 successful
To search 68, 4 units of time is required
3+2+3+4+1+3+2+4
Successful average search time= -------------------------
9
unsuccessful cases
Key=25 P Q m Search
1 9 5 x
1 4 2 x
3 4 3 x
4 4 4 x
To search 25, 4 units of time is required
Key=65 P Q m Search
1 9 5 x
6 9 7 x
8 9 8 x
9 9 9 x
To search 65, 4 units of time is required
4+4
Unsuccessful search time =--------------------
2
average (sum of unsuccessful search time
search = + sum of Successful search time)/(n+(n+1))
time
Clik here for more details:
http://www.vyomworld.com/gate/cs/ada/4.1.asp - http://www.vyomworld.com/gate/cs/ada/4.1.asp
|