Python : diviser pour régner

Ce paradigme de programmation est imaginé pour améliorer la complexité d’un programme.

Le principe

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

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

Supportscreen tag