Quelques paradigmes utiles pour construire un algorithme efficace
Méthode :
Un paradigme est une méthode générique qui s'applique dans plusieurs situations algorithmiques. Voici une liste de quelques paradigmes algorithmiques :
L'induction : Ce paradigme donne lieu a des processus itératifs.
Diviser pour régner : Exemples : procédés dichotomiques, mais aussi d'une manière plus générale tous les algorithmes récursifs.
Trouver un ordre "optimal" sur les opérations à effectuer : Exemples : les parcours en profondeur dans les graphes, les utilisations des ordres lexicographiques.
Utiliser une structure de données ad hoc : Cette structure de données doit permettre de réaliser efficacement les opérations de base de l'algorithme. Exemples : arborescences binaires ordonnées de recherche, arborescences bicoloriés, B-arborescences, ?les de priorité.
Stocker des résultats des calculs intermédiaires : Ici intervient le compromis calcul/mémoire. Par exemple pour calculer un sinus on peut utiliser un calcul (développement en série) ou aller chercher une valeur dans une table (si le calcul a déjà été fait).
Utiliser un procédé stochastique (à base de tirages aléatoires) : Les algorithmes randomisés ou probabilistes sont souvent très simples à mettre en œuvre et l'on peut montrer qu'ils donnent le bon résultat avec une forte probabilité[1].