Was ist Brute Force und wann ist es akzeptabel?

Question

Accepted Answer

**Brute Force** bedeutet, jeden möglichen Kandidaten auszuprobieren, bis Sie die Antwort finden. Es ist einfach und garantiert korrekt, aber oft langsam — häufig exponentiell oder O(n²).

## Die Idee

Erschöpfend den Lösungsraum aufzählen, ohne clevere Abkürzungen.

## Beispiel: Finde ein Paar, das sich zu einem Ziel summiert (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
```

Eine Hash-Map macht dies zu O(n), aber die Brute-Force-Version ist der offensichtliche Ausgangspunkt.

## Warum es wichtig ist

- **Kleine Eingaben**, wobei der konstante Faktor und n winzig sind.
- Als **Korrektheitsbasis**, um einen schnelleren Algorithmus dagegen zu überprüfen.
- Wenn das Problem selten ausgeführt wird und Klarheit wichtiger als Geschwindigkeit ist.
- Während Interviews nennen Sie es zuerst, dann optimieren Sie.

## Fallstricke

Brute Force bei großen Eingaben verursacht Timeouts. Schätzen Sie immer die Größe des Lösungsraums, bevor Sie sich verpflichten.

## Warum es wichtig ist

Brute Force ist die ehrliche erste Lösung: Sie beweist, dass das Problem lösbar ist, und verdeutlicht genau, was "korrekt" bedeutet.

Sie erhalten eine Referenzimplementierung, um Optimierungen dagegen zu testen.

Zu wissen, wann O(n²) oder schlimmer *ausreichend* ist, ist eine echte Ingenieurfähigkeit — nicht jedes Problem verdient einen cleveren Algorithmus.