Diviser pour régner en Python

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.

Diviser pour régner en Python
Diviser pour régner 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)\).

Et n’oubliez pas que si vous avez besoin d’une aide, vous pouvez réserver un cour par webcam.

[Retour à la page principale]

Supportscreen tag