Divide-and-Conquer Algorithm
IT 위키
더 많은 작업
Divide-and-Conquer Algorithm is a problem-solving approach that breaks a complex problem into smaller subproblems, solves them recursively, and then combines the results to obtain the final solution. It is widely used in computer science for designing efficient algorithms.
- Divide: The original problem is split into smaller, independent or overlapping subproblems.
- Conquer: Each subproblem is solved recursively.
- Combine: The solutions of the subproblems are merged to obtain the final result.
- Divide the problem into smaller subproblems of the same type.
- Recursively solve each subproblem.
- Combine the results of the subproblems to solve the original problem.
- Merge Sort
- Divides the array into two halves.
- Recursively sorts each half.
- Merges the two sorted halves into a single sorted array.
- Complexity: O(n log n).
- Quick Sort
- Selects a pivot element.
- Partitions the array such that elements smaller than the pivot are on the left and larger ones are on the right.
- Recursively applies quick sort to both partitions.
- Complexity: O(n log n) (average case).
- Binary Search
- Compares the target value with the middle element.
- If the target is smaller, searches in the left half; otherwise, searches in the right half.
- Repeats until the target is found or the search space is empty.
- Complexity: O(log n).
- Efficiency: Many divide-and-conquer algorithms have better time complexity than iterative approaches.
- Parallelism: The independent subproblems can be solved concurrently.
- Simplification: Reduces complex problems into manageable subproblems.
- Recursion Overhead: Excessive recursive calls can lead to high memory usage.
- Merge Overhead: Combining subproblem results may require extra computations.
- Not Always Optimal: Some problems do not naturally fit the divide-and-conquer paradigm.
Divide-and-conquer algorithms are used in:
- Sorting Algorithms: Merge Sort, Quick Sort.
- Searching Algorithms: Binary Search.
- Matrix Multiplication: Strassen’s algorithm.
- Computational Geometry: Closest pair of points problem.
- Graph Algorithms: Finding strongly connected components.
| Approach | Description | Example Algorithms |
|---|---|---|
| Divide and Conquer | Breaks the problem into smaller subproblems, solves recursively, then combines | Merge Sort, Quick Sort, Binary Search |
| Dynamic Programming | Breaks the problem into overlapping subproblems and stores results to avoid recomputation | Fibonacci Sequence, Matrix Chain Multiplication |
| Greedy Algorithms | Makes the best local choice at each step to find a global solution | Kruskal’s Algorithm, Dijkstra’s Algorithm |