Divide and conquer: Difference between revisions
Jump to navigation
Jump to search
imported>Gareth Leng No edit summary |
imported>Gareth Leng No edit summary |
||
| Line 1: | Line 1: | ||
{ | {{subpages}} | ||
The '''divide and conquer''' algorithmic method refers to the process of taking input data and dividing them into smaller portions (usually halves) and then recursively performing the division on the separate parts until a base with a predefined constant size is reached and some preset algorithm can be performed on the base sized input. The algorithm then performs some function on the separate parts which have already been processed by the recursive calls until it ultimately is able to perform this function on the first division which it performed on the input. Each set of recursive calls deals with the same input (in different divisions) for a running time of O(n) and there are log n divisions so the final running time is O(n log n). | The '''divide and conquer''' algorithmic method refers to the process of taking input data and dividing them into smaller portions (usually halves) and then recursively performing the division on the separate parts until a base with a predefined constant size is reached and some preset algorithm can be performed on the base sized input. The algorithm then performs some function on the separate parts which have already been processed by the recursive calls until it ultimately is able to perform this function on the first division which it performed on the input. Each set of recursive calls deals with the same input (in different divisions) for a running time of O(n) and there are log n divisions so the final running time is O(n log n). | ||
==References== | ==References== | ||
<references/> | <references/> | ||
Latest revision as of 10:30, 13 February 2009
The divide and conquer algorithmic method refers to the process of taking input data and dividing them into smaller portions (usually halves) and then recursively performing the division on the separate parts until a base with a predefined constant size is reached and some preset algorithm can be performed on the base sized input. The algorithm then performs some function on the separate parts which have already been processed by the recursive calls until it ultimately is able to perform this function on the first division which it performed on the input. Each set of recursive calls deals with the same input (in different divisions) for a running time of O(n) and there are log n divisions so the final running time is O(n log n).