Hva er brute force, og når er det akseptabelt?

Question

Accepted Answer

**Brute force** betyr å prøve alle mulige kandidater inntil du finner svaret. Det er enkelt og garantert korrekt, men ofte sakte — typisk eksponentiell eller O(n²).

## Ideen

Gjennom å uttømmende enumerere løsningsrommet uten smarte snarveier.

## Eksempel: finn et tallpar som summerer til målet (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 gjør dette til O(n), men brute-force-versjonen er det åpenbare utgangspunktet.

## Når det er akseptabelt

- **Små inndata** hvor konstantfaktoren og n er minimal.
- Som en **korrektnesbaseline** for å validere en raskere algoritme mot.
- Når problemet kjøres sjelden og klarhet er viktigere enn hastighet.
- Under intervjuer, stat det først, så optimer.

## Fallgruver

Brute force på store inndata forårsaker timeout. Alltid estimer størrelsen på løsningsrommet før du forplikter deg.

## Hvorfor det betyr noe

Brute force er den ærlige første løsningen: det beviser at problemet er løsbar og avklarer nøyaktig hva "korrekt" betyr.

Det gir deg en referanseimplementering til å teste optimeringer mot.

Å vite når O(n²) eller verre er *god nok* er en reell ingeniørferdighet — ikke alle problemer fortjener en smart algoritme.