Calcul de puissance en O(log n)
Résolu
azerty27
Messages postés
6
Date d'inscription
Statut
Membre
Dernière intervention
-
azerty27 Messages postés 6 Date d'inscription Statut Membre Dernière intervention -
azerty27 Messages postés 6 Date d'inscription Statut Membre Dernière intervention -
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.
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.
A voir également:
- Log(n)
- Vpn no log - Guide
- View rescue log - Guide
- Log freebox - Forum Freebox
- Log crash windows - Guide
- 0.log miui - Forum Logiciels
1 réponse
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...
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
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
azerty27
Messages postés
6
Date d'inscription
Statut
Membre
Dernière intervention
J'ai bien compris. Merci infiniment pour votre aide.
