Hvad er brute force, og hvornår er det acceptabelt?

Question

Accepted Answer

**Brute force** betyder at prøve alle mulige kandidater, indtil du finder svaret. Det er enkelt og garanteret korrekt, men ofte langsomt — ofte eksponentielt eller O(n²).

## Ideen

Opregn løsningsrummet udtømmende uden smarte genveje.

## Eksempel: find et par, der summerer til et mål (brute force)

```python
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # check every pair
            if nums[i] + nums[j] == target:
                return (i, j)
    return None
# O(n^2) time, O(1) space
```

Et hash map gør dette til O(n), men brute-force-versionen er det åbenlyse udgangspunkt.

## Hvornår det er acceptabelt

- **Små inputs**, hvor konstantfaktoren og n er tiny.
- Som et **korrekthedgrundlag** til at validere en hurtigere algoritme mod.
- Når problemet køres sjældent, og klarhed slår hastighed.
- Under interviews, start med det, derefter optimer.

## Faldgruber

Brute force på store inputs forårsager timeout. Estimér altid størrelsen af løsningsrummet, før du forpligter dig.

## Hvorfor det betyder noget

Brute force er den ærlige første løsning: det beviser, at problemet er løsbart, og præciserer præcist, hvad "korrekt" betyder.

Det giver dig en referenceimplementering til at teste optimeringer mod.

At vide, hvornår O(n²) eller værre er *godt nok*, er en reel ingeniørkompetence — ikke ethvert problem fortjener en smart algoritme.