Kas yra brute force, ir kada jis yra priimtinas?

Question

Accepted Answer

**Brute force** reiškia bandyti kiekvieną galimą variantą, kol rasite atsakymą. Tai paprasta ir garantuotai teisingas, tačiau dažnai lėtas — dažniausiai eksponentinis arba O(n²).

## Idėja

Išsamiai išvardinti sprendimo erdvę be gudraių nuorodų.

## Pavyzdys: rasti porą, kurios suma lygi tikslui (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
```

Hešo žemėlapis tai paverčia O(n), tačiau brute force versija yra akivaizdus pradžios taškas.

## Kada jis yra priimtinas

- **Maži įėjimai**, kai konstanta ir n yra labai maži.
- Kaip **teisingumo bazinė linija**, skirtą greitesniam algoritmui pavalidinti.
- Kai problema paleidžiama retai ir aiškumas svarbesnis nei greitis.
- Per pokalbius, išdėstykite jį pirmiausia, tada optimizuokite.

## Pavojus

Brute force su dideliais įėjimais sukelia timeout'us. Visada įvertinkite sprendimo erdvės dydį prieš pradėdami.

## Kodėl tai svarbu

Brute force yra sąžiningas pirmasis sprendimas: jis įrodo, kad problema yra sprendžiama, ir paaiškina, ką tiksliai reiškia „teisingas