Qu'est-ce que le paradigme diviser-pour-régner ?

Question

Accepted Answer

**Diviser-pour-régner** résout un problème en (1) le **divisant** en sous-problèmes plus petits, (2) **conquérant** chacun récursivement, et (3) **combinant** les résultats. Beaucoup d'algorithmes efficaces suivent ce modèle.

## L'idée

Si les sous-problèmes sont indépendants et se réduisent rapidement, le travail total suit une récurrence que vous pouvez analyser avec le **Master Theorem**.

## Exemple : élément maximum via diviser-pour-régner

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## Exemples classiques

- **Merge sort / quicksort** — Tri O(n log n).
- **Recherche binaire** — O(log n).
- **Exponentiation rapide, multiplication de Karatsuba, paire la plus proche.**

## Complexité

Souvent T(n) = a·T(n/b) + f(n) ; pour merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Quand l'utiliser / pièges

Utilisez-le quand un problème se **divise proprement** en sous-problèmes indépendants. Si les sous-problèmes se **chevauchent**, privilégiez plutôt la programmation dynamique (pour éviter les recalculs). La surcharge de récursion et l'étape de combinaison peuvent dominer pour les petites entrées.

## Pourquoi c'est important

Diviser-pour-régner est un modèle réutilisable derrière une énorme fraction d'algorithmes efficaces.

Reconnaître le motif vous permet de dériver et analyser rapidement de nouveaux algorithmes avec des récurrences.

Cela se mappe aussi naturellement au parallélisme, puisque les sous-problèmes indépendants peuvent s'exécuter concurremment.