Mitä on brute force ja milloin se on hyväksyttävä?

Question

Accepted Answer

**Brute force** tarkoittaa jokaisen mahdollisen ehdokkaan kokeilua, kunnes löydät vastauksen. Se on yksinkertainen ja taattu oikea, mutta usein hidas — usein eksponentiaalinen tai O(n²).

## Ajatus

Luetele ratkaisuavaruus tyhjentävästi ilman älykkäitä pikakuvakkeita.

## Esimerkki: etsi pari, joka laskee kohteeseen (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-kartta muuttaa tämän O(n):ksi, mutta brute-force-versio on ilmeinen lähtökohta.

## Milloin se on hyväksyttävää

- **Pienet syötteet**, joissa vakiokerroin ja n ovat pieniä.
- **Oikeellisuusperusteena** nopeamman algoritmin validointiin.
- Kun ongelma ajetaan harvoin ja selkeys lyö nopeuden.
- Haastatteluiden aikana mainitse se ensin, sitten optimoi.

## Sudenkuopat

Brute force suurille syötteille aiheuttaa aikakatkeaisuja. Arvioi aina ratkaisuavaruuden koko ennen sitoutumista.

## Miksi sillä on merkitystä

Brute force on rehellinen ensimmäinen ratkaisu: se todistaa, että ongelma on ratkaistavissa ja selventää tarkalleen, mitä "oikea" tarkoittaa.

Se antaa sinulle vertailuimplementaation optimisointien testaamiseen.

Tietää, milloin O(n²) tai huonompi on *riittävä*, on todellinen suunnittelutaito — kaikki ongelmat eivät ansaitse älykästä algoritmia.