Glossaire

Le vocabulaire à maîtriser pour parler d'algorithmes clairement en entretien.

Amorti#

Coût moyen par opération sur une longue séquence. Ajouter en fin de tableau dynamique est O(1) amorti : un redimensionnement coûteux est rare.

Invariant#

Propriété qui reste vraie à chaque itération d'une boucle. L'énoncer aide à prouver qu'un algorithme est correct.

En place (in-place)#

Algorithme qui utilise O(1) mémoire supplémentaire en modifiant directement l'entrée.

Tri stable#

Un tri qui conserve l'ordre relatif des éléments égaux.

DFS / BFS#

Parcours en profondeur (pile ou récursion) et en largeur (file). Le BFS trouve le plus court chemin dans un graphe non pondéré.

Mémoïsation#

Mettre en cache le résultat d'un sous-problème pour ne le calculer qu'une fois (DP top-down).

Tabulation#

Remplir un tableau de sous-problèmes du plus petit au plus grand (DP bottom-up).

Pile monotone#

Pile dont les éléments restent triés ; sert à trouver le prochain élément plus grand ou plus petit en O(n).

Sentinelle (dummy node)#

Nœud factice en tête de liste qui évite de traiter à part le cas « liste vide » ou « modification de la tête ».

Tri topologique#

Ordre linéaire des nœuds d'un graphe orienté acyclique tel que chaque dépendance passe avant ce qui en dépend.

Élagage (pruning)#

Abandonner une branche de recherche dès qu'on sait qu'elle ne peut pas mener à une solution.

Cas limites (edge cases)#

Entrées extrêmes à tester : vide, un seul élément, doublons, valeurs négatives, très grandes entrées.