Divide and conquer: Difference between revisions
Jump to navigation
Jump to search
imported>Yitzchak Novick (added the definition of divide and conquer algorithms) |
mNo edit summary |
||
| (2 intermediate revisions by one other user not shown) | |||
| 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/>[[Category:Suggestion Bot Tag]] | |||
Latest revision as of 17:01, 7 August 2024
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).