Universite de Sfax Annee Universitaire 2014/2015

Institut Superieur d’Informatique Resp. S. Elaoud

et de Multimedia de Sfax duree 30 minutes

Algorithmique avancee et complexite-DEVOIR SURVEILL E-

Soit les fonctions F, F1, F2, F3 et F suivantes:

void F1(int n){

int x=rand()%5, i=0;

while(i<n)

{ if(x<2) x=x*2;

else x++;

}

}

int F2(int n){

for(int i=0; i<n; i++)

for(int j=i; j<n/2; j++)

x++;

return (rand()%4);

}

int F3(int n){

int j, y=0, x=rand()%10;

for(int i=0; i<n; i++)

{ if(x<4||F2(n))

F1(n);

else

{ j=2n; while(j>1){j/=2; y++}

} return y;

}

int F(int n){

if(n==0) return 2;

int y=F3(n);

return y+F(n/2)+F(n/2)+F(n/2);

}

1. Etudier la complexite de F1,F2et F3; Justifier.

2. Donner la complexite moyenne de F1 et F3; Justifier.

3. Etudier la complexite de F; Justifier.

1