Discussion :

[Dimitri_87]

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.

[PRomu@ld]

J'aimerais avoir de l'aide concernant la complexité en temps et espace d'une fonction.

Quelle est exactement ta question ?