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=7^{52}\). 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 \( 7^{26} \times 7^{26}\), c’est-à-dire \((7^{26})^2\). Là, il n’y a plus que 26 + 1 opérations (26 multiplications pour calculer \(7^{26}\), et une dernière pour faire le carré du résultat.
On recommence ensuite avec \(7^{26}\) : on le calcule en faisant \( (7^{13})^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 :$$\begin{align}N & = 7^{52}\\&= (7^{26})^2\\&= \big((7^{13})^2\big)^2\\&=\big[[(7^6)^2\times7]^2\big]^2\\&=\big[[\big((7^3)^2\big)^2\times7]^2\big]^2\\&=\big[[\big((7^2\times7)^2\big)^2\times7]^2\big]^2 \end{align}$$
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:$$\begin{cases}x^0 = 0& \\x^n = (x^2)^{n/2} & \text{ si }n\text{ est pair}\\x^n = x(x^2)^{(n-1)/2} & \text{ si }n\text{ est impair} \end{cases}$$Cela 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) = a C(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\left(\frac{n-1}{2}\right) + 2\).
On arrive à prouver (sans doute au-delà du programme de Terminale NSI) que la complexité de l’exponentiation rapide est \(C(n) = O(\ln n)\).