Algorithmique et programmation C
TD5 : La complexité
L. Sternberger
13 novembre 2006
Exercice 1
Écrire un algorithme itératif donnant l’indice de la première occurence d’un élé-
ment minimal dans un tableau de N entiers (on suppose N ≥ 2). Exemple : si la suite
des élément du tableau est 5,2,4,2,1,7,9,4,1,1, il y a 3 occurrences de l’élément
minimal et l’indice de sa première occurence est 5. La fonction pourra par exemple
s’écrire int min(int tab[N]) ;.
Évaluer sa complexité.
Corrigé
int min(int tab[N])
{
int i;
// 1 première affectation de index
int index = 0;
// n comparaisons + n-1 affectations
for(i=1; i<N; i++)
{
// n-1 comparaisons
// dans le pire des cas, n-1 affectations
if(tab[i] < tab[index])
index = i;
}
return index;
}
– complexité : T (n) = 1 + n + (n − 1) + 2 ∗ (n − 1) = 4n − 1 ;
– ordre : O(n) ;
1
Exercice 2
On appelle MiniMax d’une matrice d’entiers la valeur minimale des maxima de
chaque ligne.
Écrire un algorithme qui retourne la valeur MiniMax d’une matrice d’entiers n × m.
On suppose N ≥ 1 et M ≥ 1. La fonction pourra être int MiniMax(int tab[N][M]) ;.
Corrigé
int MiniMax(int tab[N][M])
{
int i;
int j;
int max;
int minimax;
// (n-1) comparaisons
// n affectations
Advertisement
for(i=0; i<n; i++)
{
// n initialisations du max. pour chaque nouvelle ligne
max = tab[i][0];
// (n-1)*m comparaisons
// (n-1)(m-1) affectations
for(j=1; j<m; j++)
{
// (n-1)(m-1) comparaisons
// (n-1)(m-1) affectations
if(tab[i][j] < max)
max = tab[i][j];
}
// m comparaisons
// 1 affectation
if(i==0)
minimax = max;
// n comparaisons
// (n-1) comparaisons
else if(minimax > max)
minimax = max;
}
return minimax;
}
– complexité : T (n) = (n − 1) + n + n + (n − 1) ∗ m + (n − 1)(m − 1) + (n − 1)(m −
2
1) + (n − 1)(m − 1) + m + 1 + n + (n − 1) = 5nm + n − 4m + 3 ;
– ordre : O(nm), si m = n alors on est en O(n2) ;
Exercice 3
1. Donner une fonction récursive puissance(a,i) qui calcule ai.
2. Calculer la complexité de l’algorithme précédent (puissance).
3. Donner une fonction récursive somme(a,n) qui calcule ∑n
i=0 ai.
4. Calculer la complexité de l’algorithme précédent (somme).
Corrigé
int puissance(a,i)
{
if(i==0)
return 1;
else
return (a*puissance(a,i-1));
}
T (p(a, i)) = n d’où complexité en O(n).
int somme(a,n)
Advertisement
{
if(n==0)
return 1;
else
return (puissance(a,n)+somme(a,n-1));
}
T (s(a, n)) = T (p(a, n)) + T (somme(a, n − 1))
= T (p(a, n)) + T (p(a, n − 1)) + T (somme(a, n − 2))
= T (p(a, n)) + T (p(a, n − 1)) + T (p(a, n − 2)) + T (p(a, n − 3)) + ... + T (p(a, 1)) + 1
= n + n − 1 + n − 2 + n − 3 + n − 4 + ... + 3 + 2 + 1
= somme(1 à n)(i)
= (n(n + 1))/2 d’où complexité en O(n2).
Exercice 4
Que calcule la fonction suivante :
int quid(int x, int n)
{
if (n==0)
3
return 1;
if (n==1)
return x;
else
return (quid(x,n-1)*x);
}
Quelle est sa complexité ?
Corrigé
La fonction calcule xn pour tout entier x et pour tout entier n ≥ 0.
Dans le pire des cas, on a :
T (quid(x, n)) = 3 + T (quid(x, n − 1))
= 3 + 3 + T (quid(x, n − 2)
= 3 + 3 + ... + 3 + T (quid(x, 1))
= 3 + 3 + ... + 3 + 2
|
{z
}
n−1 f ois
= 3n − 1
d’où la complexité est en O(n).
Exercice 5
Dire ce que définissent les fonctions suivantes, puis calculer leur complexité, pour
rec1 en nombre de multiplications par 2 et pour rec2 en nombre d’additions ;
int rec1(int n)
{
if(n == 0)
Advertisement
return 1;
else
return 2*rec1(n-1);
}
int rec2(int n)
{
if(n == 0)
return 1;
else
return (rec2(n-1) + rec2(n-1));
}
Corrigé
1. Ces deux fonctions calculent 2n−1.
4
2. Soient T1(n) (resp. T2(n)) le nombre d’appels récursifs de rec1 (resp. rec2) avec
n comme paramètre.
Pour rec1, on a : T1(0) = 0, T1(1) = 0, T1(2) = 1, T1(3) = 2, ...T1(n) = n − 1.
Pour rec2, on a : T2(0) = 0, T2(1) = 0, T2(2) = 2, T2(3) = 6.
Pour calculer T2(n), il faut comptabiliser les deux appels à rec2(n − 1), ainsi
que tous ceux qu’ils engendrent. On obtient donc : T2(n) = 2T2(n − 1) + 2 =
2n−1 + ... + 21 = 2n − 2.
Si l’on fait l’hypothèse (réaliste) qu’un appel à rec1 coûte la même chose qu’un
appel à rec2, rec1 est plus efficace que rec2.
Exercice 6
Pour cet exercice, on demande d’écrire les spécifications complètes pour chaque
fonction. On rappelle que la somme des r premiers impairs est égale au carré de r.
– Écrivez à l’aide d’une boucle tant que et de l’opération d’addition (exclusive-
ment) une fonction Racine1 calculant la racine carrée entière par défaut d’un
nombre entier positif n donné. La racine carrée entière par défaut r d’un nombre
n vérifie la relation r2 ≤ n ≤ (r + 1)2. Attention à bien vérifier que le résultat est
bon quelque soit la valeur de n (positif ou nul) donné.
– Même question avec une boucle répéter · · · jusqu’à. Vous appellerez cette fonc-
tion Racine2.
– Donnez une version récursive de cette fonction, que vous appellerez Racine3.
– Pour chacune des 3 fonctions, calculez le nombre d’additions et de comparaisons
à effectuer.
Corrigé
#include <stdio.h>
int Racine1(int carre)
{
int impair = 1;
int somme = 0;
int racine = -1;
while (somme <= carre)
Advertisement
{
somme+=impair;
impair+=2;
racine ++;
}
return racine;
}
5
int Racine2(int carre)
{
int impair = 1;
int somme = 0;
int racine = -1;
do
{
racine ++;
somme+=impair;
impair+=2;
}while (somme <= carre);
return racine;
}
int Racine3(int carre, int impair)
{
if (carre < 0)
return -1;
else
return (1 + Racine3(carre-impair, impair+2));
}
main()
{
int carre;
printf("Entrez un carré :\n");
scanf("%d",&carre);
printf("La racine est : %d\n",Racine1(carre));
printf("La racine est : %d\n",Racine2(carre));
printf("La racine est : %d\n",Racine3(carre,1));
}
Pour tout entier n de racine r, on fait toujours
– Racine1 : r + 2 comparaisons et 3(r + 1) additions ;
– Racine2 : r + 1 comparaisons et 3(r + 1) additions ;
– Racine3 : r + 2 comparaisons et 3(r + 1) additions
6