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)\).