So, it looks like a process of breaking an array into two halves and then repeatedly applying this process to smaller arrays to again break them in two halves. We are first breaking the array into two subarrays and then again breaking those arrays into 4 subarrays and so on. Let's take an array and write a program to break it into a smaller subarrays of size 1 as shown in the first picture. So, now we will deal with the array from 'start' to 'middle' as one smaller array and the array from 'middle+1' to 'end' as the second subarray. Suppose we have to divide an array into two subarrays, we would introduce a variable which will point to the element from which we are breaking the array. In Divide and Conquer, we generally deal with arrays and our task is to first divide the array into smaller subarrays.Īt first, it might seem that we are going to make new smaller subarrays for this purpose but this is not the case. Now, let's take these steps to the domain we are concerned with i.e., programming and start our discussion with the 'divide' first. For example, the whole point of an organization would be to earn profit, so whatever the departments are doing, in last, they would sum up to generate some profit for the organization. Combine → In the last step, we combine the solutions of the smaller subproblems to get the solution of the bigger problem.In the example of the organizations, the problems of the departments will be solved individually by the departments. Conquer → This is basically solving of the smaller subproblems.In short, we are breaking our problem into smaller subproblems. So, the organization is divided into several departments and different people are appointed to assist those departments. It would be quite difficult for a single person to directly handle all the work of the organization himself. For example, take an example of any big organization. Divide → The first step is to break the problem into smaller subproblems.Thus, Divide and Conquer is a three-step process: After this, we combine the solution of the smaller subproblems to get the solution for the original problem. We literally divide the problems into smaller subproblems and then conquer (or solve) the smaller subproblems first. The name of this technique tells a lot about the technique itself. So, why not first see what basically this technique is in a detailed way and then implement it to the algorithms. Indeed, Divide and Conquer is a very useful technique but direct jumping into the algorithms might feel difficult for beginners. So, why an entire chapter just for the introduction of Divide and Conquer? This chapter is going to be just an introduction about the Divide and Conquer, we are going to study algorithms based on the divide on conquer in the next three chapters.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |