Cos'è la forza bruta e quando è accettabile?

Question

IT Interview Practice · Accepted Answer

**Forza bruta** significa provare ogni possibile candidato finché non trovi la risposta. È semplice e garantisce la correttezza, ma spesso è lenta — frequentemente esponenziale o O(n²).

## L'idea

Enumerare esaustivamente lo spazio delle soluzioni senza scorciatoie intelligenti.

## Esempio: trovare una coppia che somma a un target (forza bruta)

```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
```

Una hash map riduce questo a O(n), ma la versione a forza bruta è il punto di partenza ovvio.

## Quando è accettabile

- **Input piccoli** dove il fattore costante e n sono minuscoli.
- Come **baseline di correttezza** per validare un algoritmo più veloce.
- Quando il problema viene eseguito raramente e la chiarezza batte la velocità.
- Durante i colloqui, enuncialo prima, poi ottimizza.

## Insidie

La forza bruta su input grandi causa timeout. Stima sempre la dimensione dello spazio delle soluzioni prima di impegnarti.

## Perché è importante

La forza bruta è la prima soluzione onesta: dimostra che il problema è risolvibile e chiarisce esattamente cosa significa "corretto".

Ti fornisce un'implementazione di riferimento per testare le ottimizzazioni.

Sapere quando O(n²) o peggio è *abbastanza buono* è una vera abilità ingegneristica — non ogni problema merita un algoritmo intelligente.

L'idea

Esempio: trovare una coppia che somma a un target (forza bruta)

Quando è accettabile

Insidie

Perché è importante

Domande correlate