2026_TD3_DEV51_Qualite_Algo/COMPTE_RENDU.md

Compte rendu — TD3 : complexité algorithmique

R5.A.04 · Qualité Algorithmique

Groupe : Ryad MEHIRI · Luka PLOUVIER · Jimmy COLOMB-RAVAT

Programme étudié : banque.c. Il génère 30 000 transactions pseudo-aléatoires (graine fixe), calcule une dizaine d'indicateurs (fonctions F1 à F10) et écrit rapport.txt. L'empreinte du rapport doit rester ff68d260a7a58441.

Tailles : n = 30 000 transactions, C = 2 000 clients, J = 1 000 jours, Q = 30 000 requêtes, S = 400 centimes à rendre, k = 8 pièces, L = 120 348 caractères de rapport (6 017 lignes).

---

Résumé

	Avant	Après
Temps, gcc -O2 (médiane de 5 exécutions)	3,05 s	0,061 s (×50)
./evaluer.sh (médiane de 5, en ms)	2 945 ms (2ᵉ essai : 3 855)	124 ms (124 à 142 sur 3 essais)
Empreinte	ff68d260a7a58441	ff68d260a7a58441 ✔
M maximal du fichier (hors alea et generer_transactions)	14 (categorie)	5
Durée de l'exécution profilée (-O0 -pg)	38,10 s	0,05 s
Objectifs de complexité atteints	0 / 10	10 / 10

Il y a 11 commits d'optimisation : un par fonction F1 à F10, plus un pour découper main. À chaque étape, l'empreinte, rapport.txt (octet par octet) et la sortie console restent identiques à ceux de la version d'origine.

---

1. Environnement de mesure

Machine	Intel Core i7-1165G7 (4 cœurs / 8 threads), 7,8 Go de RAM, portable
Système	Windows 11, environnement MSYS de MSYS2
Compilateur	gcc 15.3.0 (-O2 pour les temps, -O0 -g -pg pour les profils)
Profiler	GNU gprof 2.47

Nous avons utilisé l'environnement MSYS, où long fait 64 bits comme sous Linux. En Windows natif (MinGW), unsigned long ne fait que 32 bits et alea() (etat_alea >> 33) ne renvoie que des zéros. Nous l'avons constaté lors du TD1 : les données générées sont alors fausses.

Sur ce portable, le bruit de mesure est important : d'une exécution à l'autre, on observe ±0,2 s sur la version de 1 s, et la version d'origine a donné 2,9 s puis 3,9 s avec evaluer.sh. Nous retenons donc des médianes. Quand un gain était plus petit que ce bruit, nous l'avons vérifié par des exécutions alternées des deux versions (partie 5, F10).

gcc -O2 banque.c -o banque && time ./banque                       # temps (5 fois)
gcc -O0 -g -pg banque.c -o banque_pg && ./banque_pg
gprof -b ./banque_pg gmon.out > profil_avant.txt                  # profil

---

2. Mesure initiale

Exécution	1	2	3	4	5	Médiane
Temps réel, -O2 (s)	4,14	3,02	2,77	3,05	3,57	3,05

Le cours annonçait environ 2,7 s sur la machine de l'enseignant.

Clients distincts   : 2000
Somme des requêtes  : -2624578
Meilleure période   : jours 650 à 986 (3548830)
Paires opposées     : 5832
Façons de rendre 400 : 1960497
Empreinte           : ff68d260a7a58441

---

3. Profil initial (profil_avant.txt)

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 37.93     14.45    14.45                             _mcount_private
 24.41     23.75     9.30        1     9.30     9.30  trier_par_montant
  9.17     27.25     3.50        1     3.50     3.50  nb_facons_rendre
  9.00     30.68     3.43     6017     0.00     0.00  longueur
  5.77     32.88     2.20    30000     0.00     0.00  rechercher_par_id
  5.25     34.88     2.00                             __fentry__
  4.72     36.67     1.80        1     1.80     1.80  nb_paires_opposees
  2.10     37.48     0.80        1     0.80     0.80  meilleure_periode
  0.58     37.70     0.22        1     0.22     0.22  nb_clients_distincts
  0.58     37.91     0.22        1     0.22     0.22  total_par_client
  0.26     38.02     0.10        1     0.10     0.10  total_par_jour
  0.14     38.07     0.06    30000     0.00     0.00  categorie

Le graphe d'appels indique 1 + 266 723 738 appels pour nb_facons_rendre : c'est la récursion. _mcount_private et __fentry__ (16,45 s) sont le code ajouté par -pg à chaque appel de fonction. Presque tous ces appels viennent de F8, donc le vrai coût de F8 dans ce profil est d'environ 3,5 + 16,5 = 20 s. C'est l'effet de sonde : il a disparu dès que F8 n'a plus été récursive (partie 5).

Les fonctions les plus coûteuses ont-elles les pires complexités ?

Rang	Fonction	Complexité	Opérations pour nos tailles	Temps propre (profil)
1	F1 trier_par_montant	O(n²)	n(n−1)/2 = 450 millions de comparaisons, avec échanges	9,30 s
2	F8 nb_facons_rendre	exponentielle (≈ S^k)	266,7 millions d'appels	3,50 s (+ ~16 s de sonde)
3	F10 ajouter_ligne → longueur	O(L) par ligne, O(L²) au total	341 millions de caractères reparcourus	3,43 s
4	F6 rechercher_par_id	O(n) par requête, O(Q × n)	≈ Q × n/2 = 450 millions de comparaisons	2,20 s
5	F7 nb_paires_opposees	O(n²)	450 millions d'additions	1,80 s
6	F5 meilleure_periode	O(J³)	J(J+1)(J+2)/6 = 167 millions d'additions	0,80 s
7	F2 nb_clients_distincts	O(n²) au pire	≈ n × C ici (le client est retrouvé tôt)	0,22 s
8	F3 total_par_client	O(n × C)	60 millions de tests	0,22 s
9	F4 total_par_jour	O(n × J)	30 millions de tests	0,10 s
10	F9 categorie	O(1) par transaction	30 000 appels	0,06 s

Oui, dans l'ensemble. Les cinq fonctions les plus coûteuses sont exactement celles dont la complexité est quadratique ou pire. Mais le degré de la complexité ne suffit pas à les classer, il faut aussi tenir compte des tailles réelles et du coût de chaque opération. On le voit sur deux cas :

• F5 a la pire complexité polynomiale (cubique), mais n'est que 6ᵉ. J = 1 000 est petit : J³/6 = 167 millions d'opérations, moins que les n²/2 = 450 millions de F1 ou F7.
• F1 et F7 font le même nombre de tours (450 millions), mais F1 est 5 fois plus lente. Chaque tour de F1 compare deux critères et échange des structures de 24 octets, alors que F7 fait une addition et un test. C'est la constante que la notation O ignore.

---

4. Complexités et complexité cyclomatique, avant / après

4.1 Complexité de F1 à F10

F	Fonction	Avant	Objectif	Après	Comment
F1	trier_par_montant	O(n²)	O(n log n)	O(n log n) ✔	qsort
F2	nb_clients_distincts	O(n²) au pire	O(n + C)	O(n + C) ✔	tableau vu[C]
F3	total_par_client	O(n × C)	O(n + C)	O(n + C) ✔	un seul parcours
F4	total_par_jour	O(n × J)	O(n + J)	O(n + J) ✔	un seul parcours
F5	meilleure_periode	O(J³)	O(J)	O(J) ✔	sommes préfixes
F6	rechercher_par_id	O(n) par requête	O(1) par requête	O(1) par requête ✔ (index construit une fois en O(n))	tableau position[id]
F7	nb_paires_opposees	O(n²)	O(n log n)	O(n log n) ✔	n dichotomies sur le tableau trié par F1
F8	nb_facons_rendre	exponentielle	O(S × k)	O(S × k) ✔	programmation dynamique
F9	categorie	O(1), M = 14	M ≤ 10	O(1), M ≤ 5 ✔	découpage en 5 fonctions
F10	ajouter_ligne	O(L) par ligne, O(L²) au total	O(L) au total	O(L) au total ✔	on passe la position de fin

4.2 Complexité cyclomatique M, calculée à la main

Nous avons compté M = décisions + 1, avec +1 pour chaque if, else if, for, while, &&, || et ternaire ?:. Comme le demande evaluer.sh, alea et generer_transactions ne comptent pas dans le maximum.

Avant

Fonction	Décisions	M
trier_par_montant (F1)	for, for, if, ||, &&	6
nb_clients_distincts (F2)	for, for, if, if	5
total_par_client (F3)	for, for, if	4
total_par_jour (F4)	for, for, if	4
meilleure_periode (F5)	for, for, for, if	5
rechercher_par_id (F6)	for, if	3
nb_paires_opposees (F7)	for, for, if	4
nb_facons_rendre (F8)	if, if, ||	4
categorie (F9)	if (< 0), if (< −20 000), if + || (week-end), else if (< −5 000), if (client), else if (== 0), if (> 30 000), if + &&, else if (> 10 000), else if (> 1 000), if (jour % 30) : 13	14
longueur (F10)	while	2
ajouter_ligne (F10)	while	2
empreinte	for	2
main	6 for, 2 if	9
alea, generer_transactions (exclues)	—, puis for, if, &&, for	1, 5

Maximum : M = 14 (categorie).

Après

Fonction	Décisions	M
comparer_transactions (F1)	if	2
trier_par_montant (F1)	—	1
nb_clients_distincts (F2)	for, if	3
total_par_client (F3)	for, for	3
total_par_jour (F4)	for, for	3
meilleure_periode (F5)	for, if, if	4
indexer_par_id (F6)	for	2
rechercher_par_id (F6)	—	1
premier_indice (F7)	while, if	3
effectif (F7)	—	1
nb_paires_opposees (F7)	for	2
nb_facons_rendre (F8)	for, for	3
est_week_end (F9)	—	1
categorie_debit (F9)	if, ?:, if, ?:	5
categorie_gros_credit (F9)	&&, ?:	3
categorie_credit (F9)	if, if, if, ?:	5
categorie (F9)	if, if	3
ajouter_ligne (F10)	while	2
empreinte	for	2
sommer_requetes	for	2
compter_categories	for	2
analyser	—	1
ajouter_formatee	—	1
construire_rapport	4 for	5
ecrire_fichier	if	2
afficher	—	1
main	—	1

Maximum : M = 5, atteint par categorie_debit, categorie_credit et construire_rapport.

On pourrait descendre plus bas avec des astuces comme return 2 - est_week_end(jour); à la place du ternaire, ou en coupant le rapport en morceaux. Nous ne l'avons pas fait : chaque fonction à M = 5 se lit d'un coup d'œil, et construire_rapport garde tout le format du rapport au même endroit.

---

5. Optimisations réalisées (un commit par optimisation)

L'ordre suit le profil : on traite d'abord la fonction la plus coûteuse. Seule exception, F7 utilise le tableau trié par F1 et vient donc après lui. Après chaque commit, nous avons vérifié l'empreinte, rapport.txt (identique octet par octet) et la sortie console.

F1 — cb7857c : qsort au lieu du tri à bulles

int comparer_transactions(const void *pa, const void *pb)
{
    const Transaction *a = pa, *b = pb;
    if (a->montant != b->montant)
        return (a->montant > b->montant) - (a->montant < b->montant);
    return (a->id > b->id) - (a->id < b->id);
}

Pourquoi c'est correct : les id sont tous distincts, donc l'ordre (montant, puis id) est total. qsort n'est pas stable, mais il donne exactement le même classement que le tri à bulles. L'écriture (a > b) - (a < b) évite tout débordement, contrairement à une soustraction.

O(n²) → O(n log n). Temps : 3,05 s → 1,17 s.

F8 — d19085e : programmation dynamique

long *facons = calloc(somme + 1, sizeof(long));
facons[0] = 1;
for (int p = 0; p < nb_pieces; p++)
    for (int s = PIECES[p]; s <= somme; s++)
        facons[s] += facons[s - PIECES[p]];

Pourquoi c'est plus rapide : la récursion recalculait sans cesse les mêmes couples (somme, pièces) : 266,7 millions d'appels. Après avoir traité les p premières pièces, facons[s] est le nombre de façons de rendre s avec ces pièces. On compte des combinaisons, sans tenir compte de l'ordre des pièces, comme la récursion d'origine. On fait ainsi 2 820 additions au lieu de 266 millions d'appels.

Exponentielle → O(S × k). Temps : 1,17 s → 1,00 s. En -O2, la récursion ne coûtait donc qu'environ 0,2 s, un écart proche du bruit de mesure. Dans le profil, en revanche, les 16 s de _mcount_private disparaissent.

F10 — 4babca1 : rapport en O(L)

char *ajouter_ligne(char *fin, const char *ligne)
{
    while (*ligne != '\0')
        *fin++ = *ligne++;
    *fin = '\0';
    return fin;
}

Pourquoi c'est plus rapide : longueur(rapport) reparcourait tout le rapport à chaque ligne, soit 341 millions de caractères pour 6 017 lignes. On passe maintenant la position du '\0' final et on renvoie la nouvelle. Chaque caractère n'est écrit qu'une fois. longueur n'est plus utilisée et disparaît.

O(L²) → O(L). Temps : 0,90 s → 0,72 s, mesuré par 11 exécutions alternées des deux versions. La mesure habituelle de 5 exécutions (1,00 → 1,08 s) était noyée dans le bruit. En -O2, gcc intègre longueur dans ajouter_ligne, mais la boucle reste octet par octet (nous l'avons vérifié dans l'assembleur) : le coût quadratique était donc bien réel.

F6 — d913c22 : index par id

int *indexer_par_id(const Transaction *t, int n)
{
    int *position = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        position[t[i].id] = i;
    return position;
}

Pourquoi c'est correct : generer_transactions attribue les id 0 à n−1, puis les mélange. Les id forment donc une permutation et chaque id a sa case. rechercher_par_id devient return &t[position[id]];. Le test r != NULL de main ne pouvait plus jamais être vrai et a été retiré. L'index est construit avant le tri de F1, car les requêtes portent sur l'ordre d'origine.

O(n) → O(1) par requête (index en O(n) une seule fois). Temps : 1,08 s → 0,92 s.

F7 — c84ff59 : paires opposées par dichotomie

long nb_paires_opposees(const Transaction *t, int n)   /* t trié par F1 */
{
    long nb = 0;
    for (int i = 0; i < n; i++)
        nb += effectif(t, n, -t[i].montant);
    return (nb - effectif(t, n, 0)) / 2;
}

effectif(t, n, v) vaut premier_indice(v + 1) − premier_indice(v), où premier_indice est une recherche dichotomique en O(log n).

Pourquoi c'est correct : la somme compte, pour chaque transaction, les transactions de montant opposé. Chaque paire {a, b} est donc comptée deux fois (une fois depuis a, une fois depuis b), et une transaction de montant 0 se compte aussi elle-même. On retire ces auto-comptages, puis on divise par 2. Le résultat reste bien 5 832 paires. F7 réutilise le tri de F1 et est donc appelée après lui dans main.

O(n²) → O(n log n) (n recherches en O(log n), le tri étant déjà fait pour F1). Temps : 0,92 s → 0,25 s.

F5 — 9227039 : sommes préfixes, un seul parcours

for (int j = 0; j < nb_jours; j++) {
    if (prefixe < prefixe_min) {   /* prefixe vaut ici prefixe(j) */
        prefixe_min = prefixe;
        debut_min = j;
    }
    prefixe += totaux[j];          /* prefixe vaut maintenant prefixe(j+1) */
    if (prefixe - prefixe_min > meilleur) {
        meilleur = prefixe - prefixe_min;
        *debut = debut_min;
        *fin = j;
    }
}

Pourquoi c'est correct : la somme des jours i à j vaut prefixe(j+1) − prefixe(i). Pour une fin j fixée, le meilleur début est donc l'indice du plus petit préfixe avant j. L'original gardait la première période maximale dans l'ordre (i, puis j). Pour la retrouver, on garde le premier minimum (< strict) et on ne remplace le meilleur que s'il est strictement dépassé. On peut montrer que cela donne le même couple (début, fin), même en cas d'égalité. Nous l'avons vérifié sur 200 000 tableaux aléatoires remplis d'égalités, en comparant à la triple boucle d'origine.

O(J³) → O(J). Temps : 0,25 s → 0,097 s.

F3 — b402946 et F4 — 6c8b915 : un seul parcours

for (int c = 0; c < NB_CLIENTS; c++)
    totaux[c] = 0;
for (int i = 0; i < n; i++)
    totaux[t[i].client] += t[i].montant;

Au lieu de reparcourir les n transactions pour chaque client (ou chaque jour), chaque montant va directement dans la bonne case. Les montants d'un même client sont additionnés dans le même ordre, et ce sont des entiers, donc les totaux sont identiques. F4 est identique avec jour.

F3 : O(n × C) → O(n + C), 0,097 s → 0,087 s. F4 : O(n × J) → O(n + J), 0,087 s → 0,073 s.

F2 — 3bf75a2 : tableau de présence

char vu[NB_CLIENTS] = {0};
for (int i = 0; i < n; i++)
    if (!vu[t[i].client]) {
        vu[t[i].client] = 1;
        nb++;
    }

O(n²) au pire → O(n + C). Temps : 0,073 s → 0,069 s, au niveau du bruit. Dans le profil -O0, la fonction passe de 0,32 s à 0.

F9 — 60fd5e5 : categorie découpée (M = 14 → 5)

int categorie(const Transaction *t)
{
    if (t->montant < 0)
        return categorie_debit(t);
    if (t->montant == 0)
        return 0;
    return categorie_credit(t);
}

categorie_debit et categorie_credit (M = 5), categorie_gros_credit (M = 3) et le prédicat est_week_end (jour % 7 >= 5, équivalent à == 5 || == 6 puisque jour ≥ 0) remplacent les if imbriqués.

Pourquoi c'est correct : nous avons comparé l'ancienne et la nouvelle fonction sur tout le domaine. Le montant va de −50 000 à 50 000. Pour le jour, seuls jour % 7 et jour % 30 comptent, donc 210 valeurs suffisent (ppcm(7, 30) = 210). Pour le client, seul client % 10 compte. Les 210 002 100 combinaisons donnent la même catégorie.

Complexité inchangée (O(1)), M maximal 14 → 5.

main — 9ee6245 : fonctions courtes (M = 8 → 1)

Après F9, main (6 boucles et 1 test) avait le plus grand M du fichier. Les calculs passent dans analyser, qui remplit une structure Resultats. Le rapport est construit par construire_rapport, à l'aide de ajouter_formatee (un vsnprintf suivi d'un ajouter_ligne). ecrire_fichier et afficher terminent. Temps : 0,068 s → 0,061 s, rapport identique octet par octet.

Évolution du temps

Étape	Commit	Temps -O2 (médiane de 5)	Durée profilée (-O0 -pg)
Version d'origine	—	3,05 s	38,10 s
F1 qsort	cb7857c	1,17 s	30,17 s
F8 programmation dynamique	d19085e	1,00 s	9,12 s
F10 rapport en O(L)	4babca1	1,08 s*	6,34 s
F6 index par id	d913c22	0,92 s	4,62 s
F7 dichotomie	c84ff59	0,25 s	1,90 s
F5 sommes préfixes	9227039	0,097 s	0,62 s
F3 un seul parcours	b402946	0,087 s	0,48 s
F4 un seul parcours	6c8b915	0,073 s	0,38 s
F2 tableau de présence	3bf75a2	0,069 s	0,03 s
F9 découpage (M)	60fd5e5	0,068 s	0,04 s
main découpée (M)	9ee6245	0,061 s	0,05 s

* Bruit de mesure. Avec 11 exécutions alternées des deux versions, F10 fait passer de 0,90 s à 0,72 s.

---

6. Validation (profil_apres.txt)

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 40.00      0.02     0.02                             __fentry__
 40.00      0.04     0.02                             _mcount_private
 20.00      0.05     0.01   149998     0.00     0.00  alea
  0.00      0.05     0.00    60002     0.00     0.00  premier_indice
  0.00      0.05     0.00    30001     0.00     0.00  effectif
  0.00      0.05     0.00    30000     0.00     0.00  categorie
  0.00      0.05     0.00    30000     0.00     0.00  rechercher_par_id

• Il ne reste plus que 5 échantillons (0,05 s). Le seul qui tombe dans le programme lui-même est dans alea, c'est-à-dire la génération des données, qu'on n'a pas le droit de modifier.
• Les nombres d'appels correspondent aux nouvelles complexités. premier_indice est appelée 60 002 fois : 2 fois par transaction pour F7, plus 2 pour les montants nuls. rechercher_par_id est appelée 30 000 fois, une par requête, mais chaque appel est en O(1).
• comparer_transactions n'a aucun nombre d'appels : elle est appelée par qsort, qui est dans la bibliothèque C et n'est pas instrumentée. C'est la limite de gprof vue en cours (« gprof ne voit pas la libc »).

Ce qui reste à gagner : nous avons mesuré le plancher (médiane de 11 exécutions) :

Programme	Temps
int main(void) { return 0; } (démarrage d'un processus)	32 ms
Génération des transactions seule (non modifiable)	41 ms
Version finale complète	45 ms

Nos dix fonctions ne coûtent plus qu'environ 4 ms sur 45. Une optimisation supplémentaire, par exemple un tri par dénombrement ou un parcours à deux indices pour F7, ne serait pas mesurable face au bruit. Nous nous sommes donc arrêtés là.

---

7. Concours

Critère	Résultat
Complexité algorithmique	les 10 objectifs sont atteints (partie 4.1)
Complexité cyclomatique maximale	M = 5, calculée à la main (partie 4.2). Lizard n'est pas installé, donc evaluer.sh affiche « - ».
Temps (./evaluer.sh banque.c MEHIRI_PLOUVIER_COLOMB-RAVAT)	124 ms, empreinte correcte. Les deux autres essais ont donné 142 et 124 ms.

La ligne MEHIRI_PLOUVIER_COLOMB-RAVAT;-;124 a été ajoutée à resultats.csv. Ce temps a été mesuré sur notre portable sous Windows. Chaque exécution y paie environ 30 ms de démarrage de processus, et evaluer.sh lance aussi date deux fois par mesure. Il n'est donc pas comparable à une mesure sur la machine de l'enseignant.

---

8. Bilan

• « Le bon algorithme bat la machine » : de 3,05 s à 0,061 s (×50), sans changer la machine ni les options de compilation, uniquement en changeant les algorithmes.
• « La théorie prédit, la mesure confirme » : les fonctions quadratiques ou pires étaient bien les plus coûteuses. Mais leur ordre dépendait des tailles réelles (F5 cubique, mais J petit) et des constantes (F1 cinq fois plus lente que F7 pour le même nombre de tours).
• Coût des optimisations : l'index de F6 occupe 120 Ko (30 000 entiers). F7 suppose le tableau trié par F1, ce qui est indiqué en commentaire et dans main. F8 alloue S + 1 entiers. Pour la complexité cyclomatique, le fichier a plus de fonctions (27 au lieu de 13), mais chacune est courte, avec M ≤ 5 au lieu de 14 au maximum.
• Limites de gprof rencontrées : l'effet de sonde (16 s de _mcount dues aux 267 millions d'appels récursifs de F8) et qsort, qui reste invisible.