|
In computer science, divide and conquer (D&C) is an important algorithm design paradigm. It works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. A divide and conquer algorithm is closely tied to a type of recurrence relation between functions of the data in question; data is "divided" into smaller portions and the result calculated thence. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
Algorithm design is a specific method to create a mathematical process in solving problems. ...
For other uses, see Paradigm (disambiguation). ...
This article is about the concept of recursion. ...
In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...
This technique is the basis of efficient algorithms for all kinds of problems, such as sorting (quicksort, merge sort) and the discrete Fourier transform (FFTs). Its application to numerical algorithms is commonly known as binary splitting. Flowcharts are often used to represent algorithms. ...
In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...
Q sort redirects here. ...
A merge sort algorithm used to sort an array of 7 integer values. ...
In mathematics, the discrete Fourier transform (DFT), occasionally called the finite Fourier transform, is a transform for Fourier analysis of finite-domain discrete-time signals. ...
The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...
Babylonian clay tablet YBC 7289 (c. ...
In mathematics, binary splitting is a technique for speeding up numerical evaluation of many types of series with rational terms. ...
History
The core idea behind the divide and conquer algorithm was first proposed by Anatolii Karatsuba in 1960[1], as an algorithm for multiplying two n-digit numbers with an algorithmic complexity of  . This algorithm, now known as Karatsuba's algorithm, thus disproved Andrey Kolmogorov's 1956 conjecture that the fastest multiplication algorithm was O(n2). Kolmogorov's work, together with Karatsuba's discovery, helped launch the study of the performance of algorithms. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
The Karatsuba multiplication algorithm, a technique for quickly multiplying large numbers, was discovered by Anatolii Alexeevich Karatsuba in 1960 and published in the joint paper with Yu. ...
Andrey Nikolaevich Kolmogorov (Russian: ÐндреÌй ÐиколаÌевич КолмогоÌров) (April 25, 1903 - October 20, 1987) was a Soviet mathematician who made major advances in different academic fields (among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity). ...
A multiplication algorithm is an algorithm (or method) to multiply two numbers. ...
Implementation Divide-and-conquer algorithms are naturally implemented as recursive procedures. In that case, the partial sub-problems leading to the one currently being solved are implicitly stored in the procedure call stack. In computer science, a subroutine (function, method, procedure, or subprogram) is a portion of code within a larger program, which performs a specific task and can be relatively independent of the remaining code. ...
In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. ...
However, D&C solutions can also be implemented by a non-recursive algorithm that stores the partial sub-problems in some explicit data structure, such as a stack, queue, or priority queue. This approach allows more freedom in the choice of the sub-problem that is to be solved next, a feature that is important in some applications — e.g. in breadth-first recursion and the branch and bound method for function optimization. Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ...
A queue (pronounced /kuË/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. ...
A priority queue is an abstract data type in computer programming, supporting the following three operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it (optionally) peek at the element with highest priority without removing...
In computer science, breadth-first search (BFS) is a tree search algorithm used for traversing or searching a tree, graph. ...
Branch and bound is a general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ...
Variations One variation of divide and conquer is called decrease and conquer, where a solution of problem depends on only one subproblem. There are two advantages of treating this variant separately. Some problems do not need to solve all subproblems, and have a simpler conquer strategy. They can be generally solved with tail recursion. Analysis of these problems is simpler than divide and conquer. In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function is a recursive call. ...
For finding the largest element in a list of numbers:
Algorithm LargestNumber Input: A non-empty list of numbers L. Output: The largest number in the list L. Comment: Divide and Conquer if L.size = 1 then return L.front largest1 ← LargestNumber(L.front...L.mid) largest2 ← LargestNumber(L.mid....L.back) if largest1 > largest2, then largest ← largest1 else largest ← largest2 return largest Algorithm LargestNumber Input: A non-empty list of numbers L. Output: The largest number in the list L. Comment: Decrease and Conquer if L.size = 1 then return L.front last = L.size - 1; largest ← LargestNumber(L.front...L.last) if largest < L.back then largest ← L.back return largest Finding the maximum is solved by decreasing the problem by one element on each pass. A more popular example of decrease and conquer is the binary search algorithm, where the problem size will be cut down by half in each decrease phase and thus completes faster. In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ...
Advantages
Solving difficult problems Divide and conquer is a powerful tool for solving conceptually difficult problems, such as the classic Tower of Hanoi puzzle: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases and of combining sub-problems to the original problem. Indeed, for many such problems the paradigm offers the only simple solution. A model set of the Towers of Hanoi (with 8 disks) An animated solution of the Tower of Hanoi puzzle for T(4,3). ...
Dividing the problem into sub-problems so that the sub-problems can be combined again is often the major difficulty in designing a new algorithm.
Algorithm efficiency Moreover, divide and conquer often provides a natural way to design efficient algorithms.
For example, if the work of splitting the problem and combining the partial solutions is proportional to the problem's size n, there are a bounded number p of subproblems of size ~ n/p at each stage, and the base cases require O(1) (constant-bounded) time, then the divide-and-conquer algorithm will have O(n log n) complexity. This is used for problems such as sorting and FFTs to reduce the complexity from O(n2), although in general there may also be other approaches to designing efficient algorithms.
Parallelism Divide and conquer algorithms are naturally adapted for execution in multi-processor machines, especially shared-memory systems where the communication of data between processors does not need to be planned in advance, because distinct sub-problems can be executed on different processors.
Memory access Divide-and-conquer algorithms naturally tend 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. An algorithm designed to exploit the cache in this way is called cache oblivious, because it does not contain the cache size(s) as an explicit parameter. For other uses, see cache (disambiguation). ...
In computing, a cache-oblivious algorithm is an algorithm designed to exploit the CPU cache without having the size of the cache (or the length of the cache lines, etcetera) as an explicit parameter. ...
Moreover, D&C algorithms can be designed for many important algorithms, such as sorting, FFTs, and matrix multiplication, in such a way as to be optimal cache oblivious algorithms—they use the cache in a provably optimal way, in an asymptotic sense, regardless of the cache size. In contrast, the traditional approach to exploiting the cache is blocking, where the problem is explicitly divided into chunks of the appropriate size—this can also use the cache optimally, but only when the algorithm is tuned for the specific cache size(s) of a particular machine.
The same advantage exists with regards to other hierarchical storage systems, such as NUMA or virtual memory, as well as for multiple levels of cache: once a sub-problem is small enough, it can be solved within a given level of the hierarchy, without accessing the higher (slower) levels. Non-Uniform Memory Access or Non-Uniform Memory Architecture (NUMA) is a computer memory design used in multiprocessors, where the memory access time depends on the memory location relative to a processor. ...
The program thinks it has a large range of contiguous addresses; but in reality the parts it is currently using are scattered around RAM, and the inactive parts are saved in a disk file. ...
However, the kind of asymptotic optimality described here, analogous to big O notation, ignores constant factors, and additional machine/cache-specific tuning is in general required to achieve optimality in an absolute sense. For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...
Disadvantages One commonly argued disadvantage of a divide-and-conquer approach is that recursion is slow: the overhead of the repeated subroutine calls, along with that of storing the call stack (the state at each point in the recursion), can outweigh any advantages of the approach. This, however, depends upon the implementation style: with large enough recursive base cases, the overhead of recursion can become negligible for many problems.
Another problem of a divide-and-conquer approach is that, for simple problems, it may be more complicated than an iterative approach, especially if large base cases are to be implemented for performance reasons. For example, to add N numbers, a simple loop to add them up in sequence is much easier to code than a divide-and-conquer approach that breaks the set of numbers into two halves, adds them recursively, and then adds the sums.
For some problems, many of the subproblems overlap. In such cases it is better to reuse the solutions to these overlapping subproblems. This approach is commonly known as memoization and is the recursive version of dynamic programming. Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...
In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ...
See also Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...
In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. ...
In computer science, the Akra-Bazzi method, or Akra-Bazzi theorem, is used to analyze the asymptotic behavior of the mathematical recurrences that appear in the analysis of divide and conquer algorithms where the sub-problems have substantially different sizes. ...
For the collection of novellas by L. Sprague de Camp, see Divide and Rule (collection). ...
A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. ...
References - M. Frigo, C. E. Leiserson, and H. Prokop, "Cache-oblivious algorithms", Proc. 40th Symp. on the Foundations of Computer Science (1999).
- Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).
External links - Code example of Divide and Conquer, fast power calculation, in C++
leroy suck wang |
Feeds |
Contact