Bonjour,

J'aimerais avoir de l'aide concernant la complexité en temps et espace d'une fonction.
Voici le code :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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.