Mi az a brute force, és mikor elfogadható?

Question

Accepted Answer

**Brute force** azt jelenti, hogy minden lehetséges jelöltet megpróbálunk addig, amíg meg nem találjuk a választ. Egyszerű és garantáltan helyes, de gyakran lassú — általában exponenciális vagy O(n²).

## Az ötlet

A megoldásteret teljesen felsoroljuk, anélkül hogy okos rövidítéseket keresnénk.

## Példa: keressen egy párt, amely összeadódik a célhoz (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
```

Egy hash mapa ezt O(n)-re redukálja, de a brute-force verzió az nyilvánvaló kiindulópontd.

## Mikor elfogadható

- **Kis bemenetek**, ahol az állandó faktor és n apró.
- Mint egy **helyességi alap** egy gyorsabb algoritmus ellenőrzésére.
- Amikor a probléma ritkán fut le, és az érthetőség legyőzi a sebességet.
- Interjú közben először ezt állapítsa meg, majd optimalizáljon.

## Buktatók

Brute force nagyobb bemeneteken időtúllépést okoz. Mindig becsülje meg a megoldástér méretét, mielőtt elkötelezetné magát.

## Miért fontos

A brute force az őszinte első megoldás: bizonyítja, hogy a probléma megoldható, és pontosan tisztázza, mit jelent a "helyes".

Referencia-implementációt biztosít az optimalizálások teszteléséhez.

Annak tudása, hogy mikor elegendő az O(n²) vagy rosszabb, valódi mérnöki készség — nem minden probléma érdemel okos algoritmust.