|
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. Computer science (academically, CS, CSC or compsci) encompasses a variety of topics that relates to computation, like abstract analysis of algorithms, formal grammars, and subjects such as programming languages, program design, software and computer hardware. ...
Flowcharts are often used to represent algorithms. ...
In mathematics and computer science, recursion is a particular way of specifying (or constructing) a class of objects (or an object from a certain class) with the help of a reference to other objects of the class: a recursive definition defines objects in terms of the already defined objects of...
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). In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes O(n log n) comparisons to sort n items. ...
In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e. ...
In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ...
A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...
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 in implicitly stored in the procedure call stack. In computer science, a subroutine (function, procedure, or subprogram) is a sequence of code which performs a specific task, as part of a larger program, and is grouped as one, or more, statement blocks; such code is sometimes collected into software libraries. ...
A stack is a data structure that works on the principle of Last In First Out (LIFO). ...
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. A stack is a data structure that works on the principle of Last In First Out (LIFO). ...
For queueing people, see queue area. ...
A priority queue is an abstract data type supporting the following two 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 The simplest way to implement a priority queue data type is to keep...
Branch and bound is a general method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ...
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 to the original problem. 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. Indeed, for many such problems the paradigm offers the only simple solution. A model set of the Towers of Hanoi The Tower of Hanoi (also called Towers of Hanoi) is a mathematical game or puzzle. ...
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. In computer science, a cache (pronounced kăsh) is a collection of data duplicating original values stored elsewhere or computed earlier, where the original data are expensive (usually in terms of access time) to fetch or compute relative to reading the cache. ...
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. Virtual memory is a computer design feature that permits software to use more main memory (the memory which the CPU can read and write to directly) than the computer actually physically possesses. ...
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. In complexity theory, computer science, and mathematics the Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
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 a 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. (On the other hand, the latter approach turns out to be much more accurate in finite-precision floating-point arithmetic.)
Alternatively, an algorithm can be designed by a divide-and-conquer approach and then implemented in an iterative style; of course, any recursive algorithm can be simulated in an iterative style, but by reordering the computation it is sometimes possible to avoid simulating a recursive call stack altogether. The Cooley-Tukey FFT algorithm is a prime example of this: it was initially derived in a divide-and-conquer style, but implementations were traditionally implemented iteratively in a re-ordered fashion that avoided call-stack-like storage (although some recent implementations have returned to a recursive style). The Cooley-Tukey algorithm is the most common fast Fourier transform (FFT) algorithm. ...
See also Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. ...
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. ...
References - M. Frigo, C. E. Leiserson, and H. Prokop, " Cache-oblivious algorithms (http://theory.lcs.mit.edu/~athena/abstracts/abstract4.html#afterheading)", 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).
|
Feeds |
Contact