42 lines
1.8 KiB
Markdown
42 lines
1.8 KiB
Markdown
|
---
|
||
|
|
date: 09.09.2024
|
||
|
|
type: theoretical
|
||
|
|
---
|
||
|
|
|
||
|
|
|
||
|
|
Divide and Conquer is a powerful algorithmic paradigm used to solve complex problems by breaking them down into smaller, more manageable sub-problems.
|
||
|
|
|
||
|
|
## Steps in Divide and Conquer
|
||
|
|
|
||
|
|
1. **Divide:**
|
||
|
|
- The problem is divided into smaller subproblems that are similar to the original but smaller in size.
|
||
|
|
- This division continues until the subproblems become simple enough to be solved directly.
|
||
|
|
|
||
|
|
2. **Conquer:**
|
||
|
|
- Solve the smaller subproblems recursively. If the subproblems are small enough (base cases), solve them directly without further recursion.
|
||
|
|
|
||
|
|
3. **Combine:**
|
||
|
|
- Combine the solutions of the subproblems to get the solution to the original problem.
|
||
|
|
|
||
|
|
### Example: Merge Sort
|
||
|
|
|
||
|
|
**Merge Sort** is a classic example of the Divide and Conquer approach:
|
||
|
|
|
||
|
|
1. **Divide:**
|
||
|
|
- Split the unsorted array into two halves recursively until each subarray contains a single element.
|
||
|
|
|
||
|
|
2. **Conquer:**
|
||
|
|
- Merge two sorted halves by comparing elements from each half in sorted order.
|
||
|
|
|
||
|
|
3. **Combine:**
|
||
|
|
- Combine the sorted halves to form a single sorted array.
|
||
|
|
|
||
|
|
The time complexity of Merge Sort is $\mathcal{O}(n \log n)$ because the array is repeatedly divided in half ($\log n$ divisions) and each division requires a linear amount of work ($\mathcal{O}(n)$) to merge.
|
||
|
|
|
||
|
|
### Other Examples
|
||
|
|
|
||
|
|
- **Quick Sort:** Uses Divide and Conquer by selecting a "pivot" element and partitioning the array into elements less than and greater than the pivot.
|
||
|
|
- **Binary Search:** Recursively divides a sorted array in half to search for an element, reducing the search space by half each time.
|
||
|
|
- **Strassen's Matrix Multiplication:** An algorithm that reduces the time complexity of matrix multiplication from $\mathcal{O}(n^3)$ to approximately $\mathcal{O}(n^{2.81})$ by recursively breaking down matrices.
|
||
|
|
|