Kaj je groba sila in kdaj je sprejemljiva?

Question

Accepted Answer

**Groba sila** pomeni poskušanje vsakega možnega kandidata, dokler ne najdeš odgovor. Je preprosta in zagotovljeno pravilna, toda pogosto počasna — pogosto eksponentna ali O(n²).

## Ideja

Izčrpno naštevanje prostora rešitev brez pametnih bližnjic.

## Primer: poišči par, ki se sešteje v cilj (groba sila)

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

Zgostitev s preslikavo pretvori to v O(n), toda verzija z grob silo je očitna začetna točka.

## Kdaj je sprejemljiva

- **Majhni vhodi**, kjer sta konstanti in n majhna.
- Kot **referenca za pravilnost**, da preveriti hitrejši algoritem.
- Ko se problem redko izvršuje in jasnost prekaša hitrost.
- Med intervjuji jo najprej navedi, nato optimiziraj.

## Pasti

Groba sila na velikih vhodih povzroči časovne limite. Vedno oceni velikost prostora rešitve, preden se odločiš.

## Zakaj je to pomembno

Groba sila je pošten prvi korak: dokaže, da je problem rešljiv, in pojasni natančno, kaj pomeni "pravilno".

Vam referenčno implementacijo za testiranje optimizacij.

Znati, kdaj je O(n²) ali slabše *dovolj dobro*, je prava inženirska veščina — ne vsak problem zasluži pameten algoritem.