Complexité Algorithmique

stocke les résultats en C.

2. Déterminer la fonction de temps maximale (”worst case”) T(n) pour des matrices de taille n. (vous

devez calculer le nombre d’opérations)

3. Déterminer la complexité asymptotique pour calculer des matrices de taille n.

Exercice 2 (6 points)

1- La technique de hashage permet d’accélérer l’algorithme de recherche d’un élément dans un

ensemble de données. Quel serait la complexité asymptotique d’un tel algorithme ? Expliquer

brièvement la gestion des collisions avec le hashage double.

2- Etant donné un ordinateur X qui permet de traiter 10 milliards d’opérations élémentaires par

seconde. Quel est le temps nécessaire en pour exécuter le programme P1 ?

P1

i=1 \\(1 opération élémentaire )

While (i<1018 ) \\(1 opérations

élémentaires)

{ i=i*2 } \\(2 opérations

élémentaires)

P2

i=1 \\(1 opération élémentaire )

While (i<1018 ) \\(1 opération

élémentaire)

{ i=i+10 } \\(2 opérations

élémentaires)

Exercice 3 (6 points) Calculer la complexité asymptotique des algorithmes suivants en fonction de

n : (Donner le détail de calcul)

int m=1 ;int m2=1;

While ( m2<=n ) {

int j=1; int x=0;

While (j < m2)

{ x=x+1; j=j*2 }

m2=m*2

}

int i =1 ;int K=1;

While ( i<=n || k>=n )

{

int j=i ; int x=0;

While (j < k)

{ x=x+1; j++; }

i=i+2;

K=K*2

}

n2=n

i = 0

While (n2 > 0 && i<n) {

T[i] = n2 mod 2

n2 = n2 / 2

i = i + 1

}