Programmation avancée en C++ TD 1 – Complexité Algorithmique
Définition :
La complexité algorithmique fait référence à l'analyse de la performance des algorithmes, en
particulier la quantité de ressources telles que le temps d'exécution ou la mémoire qu'un
algorithme utilise pour résoudre un problème donné.
En d'autres termes, la complexité algorithmique mesure la difficulté de résoudre un
problème à l'aide d'un algorithme en fonction de la taille de l'entrée du problème. La taille
de l'entrée peut être définie de différentes manières, en fonction du problème à résoudre,
mais elle est généralement liée à la quantité de données à traiter.
La complexité algorithmique peut être exprimée en termes de notation big O, qui indique la
croissance asymptotique de la complexité en fonction de la taille de l'entrée. Par exemple, si
un algorithme a une complexité temporelle de O(n^2), cela signifie que le temps d'exécution
de l'algorithme augmentera quadratiquement avec la taille de l'entrée.
La complexité algorithmique est un concept important en informatique car elle permet aux
programmeurs et aux ingénieurs logiciels de concevoir des algorithmes efficaces pour
résoudre des problèmes de manière optimale. En comprenant la complexité de leurs
algorithmes, ils peuvent choisir le meilleur algorithme pour un problème donné et éviter les
inefficacités inutiles.
Types :
Il existe deux types de complexité algorithmique: la complexité temporelle et la complexité
spatiale.
Complexité temporelle:
La complexité temporelle d'un algorithme mesure la quantité de temps que celui-ci prend
pour résoudre un problème en fonction de la taille de l'entrée. Elle indique le nombre
d'opérations de base effectuées par l'algorithme pour une entrée donnée. La complexité
temporelle est généralement exprimée en notation Big O, ce qui donne une estimation de la
croissance asymptotique de la complexité en fonction de la taille de l'entrée.
Complexité spatiale:
La complexité spatiale d'un algorithme mesure la quantité de mémoire utilisée par celui-ci
pour résoudre un problème en fonction de la taille de l'entrée. Elle indique la quantité
d'espace de stockage nécessaire pour stocker les données de l'entrée ainsi que les variables
internes utilisées par l'algorithme. La complexité spatiale est également généralement
exprimée en notation Big O.
En résumé, la complexité temporelle et la complexité spatiale sont toutes deux importantes
pour évaluer la performance des algorithmes. La complexité temporelle mesure la vitesse
d'exécution de l'algorithme, tandis que la complexité spatiale mesure la quantité de
mémoire nécessaire pour l'exécuter.
Types de la complexité temporelle:
Il existe plusieurs types de complexité algorithmique temporelle, en fonction de la manière
dont la croissance du temps d'exécution de l'algorithme est liée à la taille de l'entrée. Voici
quelques-uns des types de complexité les plus couramment utilisés:
O(1) - complexité constante: le temps d'exécution de l'algorithme reste constant quelle que
soit la taille de l'entrée. Cela signifie que l'algorithme a une performance très rapide et est
considéré comme très efficace.
O(log n) - complexité logarithmique: le temps d'exécution de l'algorithme croît de manière
logarithmique en fonction de la taille de l'entrée. Les algorithmes avec une complexité
logarithmique sont également considérés comme très efficaces.
O(n) - complexité linéaire: le temps d'exécution de l'algorithme croît linéairement en
fonction de la taille de l'entrée. Les algorithmes avec une complexité linéaire sont également
considérés comme relativement efficaces.
O(n log n) - complexité quasi-linéaire: le temps d'exécution de l'algorithme croît presque
linéairement en fonction de la taille de l'entrée. Les algorithmes avec une complexité quasi-
linéaire sont également considérés comme relativement efficaces.
O(n^2) - complexité quadratique: le temps d'exécution de l'algorithme croît de manière
quadratique en fonction de la taille de l'entrée. Les algorithmes avec une complexité
quadratique sont considérés comme relativement inefficaces.
O(2^n) - complexité exponentielle: le temps d'exécution de l'algorithme croît
exponentiellement en fonction de la taille de l'entrée. Les algorithmes avec une complexité
exponentielle sont considérés comme très inefficaces.
Il existe également d'autres types de complexité algorithmique, tels que la complexité
cubique (O(n^3)), la complexité polynomiale (O(n^k) où k est une constante), et la
complexité factorielle (O(n!)), mais ils sont moins courants.
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
---------------------------------________________-------------------------___________________--------
____________________--------------------------________________------------------------------_____
Exercice 1
Calculer les complexités temporelles, au pire cas, des portions de programmes suivantes :
1-
for(i=0 ;i<n ;i++){
for (j=0;j<i;j++){
Traitement ; // instructions élémentaires
}
}
La complexité temporelle de ce programme est de O(n^2) au pire cas.
Pour comprendre pourquoi, examinons combien de fois les instructions élémentaires sont
exécutées. Lorsque i = 0, le traitement n'est pas exécuté. Lorsque i = 1, le traitement est
exécuté une fois, lorsque j = 0. Lorsque i = 2, le traitement est exécuté deux fois, lorsque j = 0
et j = 1. En général, lorsque i = k, le traitement est exécuté k fois, lorsque j = 0, 1, 2, ..., k-1.
Le nombre total d'exécutions de traitement est donc la somme des premiers n nombres
entiers, ce qui est égal à n(n+1)/2. En notation de Landau, cela se simplifie à O(n^2). Ainsi, la
complexité temporelle au pire cas de cette portion de programme est de O(n^2).
2-
j=0 ;
for(i=1 ;j<=n ;i++){
j=j+i ;
}
La complexité temporelle de ce programme est de O(sqrt(n)) au pire cas.
Le programme effectue une boucle while où la condition d'arrêt est que j dépasse n. À
chaque itération, i est incrémenté et j est mis à jour en ajoutant i à sa valeur courante. Par
conséquent, après k itérations, la valeur de j est :
j = 1 + 2 + ... + k
C'est la somme des k premiers nombres entiers. Cette somme peut être exprimée comme
suit :
j = k(k+1)/2
La condition d'arrêt de la boucle while est j > n, donc k(k+1)/2 > n. En résolvant cette
inéquation pour k, on obtient :
k^2 + k - 2n > 0
La solution de cette inéquation est :
k > (-1 + sqrt(1 + 8n))/2
Comme la boucle while s'arrête lorsque k atteint cette valeur, la complexité temporelle au
pire cas de ce programme est de O(sqrt(n)).
3-
a) for(i=1 ;i<n ;i*=2){Traitement ;} // des instructions élémentaires;
b) for(i=1 ;i<n ;i*=3){Traitement ;}
c) for(i=0 ;i<n ;i+=2){Traitement ;}
d) for(i=1 ;i<n ;i/=2){Traitement ;}
e) for(i=1 ;i<n ;i/=3){Traitement ;}
f) for(i=n ;i>1 ;i--){Traitement ;}
g) for(i=n ;i>1 ;i/=2){Traitement ;}
a) La boucle for s'exécute log(n) fois, car i est multiplié par 2 à chaque itération. La
complexité temporelle est donc O(log(n)).
b) La boucle for s'exécute log_3(n) fois, car i est multiplié par 3 à chaque itération. La
complexité temporelle est donc O(log_3(n)).
c) La boucle for s'exécute n/2 fois, car i est incrémenté de 2 à chaque itération. La
complexité temporelle est donc O(n).
d) La boucle for s'exécute log(n) fois, car i est divisé par 2 à chaque itération. La complexité
temporelle est donc O(log(n)).
e) La boucle for s'exécute log_3(n) fois, car i est divisé par 3 à chaque itération. La
complexité temporelle est donc O(log_3(n)).
f) La boucle for s'exécute n-1 fois. La complexité temporelle est donc O(n).
g) La boucle for s'exécute log_2(n) fois, car i est divisé par 2 à chaque itération. La
complexité temporelle est donc O(log(n)).
4-
for(i=0 ;i<n ;i++){
for(j=1 ;j<n ;j*=2){
Traitement ; //Inst. Elém.
}
}
La boucle externe s'exécute n fois. Pour chaque itération de la boucle externe, la boucle
interne s'exécute log(n) fois car j est multiplié par 2 à chaque itération. Ainsi, le traitement à
l'intérieur des deux boucles est exécuté n * log(n) fois.
La complexité temporelle de cette portion de code est donc O(n log(n)).
5-
i=1 ; k=1 ;
while(k<n){
Traitement ; //Inst. Elém. k=k+i ; i++ ;
La boucle while s'exécute tant que k est inférieur à n. À chaque itération, k est incrémenté
de i et i est incrémenté de 1. Ainsi, le nombre d'itérations de la boucle while dépend de la
valeur de n, mais la croissance de k est dépendante de la somme des entiers positifs jusqu'à
i. Cette somme est égale à i*(i+1)/2.
Pour déterminer la complexité temporelle de cette portion de code, il faut trouver la plus
grande valeur de i telle que i*(i+1)/2 est inférieure ou égale à n. On a donc i*(i+1)/2 ≤ n, ce
qui peut être réécrit comme i^2 + i - 2n ≤ 0.
En résolvant l'inéquation quadratique, on obtient que i ≤ (-1 + sqrt(1 + 8n)) / 2. Ainsi, le
nombre d'itérations de la boucle while est borné par O(sqrt(n)).
La complexité de Traitement ; //Inst. Elém. est O(1), donc la complexité temporelle totale de
cette portion de code est O(sqrt(n)).
6-
s=0
for(i=1 ;i<n ;i*=2){
s++ ;
}
for(i=1 ;i<s ;i*=2){
Traitement ;
}
La première boucle for s'exécute log(n) fois, car i est multiplié par 2 à chaque itération. Dans
cette boucle, la variable s est incrémentée à chaque itération. À la fin de la boucle, s contient
la valeur de log(n), car i atteint la valeur maximale de 2^log(n) à la dernière itération.
La deuxième boucle for s'exécute log(s) fois, car i est multiplié par 2 à chaque itération.
Donc, le traitement à l'intérieur de la deuxième boucle for est exécuté log(log(n)) fois.
La complexité temporelle du traitement à l'intérieur de la deuxième boucle for est O(1).
Ainsi, la complexité temporelle totale de cette portion de code est O(log(n) + log(log(n))), qui
est équivalent à O(log(n)).
Exercice 2
Calculer les complexités temporelles, au pire cas, des fonctions suivantes :
1-
int fct1(int n){
int i,j ;
int s=0 ;
for(i=0 ;i<n ;i++){
j=0 ;
while (j*j<i){
s++ ;
j++ ;
}
}
return s ;
}
La boucle externe for s'exécute n fois. Pour chaque itération de cette boucle, la boucle while
s'exécute jusqu'à ce que j² soit supérieur ou égal à i. Donc, la boucle while s'exécute pour
des valeurs de j allant de 0 à la racine carrée de i. Ainsi, le traitement à l'intérieur des deux
boucles est exécuté pour des valeurs de j allant de 0 à la racine carrée de i pour chaque
valeur de i allant de 0 à n.
Le nombre total d'itérations de la boucle while est donc la somme de la racine carrée de
chaque nombre de 0 à n. Cette somme peut être approximée à l'aide d'une intégrale. Ainsi,
la complexité temporelle de cette portion de code est approximativement égale à l'intégrale
de x^(1/2) de 0 à n, qui est équivalente à (2/3) * n^(3/2).
La complexité temporelle de Traitement ; //Inst. Elém. est O(1), donc la complexité
temporelle totale de cette portion de code est O(n^(3/2)).
2-
int fct2(int n){ int s=0 ; int i=n ; while (i>1){ s++ ; i/=2 ; } return s ; }
La fonction fct2 calcule le nombre de fois que l'on peut diviser par deux un nombre entier n
avant d'obtenir 1.
La complexité temporelle de la fonction dépend du nombre d'itérations de la boucle while.
Chaque itération divise la valeur de i par deux, ce qui signifie que la boucle se répète jusqu'à
ce que i soit inférieur ou égal à 1.
Supposons que la valeur initiale de n soit une puissance de 2 (par exemple, 2^k pour un
entier positif k). Dans ce cas, le nombre d'itérations est k, car chaque division par deux divise
le nombre de bits de i par deux. Ainsi, la complexité temporelle de fct2 dans le pire des cas
est O(log n), où log désigne le logarithme en base 2.
Cependant, si la valeur initiale de n n'est pas une puissance de 2, la boucle s'exécute
toujours jusqu'à ce que i soit inférieur ou égal à 1, mais le nombre d'itérations peut être
légèrement différent. Le nombre d'itérations peut être exprimé en fonction de la valeur
initiale de n comme suit : nombre d'itérations = ⌈log n⌉, où ⌈x⌉ est la partie entière
supérieure de x. Ainsi, la complexité temporelle de fct2 dans le pire des cas est O(log n).
Dans tous les cas, la complexité temporelle de fct2 est logarithmique en fonction de n.
3-
int fct3(int n){
int j,s=0 ;
int i=n ;
while (i>1){
for(j=0 ;j<n ;j++)
s++ ;
i/=2 ;
}
return s ;
}
La complexité temporelle de ce programme est de O(n log n) au pire cas.
Le programme contient une boucle while qui divise i par 2 à chaque itération jusqu'à ce que i
soit inférieur ou égal à 1. À chaque itération de la boucle while, il y a une boucle for qui
s'exécute n fois. Ainsi, le nombre total d'itérations de la boucle for est n + n/2 + n/4 + ... + 1,
ce qui est égal à 2n(1 - 1/2^log n). En notation de Landau, cela se simplifie à O(n).
Le nombre total d'itérations de la boucle while est log2(n). Ainsi, la complexité temporelle au
pire cas de ce programme est de O(n log n).
4-
int fct4(int n){
int j,s=0 ;
int i=n ;
while (i>1){
for(j=0 ;j<i ;j++)
s++ ;
i/=2 ;
}
return s ;
}
La complexité temporelle de cette fonction dépend du nombre d'itérations de la boucle
while.
La boucle while s'exécute tant que i>1. Initialement, i prend la valeur n. À chaque itération, i
est divisé par deux avec i/=2. Le nombre d'itérations de la boucle est donc égal à log_2(n),
arrondi à l'entier inférieur.
À chaque itération de la boucle while, la boucle for s'exécute i fois. La variable s est donc
incrémentée i fois à chaque itération de la boucle while.
Ainsi, la complexité temporelle de cette fonction est de O(n log n) dans le pire des cas, car la
boucle for s'exécute un nombre de fois qui est proportionnel à la valeur de i, qui diminue de
moitié à chaque itération de la boucle while.
5-
bool rech1(char ch[], char c){
int i=0 ;
while (i<strlen(ch)){
if(ch[i]==c)
return true ;
else
i++ ;
}
Return false ;
}
La complexité temporelle de cette fonction dépend du nombre d'itérations de la boucle
while.
La boucle while s'exécute tant que i<strlen(ch). La fonction strlen(ch) retourne la longueur
de la chaîne de caractères ch. Le nombre d'itérations de la boucle dépend donc de la
longueur de la chaîne ch. Dans le pire des cas, la boucle doit parcourir toute la chaîne de
caractères ch pour trouver le caractère recherché c.
À chaque itération de la boucle, il y a une comparaison entre le caractère courant ch[i] et le
caractère recherché c. Ainsi, la complexité temporelle de cette fonction est de O(n), où n est
la longueur de la chaîne de caractères ch, dans le pire des cas.
6-
bool rech2(char ch[], char c){
int i=0 ;
int n=strlen(ch))
while(i<n){
if (ch[i]==c)
return true ;
else
i++ ;
}
return false ;
}
La complexité temporelle de cette fonction est similaire à celle de la fonction rech1, car les
différences entre ces deux fonctions sont mineures.
La boucle while s'exécute tant que i<n, où n est la longueur de la chaîne de caractères ch, qui
est calculée une fois avec la fonction strlen. Ainsi, le nombre d'itérations de la boucle est
déterminé au début de l'exécution de la fonction et ne change pas par la suite.
À chaque itération de la boucle, il y a une comparaison entre le caractère courant ch[i] et le
caractère recherché c. Ainsi, la complexité temporelle de cette fonction est également de
O(n), où n est la longueur de la chaîne de caractères ch, dans le pire des cas.
Exercice 3 (Puissance récursive)
On voudrait calculer la puissance 𝑥
𝑛
(x>0) de manière récursive en minimisant le nombre de multiplications.
Considérons les deux suites récurrentes suivantes :
{
𝑢0 = 1
𝑢𝑛 = 𝑥𝑢𝑛−1, 𝑛 > 0
,{
𝑣0 = 1
𝑣1 = 𝑥
𝑣2𝑛 = 𝑣𝑛
2
𝑣2𝑛+1 = 𝑥𝑣2𝑛
1- Ecrire, en C++, les fonctions récursives 𝒑𝒖𝒊𝒔𝒔𝟏 et 𝒑𝒖𝒊𝒔𝒔𝟐 correspondant
respectivement aux deux suites (𝑢𝑛) et (𝑣𝑛).
Voici les fonctions récursives en C++ correspondant aux deux suites récurrentes :
// Fonction récursive pour la suite u_n
double puiss1(double x, int n) {
if (n == 0) {
return 1.0;
} else {
double u_n_minus_1 = puiss1(x, n-1);
return x * u_n_minus_1;
}
}
// Fonction récursive pour la suite v_n
double puiss2(double x, int n) {
if (n == 0) {
return 1.0;
} else if (n % 2 == 0) {
double v_n_over_2 = puiss2(x, n/2);
return v_n_over_2 * v_n_over_2;
} else {
double v_n_minus_1 = puiss2(x, n-1);
return x * v_n_minus_1;
}
}
La fonction puiss1 calcule le terme de la suite u_n correspondant à l'indice n en effectuant n-
1 multiplications de x. Cette méthode n'est pas optimale, car elle effectue un grand nombre
de multiplications, même pour de petites valeurs de n.
La fonction puiss2 utilise une méthode plus optimale pour minimiser le nombre de
multiplications. Elle utilise la propriété suivante : x^n = (x^2)^(n/2) si n est pair, et x^n = x *
x^(n-1) si n est impair. Ainsi, la fonction calcule la valeur de x^(n/2) de manière récursive et
l'utilise pour calculer x^n, en effectuant une seule multiplication si n est impair ou en
effectuant n/2 multiplications si n est pair. Cette méthode réduit considérablement le
nombre de multiplications nécessaires pour calculer x^n.
2- Calculer les complexités (en pire cas) des deux fonctions puiss1 et puiss2.
La complexité de la fonction puiss1 est O(n) car elle appelle récursivement la fonction avec
un argument n diminué de 1 à chaque appel, et donc il y aura n appels récursifs.
La complexité de la fonction puiss2 est O(log n) car à chaque appel, la valeur de n est divisée
par 2, ce qui réduit considérablement le nombre d'appels récursifs nécessaires pour arriver
au cas de base.
3- Comparer l’ordre de grandeur des deux complexités pour 𝑛 = 1000 et 𝑛 = 10000 pour
constater le grand gain apporté par la deuxième fonction 𝑝𝑢𝑖𝑠𝑠2.
Pour n = 1000, la fonction puiss1 effectuera environ 1000 multiplications, tandis que la
fonction puiss2 effectuera seulement environ 10 multiplications. Pour n = 10000, la
fonction puiss1 effectuera environ 10000 multiplications, tandis que la fonction puiss2
effectuera seulement environ 14 multiplications. On constate donc un gain considérable
en utilisant la deuxième fonction pour des valeurs de n élevées.
Exercice 4 (Recherche dichotomique)
1- Donner la complexité temporelle en pire cas de la fonction rechDichotomie.
La complexité temporelle en pire cas de la fonction rechDichotomie est O(log n), car à
chaque étape de la boucle while, on divise l'intervalle de recherche en deux parties égales.
2- Comparer le temps d’exécution (sur votre machine) de la recherche dichotomique
avec celui de la recherche séquentielle, vue dans le cours, pour n=1000 et n=10000. On
pourra remplir le tableau par des nombres aléatoires, en utilisant la fonction rand() et le
trier par un algorithme de tri déjà étudié.
Pour comparer le temps d'exécution de la recherche dichotomique et de la recherche
séquentielle, nous allons générer des tableaux de tailles 1000 et 10000, remplis de nombres
aléatoires compris entre 0 et 9999, et les trier en utilisant l'algorithme de tri quicksort. Nous
allons ensuite mesurer le temps d'exécution de chaque algorithme de recherche pour
trouver un élément aléatoire dans le tableau.
Voici le code en C++ pour effectuer ces mesures :
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
int rechercheSequentielle(int T[], int n, int x0) {
for (int i = 0; i < n; i++) {
if (T[i] == x0) {
return i;
}
}
return -1;
}
int rechercheDichotomie(int T[], int n, int x0) {
int debut = 0, fin = n - 1;
int position = -1;
int milieu;
while ((debut <= fin) && (position == -1)) {
milieu = (fin + debut) / 2;
if (x0 < T[milieu]) {
fin = milieu - 1;
} else if (x0 > T[milieu]) {
debut = milieu + 1;
} else {
position = milieu;
}
}
return position;
}
int main() {
const int N1 = 1000;
const int N2 = 10000;
int T1[N1], T2[N2];
srand(time(0));
for (int i = 0; i < N1; i++) {
T1[i] = rand() % 10000;
}
for (int i = 0; i < N2; i++) {
T2[i] = rand() % 10000;
}
sort(T1, T1 + N1);
sort(T2, T2 + N2);
clock_t debut, fin;
int x1 = T1[rand() % N1];
int x2 = T2[rand() % N2];
debut = clock();
int pos1 = rechercheSequentielle(T1, N1, x1);
fin = clock();
double tempsSeq1 = (double) (fin - debut) / CLOCKS_PER_SEC;
debut = clock();
int pos2 = rechercheDichotomie(T1, N1, x1);
fin = clock();
double tempsDicho1 = (double) (fin - debut) / CLOCKS_PER_SEC;
debut = clock();
int pos3 = rechercheSequentielle(T2, N2, x2);
fin = clock();
double tempsSeq2 = (double) (fin - debut) / CLOCKS_PER_SEC;
debut = clock();
int pos4 = rechercheDichotomie(T2, N2, x2);
fin = clock();
double tempsDicho2 = (double) (fin - debut) / CLOCKS_PER_SEC;
cout << "Pour N = " << N1 << ", x = " << x1 << endl;
cout << "Temps de recherche séquentielle : " << tempsSeq1 << " secondes" << endl;
cout << "Temps de recherche dichotomique : " << tempsDicho1 << " secondes" <<
Exercice 5 (Moyennes préfixes)
La complexité temporelle de la fonction moyPrefixe1 est O(n^2) car il y a une boucle for
imbriquée à l'intérieur de l'autre boucle for. A chaque itération de la boucle extérieure, la
boucle intérieure effectue i opérations, ce qui donne une complexité totale de O(1 + 2 + 3 +
... + n) = O(n^2).
La complexité temporelle de la fonction moyPrefixe2 est O(n) car il y a une seule boucle for
qui parcourt le tableau une fois. A chaque itération de la boucle, une opération constante
est effectuée, ce qui donne une complexité totale de O(n).
