What is a divide and conquer algorithm?
In computer science, Divide and Conquer is an algorithm design paradigm. It recursively breaks down the main problem into multiple, smaller subproblems that are similar or related. It repeatedly does so until the sub-problems become simple enough to solve. The individual solutions of the smaller problems are later combined to give the final solution to the main problem.
The divide and conquer method is the foundation of many algorithms such as sorting, including quicksort and mergesort, as well as searching algorithms such as binary search.
There are 3 main steps involved in the Divide-and-Conquer technique. These include:
Divide - This involves breaking a problem into multiple sub-problems.
Conquer - This involves solving the sub-problems. The problem is repeatedly solved until a condition is met. This condition is known as the base case.
Combine - This involves putting the solutions of the sub-problems together.
Divide-and-Conquer in Binary Search
A binary search is an algorithm that searches for a target element in a pre-sorted collection/array. It compares the target element to the middle element of the array, and then recursively divides the array into two sub-arrays that may contain the target element. Hence the search space is divided in half. Then each sub-array is conquered separately. This process continues until either the element is found or the recursion bottoms out (base case reached). The running time is O(log(n)).
Divide-and-Conquer in Merge Sort
Merge sort is a type of divide-and-conquer sorting algorithm. It is an efficient, comparison-based method that is used to sort an unsorted collection. It divides the input into two halves, calls itself for the two halves, and then merges them. The function known as merge() is used to merge the two halves of the collection. Its running time is O(n*log(n)).
Why use Divide-and-Conquer Algorithms?
It is useful to solve difficult problems. This is because it breaks down the problem into multiple smaller sub-problems, solves the trivial problems, and then combines them.
It helps solve problems efficiently. It was useful in discovering other efficient algorithms, including Karatsuba's fast multiplication method, the Strassen algorithm for matrix multiplication, and fast Fourier transforms.
It allows parallelism. Divide-and-Conquer algorithms are naturally adapted for use in multiprocessor systems such as shared memory systems, where the communication of data between processors needn't be planned, as the sub-problems can be executed on different processors.
Memory access is made easier. Divide-and-Conquer algorithms efficiently use memory caches. When the sub-problems are small enough, they can be solved inside the cache instead of the slower main memory.
It allows round-off control. In computations that involve floating-point values, this algorithm will provide the user with more accurate results compared to another iterative method.
Article was written for CyberClubNPSi
Commentaires