Что такое перебор, и когда он приемлем?

Question

Accepted Answer

**Перебор** — это попытка каждого возможного варианта до нахождения ответа. Это просто и гарантирует правильность, но часто медленно — обычно экспоненциальная сложность или O(n²).

## Идея

Исчерпывающее перечисление пространства решений без умных оптимизаций.

## Пример: найти пару с суммой, равной целевому значению (перебор)

```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
```

Хеш-таблица превращает это в O(n), но версия с перебором — это очевидная отправная точка.

## Когда это приемлемо

- **Маленькие входные данные**, где постоянный множитель и n ничтожно малы.
- Как **базовая проверка корректности** для валидации более быстрого алгоритма.
- Когда задача выполняется редко и ясность важнее скорости.
- На собеседованиях сначала озвучьте это, затем оптимизируйте.

## Ловушки

Перебор на больших входных данных приводит к timeout'ам. Всегда оценивайте размер пространства решений перед началом реализации.

## Почему это важно

Перебор — это честное первое решение: оно доказывает, что задача решаема, и уточняет, что именно означает "правильность".

Оно дает вам эталонную реализацию для проверки оптимизаций.

Умение определять, когда O(n²) или хуже *достаточно хорошо* — это реальный инженерный навык. Не каждая задача заслуживает умного алгоритма.