Chapitre 6
Diviser pour régner
Principes généraux
Pour résoudre un problème de taille N, un algorithme récursif fonctionne en général de la manière suivante :
Extraire ou construire à partir de notre entrée un problème de taille N-1
Résoudre le problème de taille N-1 (récursivité)
Utiliser cette solution pour résoudre le problème initial
La méthode diviser pour régner consiste, pour résoudre un problème de taille N, à :
(Diviser) : partager le problème en sous-problèmes (par exemple de taille N/2)
(Régner) : résoudre ces différents sous-problèmes (généralement récursivement)
(Combiner) : fusionner les solutions pour obtenir la solution du problème initial
On obtient en général moins d'appels récursifs. Dans certains cas la méthode diviser pour régner donne un algorithme de résolution plus rapide.
Exponentiation rapide
On peut définir xn de façon récursive :
x0 = 1
xn = x * xn-1
Ce qui se traduit en Python par cette fonction :
La complexité (en regardant le nombre de multiplication) de cet algorithme est en O(n), il faudra donc faire 100 multiplications pour calculer x100 .
On peut mesurer le temps d’exécution en utilisant la bibliothèque timeit :
À faire
Écrire ce programme.
À partir de quelle valeur de n on dépasse les capacités de la pile ?
Une autre approche (Diviser pour régner)
On peut définir xn d'une autre façon :
x0 = 1
Si n est pair : xn = (xn/2)2
Si n est impair : xn = x*(x(n-1)/2)2
Ce qui se traduit en Python par cette fonction :
La complexité (en regardant le nombre de multiplication) de cet algorithme est en O(log2(n)), il faudra donc faire 7 multiplications pour calculer x128 .
À faire
Écrire ce programme.
Vérifier que la différence des temps d’exécutions des deux programmes est évidente pour par exemple le calcul de 2500
Vérifier également que le second programme permet de calculer 21000
