calcul de puissance en O(log n) Résolu

Question

Bonjour,
Je traite actuellement un exercice qui propose d'écrire une méthode double pow(double x, int n) qui élève x à la puissance n et dont la complexité est en O(lg n).
J'ai trouvé un début de solution.
Voici mon programme :

static double pow(double x, int n){
  if(p == 1) return x;
  else{
     if (p%2 == 0)
       return pow(x*x, p/2);
     else
       return x*pow(x*x, p/2);
  }
}
Toutefois, cette solution me semble ne pas convenir concernant sa complexité.
En effet, celle-ci est selon moi en théta(log n).
Un algorithme dont la complexité est en théta(log n) est-il aussi un algorithme en O(lg n) sachant que f(n) = théta(g(n)) équivaut à f(n) = O(g(n)) et f(n) = oméga(g(n)) ?
D'autre part, comment pourrait-on rigoureusement montrer la complexité de cet algorithme ? Y a-t-il une méthode générale ?

Merci beaucoup.

KX · Answer

Les méthodes rigoureuses de démonstration de la complexité sont généralement lié aux démonstrations de récurrence en mathématiques. Mais pour des exemples simples comme ça, un habitué verra tout de suite qu'une dichotomie est de complexité logarithmique, donc l'idée que tu as eu est correct à part que tu t'es mélangé les pinceaux avec p et n...

public static double pow(double x, int n)
{
    if (n == 0)
        return 1;
    
    if (n == 1 || x == 0 || Double.isInfinite(x) || Double.isNaN(x))
        return x;
    
    if (n < 0)
        return pow(1 / x, -n);
    
    if (n % 2 == 0)
        return pow(x * x, n / 2);
    else
        return pow(x * x, n / 2) * x;
}
Démonstration :

Par récurrence, montrons que si n=2^k, le nombre d'appels est k.

Preuve : 

Si k = 0, alors 2^k=1, d'où n=1, donc il y a un seul appel.

Si k > 0, alors pow(x,2^k) = pow(x², (2^k)/2 ) = pow(x², 2^(k-1) ),
Il y a donc un appel de plus que pour k-1 (deux appels de plus que k-2, etc.) donc en tout il y a k appels.

Donc (par récurrence), pour tout k, si n=2^k, le nombre d'appels est k.
Petit calcul de logarithme : si n=2^k, alors k=log2(n), donc le nombre d'appel est log2(n), donc la complexité est logarithmique...

Facile non ? :p
La confiance n'exclut pas le contrôle

Calcul de puissance en O(log n)

1 réponse

Votre réponse

Discussions similaires