Divide and conquer: Difference between revisions
imported>Yitzchak Novick (added the definition of divide and conquer algorithms) |
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/> | |||
Revision as of 10:30, 13 February 2009
{[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).