Što je brute force i kada je to prihvatljivo?

Question

Accepted Answer

**Brute force** znači pokušaj svakog mogućeg kandidata dok ne pronađete odgovor. Jednostavan je i garantirano točan, ali često spora — obično eksponencijalan ili O(n²).

## Ideja

Iscrpno nabrajanje prostora rješenja bez pametan prečaca.

## Primjer: pronađite par koji se zbraja na cilj (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
```

Hash mapa to pretvara u O(n), ali brute-force verzija je očiti početak.

## Kada je to prihvatljivo

- **Mali ulazi** gdje su konstanta i n sićušni.
- Kao **referenca ispravnosti** za provjeru bržega algoritma.
- Kada se problem rijetko izvršava i jasnoća pobjeđuje brzinu.
- Tijekom razgovora, prvo to navedite, zatim optimizirajte.

## Zamke

Brute force na velikim ulazima uzrokuje timeout. Uvijek procijenite veličinu prostora rješenja prije nego što se obavežete.

## Zašto je to važno

Brute force je iskren prvi pokušaj: dokazuje da je problem rješiv i pojašnjava točno što "točno" znači.

Daje vam referentnu implementaciju za testiranje optimizacija.

Znati kada je O(n²) ili gore *dovoljan* je vještina prave inženjere — ne svaki problem zaslužuje pametan algoritam.