Calcul de puissance en O(log n)
Résolu/Fermé
azerty27
Messages postés
6
Date d'inscription
mercredi 14 août 2013
Statut
Membre
Dernière intervention
22 juin 2014
-
14 août 2013 à 16:46
azerty27 Messages postés 6 Date d'inscription mercredi 14 août 2013 Statut Membre Dernière intervention 22 juin 2014 - 15 août 2013 à 11:43
azerty27 Messages postés 6 Date d'inscription mercredi 14 août 2013 Statut Membre Dernière intervention 22 juin 2014 - 15 août 2013 à 11:43
A voir également:
- Log(n)
- Log me in - Télécharger - Connexion à distance
- View rescue log - Guide
- 0.log miui - Forum Logiciels
- Le fichier de log n'a pas pu être créé dans /var/www/html/glpi/files/_log. - Forum Gestion de parc
- Failed to send host log message virtualbox - Forum Ubuntu
1 réponse
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
Modifié par KX le 14/08/2013 à 19:33
Modifié par KX le 14/08/2013 à 19:33
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
15 août 2013 à 11:43