Vad är brute force och när är det acceptabelt?

Question

IT Interview Practice · Accepted Answer

**Brute force** betyder att du försöker varje möjlig kandidat tills du hittar svaret. Det är enkelt och garanterat korrekt, men ofta långsamt — ofta exponentiellt eller O(n²).

## Idén

Uttömmande uppräkning av lösningsutrymmet utan smarta genvägar.

## Exempel: hitta ett par som summerar till ett 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
```

En hash map gör detta till O(n), men brute-force-versionen är den uppenbara utgångspunkten.

## När det är acceptabelt

- **Små inmatningar** där konstantfaktorn och n är små.
- Som en **korrekthetsbas** för att validera en snabbare algoritm mot.
- När problemet körs sällan och klarhet slår hastighet.
- Under intervjuer, presentera det först, optimera sedan.

## Fallgropar

Brute force på stora inmatningar orsakar timeout. Uppskatta alltid storleken på lösningsutrymmet innan du förbinder dig.

## Varför det är viktigt

Brute force är den ärliga första lösningen: det bevisar att problemet är lösligt och förtydligar exakt vad "korrekt" betyder.

Det ger dig en referensimplementering för att testa optimeringar mot.

Att veta när O(n²) eller värre är *tillräckligt bra* är en verklig ingenjörskonst — inte alla problem förtjänar en smart algoritm.

Idén

Exempel: hitta ett par som summerar till ett mål (brute force)

När det är acceptabelt

Fallgropar

Varför det är viktigt

Relaterade frågor