Lançado · em melhoria
Guia de Divisão e conquista · 1/6
Por enquanto, este capítulo está disponível apenas em inglês.
Divide and conquer is a way of designing algorithms: split a problem into smaller instances of the same problem, solve those instances recursively, and build the answer for the original input from their answers. Merge sort, binary search, fast exponentiation, quickselect, Karatsuba multiplication and the FFT all follow this pattern. Once you recognize it, many problems that seem to need O(n^2) work turn out to be solvable in O(n log n) or better.
Different algorithms put the real work in different steps. In merge sort, dividing is trivial (cut at the middle) and combining, the merge of two sorted halves, does the heavy lifting. In quicksort and quickselect it is the other way around: partitioning around a pivot is the hard part and combining costs nothing.
def max_value(a, lo, hi):
"""Largest element of a[lo:hi] (non-empty), by divide and conquer."""
if hi - lo == 1: # base case: one element
return a[lo]
mid = (lo + hi) // 2 # divide
left = max_value(a, lo, mid) # conquer
right = max_value(a, mid, hi)
return left if left >= right else right # combine
print(max_value([3, 9, 2, 7, 5], 0, 5)) # 9This is no faster than a simple loop, but it shows the skeleton every divide-and-conquer algorithm shares: a base case, a split, recursive calls and a combine step.
| Term | Meaning |
|---|---|
| Subproblem |
| A smaller instance of the same problem, such as sorting half of an array |
| Base case | An input small enough to answer directly; it stops the recursion |
| Recursion tree | The tree of calls: each node is a subproblem, its children are the pieces it splits into |
| Recurrence | An equation such as T(n) = 2T(n/2) + O(n) that describes the running time |
| Combine cost | The work done in one call outside its recursive calls |
| Decrease and conquer | A variant that keeps only one subproblem (binary search, fast power, quickselect) |
Some algorithms discard all but one subproblem. Binary search compares the target with the middle element and continues in only one half, so the remaining range shrinks geometrically and the total work is O(log n).
def binary_search(a, target):
lo, hi = 0, len(a) # search in a[lo:hi]
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1 # keep the right half
else:
hi = mid # keep the left half
return lo if lo < len(a) and a[lo] == target else -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3It works well when the subproblems are independent and combining is cheaper than solving the whole problem from scratch. Good signs:
If subproblems overlap, plain recursion repeats work exponentially. The naive Fibonacci function is the classic warning sign: fib(n - 1) and fib(n - 2) both recompute fib(n - 3) and everything below it. That situation calls for dynamic programming (memoization or a table), not divide and conquer.
calls = 0
def fib(n):
global calls
calls += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)
fib(25)
print(calls) # 242785 calls for one small answer: overlapping subproblems| Algorithm | Divide | Combine | Time |
|---|---|---|---|
| Merge sort | Cut at the middle | Merge two sorted halves | O(n log n) |
| Counting inversions | Cut at the middle | Count crossing pairs while merging | O(n log n) |
| Fast exponentiation | Halve the exponent | Square, maybe multiply once more | O(log e) multiplications |
| Quickselect | Partition around a pivot | Nothing; continue in one side | O(n) expected |
| Karatsuba | Split numbers into high and low halves | Three products instead of four | O(n^1.585) |
| Closest pair of points | Split the plane with a vertical line | Check a narrow strip around the line | O(n log n) |
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.