Chapitre 8 - Révision : Algorithmique avancée et recherche textuelle

---

1. Diviser pour régner

Principe : Diviser → Régner (récursion) → Combiner

Algorithme	Diviser	Combiner	Complexité
Tri fusion	Couper en 2	Fusionner	O(n log₂ n)
Rotation d'image	4 blocs	Permuter	O(n²)
Exponentiation rapide	n/2	Multiplier	O(log₂ n)

Tri fusion : stable, O(n log₂ n) dans tous les cas.

---

2. Programmation dynamique

• Quand : sous-problèmes chevauchants + sous-structure optimale
• Mémoïsation (descendante) : récursion + dictionnaire de cache
• Tabulation (ascendante) : remplir un tableau de bas en haut

Problème	Relation de récurrence	Complexité
Fibonacci	F(n) = F(n-1) + F(n-2)	O(n) vs O(2ⁿ) naïf
Rendu de monnaie	nb[s] = 1 + min(nb[s-p])	O(somme × nb_pièces)
Distance d'édition	d[i][j] = min(ins, sup, sub)	O(n × m)

---

3. Recherche textuelle (Boyer-Moore)

• Comparaison de droite à gauche
• Prétraitement : table du mauvais caractère (dernière occurrence de chaque lettre)
• Cas favorable : O(n/m) - sous-linéaire
• Cas défavorable : O(n × m) - comme l'algorithme naïf

Algorithme	Prétraitement	Meilleur cas	Pire cas
Naïf	Aucun	O(n)	O(n × m)
Boyer-Moore	O(m)	O(n/m)	O(n × m)