Hvad er divide-and-conquer paradigmet?

Question

Accepted Answer

**Divide and conquer** løser et problem ved at (1) **opdele** det i mindre delproblemer, (2) **løse** hver af dem rekursivt, og (3) **kombinere** resultaterne. Mange effektive algoritmer følger denne skabelon.

## Ideen

Hvis delproblemer er uafhængige og bliver mindre hurtigt, følger det samlede arbejde en rekurrence, som du kan analysere med **Master Theorem**.

## Eksempel: maksimalt element via divide and conquer

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## Klassiske eksempler

- **Merge sort / quicksort** — O(n log n) sortering.
- **Binary search** — O(log n).
- **Fast exponentiation, Karatsuba multiplication, closest pair.**

## Kompleksitet

Oftest T(n) = a·T(n/b) + f(n); for merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Hvornår skal det bruges / faldgruber

Brug det når et problem **deler sig rent** i uafhængige delproblemer. Hvis delproblemer **overlapper**, foretrækker du dynamisk programmering i stedet for (for at undgå genberegning). Rekursion overhead og kombinationstrinnet kan dominere for små input.

## Hvorfor det betyder noget

Divide and conquer er en genbrugelig skabelon bag en stor andel af effektive algoritmer.

At genkende mønstret lader dig udlede og analysere nye algoritmer hurtigt ved hjælp af rekurrencer.

Det kortlægger også naturligt til parallelitet, da uafhængige delproblemer kan køre samtidigt.