USTHB - Faculté d’électronique & d’informatique - Département d’informatique
Module ALGO Av. &Complexité – M1-BioInfo Année 2021-2022
Série 1 - Complexité des algorithmes
Exercice 1
Déterminer la complexité des algorithmes suivants (par rapport au nombre d’itérations
effectuées), où m et n sont deux entiers positifs.
Algorithme A
Algorithme B
i 1;j 1 i 1;j 1
Tant que (i m) et (j n) faire Tant que (i m) ou (j n) faire
i i+1 i i+1
j j+1 j j+1
fait ; fait ;
Algorithme C
i 1;j 1 Algorithme D
i 1;j 1
Tant que (j n) faire
Tant que (j n) faire
si i m
si i m
alors
alors
i i+1 i i+1
sinon sinon
j j+1 j j+1 ; i 1
fsi ; fsi ;
fait ; fait ;
Exercice 2
On considère deux matrices d’entiers A(n,m) et B(m,p).
Ecrire l’algorithme qui calcule le produit des deux matrices A et B dans une matrice C(n, p).
Evaluer la complexité de l’algorithme
Exercice 3
Ecrire l’algorithme de recherche dichotomique d’une valeur dans un vecteur trié de taille n et
calculer sa complexité.
Exercice 4 : Fusion de deux tableaux triés
On dispose de deux tableaux T1[1..n] et T2[1..n] dont les éléments sont triés de façon croissante. On
veut créer un tableau trié T3[1..2n] contenant tous les éléments de T1 et T2. Pour cela on propose
deux algorithmes Fusion_A et Fusion_B.
Fusion_A : initialise T3 avec T1 (déjà trié) et y insère un à un les éléments de T2 de façon à ce que
l’ordre soit respecté.
1 S. BOUKHEDOUMA
Fusion_B : remplit T3 en parcourant simultanément T1 et T2 du début jusqu’à leur fin. Soit i1 et i2 les
indices courant dans T1 et T2, on a 3 cas possible :
Si T1[i1]<T2[i2] alors mettre T1[i1] à la fin de T3 et avancer dans T1
Si T1[i1]>T2[i2] alors mettre T2[i2] à la fin de T3 et avancer dans T2
Sinon mettre T1[i1] puis T2[i2] à la fin de T3 et avancer dans T1 et T2
1. Ecrire les deux algorithmes et déroulez sur l’exemple :
T1= 1 3 5 et T2 = 2 3 4
2. Donnez la complexité, au pire des cas, des algorithmes en fonction de la taille des
données.
3. Quel algorithme choisissez-vous d’implémenter ?
Exercice 5
Etant donné un tableau de n entiers, on cherche à savoir si l’un de ses éléments est égal à la
somme des n-1 autres éléments.
Exemple A= 3 8 -6 3 -1 9
Le 2ème élément de valeur 8 est égal à la somme des 5 autres.
a- Une première méthode consiste pour chaque élément du tableau à calculer la somme
des autres éléments et à vérifier si elle est égale à l’élément. Ecrivez cet algorithme.
Donnez sa complexité.
b- On peut améliorer, au sens de la complexité, l’algorithme précédent. Ecrivez ce
deuxième algorithme et donnez sa complexité.
Exercices supplémentaires
Exercice 6
Soit une liste chainée L de nombres réels et soit x un nombre réel donné.
1. Ecrire une action paramétrée Somme_2 qui vérifie s’il existe deux éléments de T dont
la somme est égale à x. Donner sa complexité en justifiant votre réponse.
On suppose maintenant que la liste est triée dans l’ordre croissant.
Ecrire une action paramétrée Somme_2bis qui résout la question n°1 avec une meilleure
complexité. Justifiez votre réponse.
Exercice 7
Ecrire une action paramétrée qui décompose un nombre entier positif en binaire dans une liste
chainée d’entiers. Calculez la complexité de l’algorithme.
2 S. BOUKHEDOUMA
