Co to jest brute force i kiedy jest akceptowalny?

Question

Accepted Answer

**Brute force** oznacza wypróbowanie każdego możliwego kandydata, aż znajdziesz odpowiedź. Jest prosty i gwarantuje poprawność, ale często wolny — często o złożoności wykładniczej lub O(n²).

## Idea

Wyczerpujące wyliczenie przestrzeni rozwiązań bez sprytnych skrótów.

## Przykład: znalezienie pary, która sumuje się do celu (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
```

Mapa hash zmienia to na O(n), ale wersja brute-force jest oczywistym punktem wyjścia.

## Kiedy jest akceptowalny

- **Małe dane wejściowe**, gdzie współczynnik stały i n są bardzo małe.
- Jako **punkt odniesienia poprawności** do walidacji szybszego algorytmu.
- Gdy problem jest wykonywany rzadko, a przejrzystość bije szybkość.
- Podczas rozmów kwalifikacyjnych najpierw go podaj, potem optymalizuj.

## Pułapki

Brute force na dużych danych wejściowych powoduje timeout'y. Zawsze oszacuj wielkość przestrzeni rozwiązań przed zaangażowaniem się.

## Dlaczego to ważne

Brute force to uczciwe pierwsze rozwiązanie: dowodzi, że problem jest rozwiązywalny i wyjaśnia dokładnie, co oznacza "poprawny".

Daje ci implementację odniesienia, aby testować optymalizacje.

Wiedza o tym, kiedy O(n²) lub gorzej jest *wystarczająco dobre* to rzeczywista umiejętność inżynierii — nie każdy problem zasługuje na sprytny algorytm.