Types d’algorithmes, quelle méthode choisir ?

Tableau comparatif des différents types d'algorithme : supervisé, non supervisé, renforcé, et profond. Il détaille les données d'entrée, l'apprentissage en continu, le transfert d'apprentissage et la complexité.

Publié le

19 nov. 2026

Table des matières

Devant un tableau de nombres désordonné, tu peux choisir un tri simple à écrire ou une méthode qui découpe le problème en morceaux. Il existe plusieurs types d’algorithmes, et le bon choix dépend de la forme des données et du résultat attendu, avec une réserve importante : une stratégie rapide n’assure pas toujours une solution correcte ou optimale.

Représentation visuelle de deux types d'algorithmes :

Le bon algorithme dépend du problème, pas seulement du code

  • Par objectif, on distingue recherche, tri, parcours et optimisation.
  • Par stratégie, on parle notamment de force brute, de récursion, de méthode gloutonne et de programmation dynamique.
  • Tri fusion illustre le principe « diviser pour régner » : les sous-problèmes sont séparés, puis leurs résultats sont réunis.
  • Une décision gloutonne peut échouer si le choix local ne garantit pas le meilleur résultat global.
  • La complexité estime l’évolution du temps de calcul ou de la mémoire lorsque l’entrée grossit.

Un « type d’algorithme » peut désigner son but ou sa méthode

Le terme prête à confusion, car il répond à deux questions différentes. Un algorithme peut être classé selon la tâche qu’il accomplit, comme trier une liste, ou selon la stratégie qu’il utilise, comme diviser le problème en sous-problèmes.

Par exemple, le tri fusion est à la fois un algorithme de tri et une méthode « diviser pour régner ». Ces catégories se croisent : elles ne forment pas une liste unique de cases où chaque algorithme n’aurait qu’une seule étiquette.

  • Recherche : trouver un élément dans une collection, par exemple avec une recherche séquentielle.
  • Tri : réorganiser les éléments, par exemple avec le tri par insertion ou le tri fusion.
  • Parcours de graphe : explorer des liens entre des sommets, comme dans un plan de métro ou un réseau social.
  • Optimisation : chercher la meilleure solution selon un critère, comme réduire le nombre de pièces utilisées pour rendre une somme.

Je considère que cette distinction entre objectif et stratégie évite une erreur fréquente : comparer des noms qui ne répondent pas à la même question. Reste à voir comment ces stratégies travaillent.

Les stratégies de conception se distinguent par leur manière d’explorer

Imagine une boîte de pièces de puzzle. Certaines méthodes examinent les possibilités une à une, d’autres découpent l’image, et d’autres encore enregistrent les essais déjà résolus. La structure du problème aide à choisir la bonne approche.

Stratégie Principe Exemple et limite
Force brute Tester directement les possibilités. Pratique pour un petit espace de recherche, mais le nombre d’essais peut exploser.
Diviser pour régner Découper le problème en sous-problèmes indépendants, puis combiner les réponses. Le tri fusion suit ce schéma ; le partage et la fusion ont toutefois un coût.
Programmation dynamique Résoudre les sous-problèmes qui se répètent et mémoriser leurs résultats. Utile pour des problèmes comme le rendu de monnaie ; la mémoire utilisée peut augmenter.
Algorithme glouton Choisir à chaque étape l’option qui paraît la meilleure sur le moment. Simple et parfois optimal, à condition que cette propriété soit démontrée.
Retour sur trace Explorer une option, puis revenir en arrière si elle mène à une impasse. Adapté aux contraintes d’un sudoku, mais le nombre de branches peut devenir élevé.

La différence entre diviser pour régner et programmation dynamique est particulièrement utile. Avec le tri fusion, les morceaux sont indépendants ; dans une suite de Fibonacci calculée naïvement, les mêmes valeurs intermédiaires reviennent plusieurs fois, ce qui rend la mémorisation intéressante.

Le rendu de 6 unités montre le piège du choix glouton

Prends un système de pièces de valeurs 1, 3 et 4, puis cherche à rendre 6 unités avec le moins de pièces possible. Le choix glouton prend d’abord la plus grande pièce, soit 4, puis deux pièces de 1 : il en faut trois.

Pourtant, deux pièces de 3 suffisent. Ici, le choix qui paraît le plus avantageux à chaque étape ne donne donc pas le minimum global. L’étude de Dexter Kozen et Shmuel Zaks sur le rendu de monnaie traite précisément de la question de savoir si une stratégie gloutonne produit toujours une représentation optimale.

La règle pratique est nette : utilise une méthode gloutonne quand tu peux justifier que chaque choix local reste compatible avec une solution optimale. Sinon, la programmation dynamique ou le retour sur trace peuvent explorer les solutions plus sûrement, au prix de calculs ou de mémoire supplémentaires.

La complexité permet de repérer quand une méthode va caler

Un programme peut sembler instantané sur dix valeurs et devenir pénible sur un million. La complexité décrit comment le coût évolue avec la taille de l’entrée, sans dépendre directement d’une marque d’ordinateur ; elle peut mesurer le temps, la mémoire ou un nombre d’opérations pertinent pour le problème.

La notation O(n) indique une croissance proportionnelle à la taille de l’entrée, tandis que O(n log n) augmente plus lentement qu’une comparaison de toutes les paires, dont le coût est souvent de l’ordre de O(n²). Ce sont des ordres de grandeur, pas une prédiction exacte du temps en secondes : l’implémentation et les données comptent aussi.

Un exemple classique aide à sentir l’écart. Le calcul récursif naïf de Fibonacci répète les mêmes appels et croît exponentiellement ; avec mémorisation, chaque valeur intermédiaire est calculée une seule fois, ce qui ramène le nombre d’états à un ordre linéaire. Le cours de programmation dynamique de Princeton présente cette logique de réutilisation des résultats.

Pour choisir, pars de la contrainte qui risque de bloquer

Un énoncé peut demander de trouver, de classer ou d’optimiser ; ce verbe donne déjà une première piste. Ensuite, regarde si les données sont triées, si les sous-problèmes se répètent et si une réponse approchée suffit.

Situation Approche à envisager Vérification utile
Petite liste sans ordre particulier Recherche séquentielle Le coût d’un tri préalable serait-il justifié ?
Liste déjà triée Recherche dichotomique Les données respectent-elles réellement l’ordre requis ?
Problème découpable en parties indépendantes Diviser pour régner Comment combiner les solutions partielles ?
Sous-problèmes répétés avec optimum recherché Programmation dynamique Quels états faut-il mémoriser ?
Choix local intuitif dans une optimisation Glouton, sous réserve de preuve Existe-t-il un contre-exemple comme les pièces 1, 3 et 4 ?

Un dernier piège consiste à confondre récursivité et stratégie algorithmique. La récursivité décrit une fonction qui s’appelle elle-même ; elle peut servir au tri fusion ou au retour sur trace, mais ne garantit à elle seule ni rapidité ni élégance.

Un bon choix commence par une preuve simple

Avant d’optimiser le code, vérifie qu’il termine et qu’il produit la réponse attendue, y compris sur une entrée vide, un élément unique ou des valeurs répétées. Je privilégierais d’abord une méthode correcte et lisible, puis une optimisation guidée par la taille des données et la complexité observée sur le papier.

En pratique, nommer le type d’algorithme est un début, pas une décision complète. Demande-toi ce qui se répète, ce qui peut être découpé, et si chaque choix local peut être justifié : ces trois questions écartent déjà bien des solutions séduisantes mais fausses.

Questions fréquentes

Le tri décrit l’objectif, c’est-à-dire réorganiser une liste, tandis que diviser pour régner décrit la méthode utilisée. Le tri fusion appartient donc aux deux catégories : c’est un algorithme de tri qui découpe les données en sous-problèmes, puis combine leurs résultats.

La programmation dynamique convient lorsque des sous-problèmes se répètent et que leurs résultats peuvent être mémorisés. Diviser pour régner est plutôt adapté à des sous-problèmes indépendants, comme dans le tri fusion, dont les solutions sont ensuite combinées.

La méthode gloutonne choisit d’abord la plus grande pièce : elle prend 4, puis deux pièces de 1, soit trois pièces. Pourtant, deux pièces de 3 suffisent. Ce choix local n’est donc pas optimal globalement, sauf si cette propriété a été démontrée pour le problème étudié.

Elle estime l’évolution du temps de calcul ou de la mémoire lorsque la taille de l’entrée augmente. Un coût en O(n) croît proportionnellement, O(n log n) reste généralement inférieur à O(n²), et la mémorisation de Fibonacci évite les répétitions du calcul récursif naïf en ramenant le nombre d’états à un ordre linéaire.

Évaluer l'article

Note: 0.00 Nombre de votes: 0

Tags:

programmation dynamique complexité récursivité tri algorithmes gloutons

Partager l'article

Écrire un commentaire