Divide & Conquer
Auxerre, La Rivière, 1902, Paul Signac.jpg
- 1. What is Divide and Conquer?
- 2. How Divide and Conquer Algorithms Work?
- 3. Time Complexity
- 4. Divide and Conquer Applications
1. What is Divide and Conquer?
A divide and conquer algorithm is a strategy of solving a large problem by
- breaking the problem into smaller sub-problems
- solving the sub-problems, and
- combining them to get the desired output.
To use the divide and conquer algorithm, recursion is used.
2. How Divide and Conquer Algorithms Work?
1. Divide: Divide the given problem into sub-problems using recursion.
2. Conquer: Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.
3. Combine: Combine the solutions of the sub-problems that are part of the recursive process to solve the actual problem.
Here, we will sort an array using the divide and conquer approach (ie. merge sort).
[Step 0]
Let the given array be
Array for merge sort
[Step 1]
Divide the array into two halves.
Divide the array into two subparts
Again, divide each subpart recursively into two halves until you get individual elements.
Divide the array into smaller subparts
[Step 2,3]
Now, combine the individual elements in a sorted manner. Here, conquer and combine steps go side by side.
Combine the subparts
3. Time Complexity
The complexity of the divide and conquer algorithm is calculated using the master theorem.
T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the same size.
f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions
Let us take an example to find the time complexity of a recursive problem.
For a merge sort, the equation can be written as:
T(n) = aT(n/b) + f(n)
= 2T(n/2) + O(n)
Where,
a = 2 (each time, a problem is divided into 2 subproblems)
n/b = n/2 (size of each sub problem is half of the input)
f(n) = time taken to divide the problem and merging the subproblems
T(n/2) = O(n log n) (To understand this, please refer to the master theorem.)
Now, T(n) = 2T(n log n) + O(n)
≈ O(n log n)
4. Divide and Conquer Applications
Advantages of Divide and Conquer Algorithm
The complexity for the multiplication of two matrices using the naive method is \(O(n3)\), whereas using the divide and conquer approach (i.e. Strassen’s matrix multiplication) is \(O(n2.8074)\). This approach also simplifies other problems, such as the Tower of Hanoi. This approach is suitable for multiprocessing systems. It makes efficient use of memory caches.
Divide and Conquer is used when
- Binary Search
- Quick Sort
- Merge Sort
- Strassen’s Matrix multiplication
- Karatsuba Algorithm
https://www.freecodecamp.org/
https://www.programiz.com/
https://www.geeksforgeeks.org/
https://blog.naver.com/PostList.naver?blogId=ndb796
이것이 코딩테스트다,2020,나동빈,한빛미디어