La méthode du « Diviser pour régner » est un paradigme de programmation imaginé pour améliorer la complexité d’un programme. Regardons ce que cela donne en Python.
Le principe du « diviser pour régner » en Python
On souhaite calculer N=752. La méthode basique consiste à multiplier le nombre 7 par lui-même 52 fois… Ce qui n’est pas très rapide !
L’idée consiste donc à diviser le problème en 2 : on va calculer 726×726, c’est-à-dire (726)2. Là, il n’y a plus que 26 + 1 opérations (26 multiplications pour calculer 726, et une dernière pour faire le carré du résultat.
On recommence ensuite avec 726 : on le calcule en faisant (713)2. N se calcule alors en 13+1+1 opérations au lieu de 52 initialement.
On ne s’arrête pas là, bien entendu : on continue tant que l’on peut utiliser ce principe :N=752=(726)2=((713)2)2=[[(76)2×7]2]2=[[((73)2)2×7]2]2=[[((72×7)2)2×7]2]2
Le principe est, vous l’avez peut-être remarqué, récursif.
Implémentation en Python du « diviser pour régner »
Nous allons écrire une fonction « puissance(x,n) » basée sur ce paradigme, où x et n sont deux entiers (positif pour n). Pour cela, nous allons prendre en compte que:{x0=0xn=(x2)n/2 si n est pairxn=x(x2)(n−1)/2 si n est impairCela donne alors la fonction suivante (exponentiation rapide):
def puissance(x,n):
if n == 0:
return 1
elif n%2 == 0:
return puissance(x*x , n/2)
else:
return x * puissance(x*x , (n-1)/2)
print(puissance(2,9))Complexité
Notons C(n) la complexité de la fonction « puissance(n) ». Comme nous divisons en deux le problème à chaque appel de la fonction, on peut estimer que : C(n)=aC(n/2)+f(n)où f(n) est la complexité totale due au partage et à la recombinaison, et où:
- a=1 si la fonction s’applique à l’un des deux sous-problèmes;
- a=2 si la fonction s’applique aux deux sous-problèmes.
Dans le cas de l’exponentiation rapide, a = 1 et:
- si n est pair, C(n)=C(n/2)+1;
- si n est impair, C(n)=C(n−12)+2.
On arrive à prouver (sans doute au-delà du programme de Terminale NSI) que la complexité de l’exponentiation rapide est C(n)=O(lnn).