Fiche de révision - Algorithmique
1. Arbres binaires
- Arbre binaire : structure récursive (vide ou nœud + gauche + droit)
- Taille :
1 + taille(gauche) + taille(droit), arbre vide → 0
- Hauteur :
1 + max(hauteur(gauche), hauteur(droit)), arbre vide → -1
- Encadrement : \(\lfloor \log_2 n \rfloor \leq h \leq n-1\)
| Parcours |
Ordre |
Structure |
| Préfixe |
Racine → Gauche → Droit |
Récursion |
| Infixe |
Gauche → Racine → Droit |
Récursion |
| Suffixe |
Gauche → Droit → Racine |
Récursion |
| Largeur |
Niveau par niveau |
File (FIFO) |
ABR : gauche < racine < droit. Infixe = ordre croissant. Recherche O(log₂ n) si équilibré.
2. Algorithmes sur les graphes
| Parcours |
Structure |
Propriété |
| DFS (profondeur) |
Pile / récursion |
Trouve un chemin, détecte les cycles |
| BFS (largeur) |
File (FIFO) |
Trouve le plus court chemin (en arêtes) |
- Cycle : DFS + vérification voisin visité ≠ parent
- Graphe connexe sans cycle = arbre (\(n-1\) arêtes pour \(n\) sommets)
3. 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.
4. 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) |
5. 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) |