Complexité algorithmique temps/espace
Bonjour,
J'aimerais avoir de l'aide concernant la complexité en temps et espace d'une fonction.
Voici le code :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static int pow(int x, int y)
{
if(y < 0)
return 0;
int r = 1;
for(int b = 1; b <= y; b *= 2; x *= x)
{
if((y & b) != 0)
r *= x;
}
return r;
} |
Et voici quelques informations :
- Le type primitif int est remplacé par une classe capable de représenter des entiers de taille arbitrairement grande. Cette classe représente un entier codé sur n bits à l'aide d'une quantité de mémoire égale à O(n).
- La comparaison de deux nombres codés sur n1 et n2 bits ainsi que l'opération "&" nécessitent un temps et une quantité de mémoire tous deux égaux à O(max(n1, n2)).
- La multiplication de deux nombres codés sur n1 et n2 bits nécessitent un temps de O(n1 * n2) et une quantité de mémoire égale à O(n1 + n2).
Merci.
Bien à vous.
