2026_TD3_DEV51_Qualite_Algo/COMPTE_RENDU.md

# Compte rendu — TD 3 : complexité algorithmique
Nathan COUCHOT et Lucas POT

## 1. Mesurer le programme

```bash
gcc -O2 banque.c -o banque
time ./banque
```

La version initiale s'exécute en environ **2,26 s**.

| Mesure initiale | Résultat |
| --- | ---: |
| Temps réel (`real`) | 2,26 s |
| Temps CPU utilisateur (`user`) | 2,23 s |
| Temps CPU système (`sys`) | 0,00 s |
| Empreinte | `ff68d260a7a58441` |

L'empreinte attendue est **`ff68d260a7a58441`**.

## 2. Profiler et analyser le programme initial

```bash
gcc -O0 -g -pg banque.c -o banque_pg
./banque_pg
gprof ./banque_pg gmon.out > profil_avant.txt
```

Le temps réel mesuré avec l'instrumentation est **8,35 s**, contre **2,26 s** sans `-pg`. Cette différence vient en partie du coût ajouté par le comptage des appels. Le profil complet est fourni dans profil_avant.txt.

| Fonction | Part du temps propre | Temps propre | Appels |
| --- | ---: | ---: | ---: |
| `trier_par_montant` | 49,43 % | 3,02 s | 1 |
| `rechercher_par_id` | 13,42 % | 0,82 s | 30 000 |
| `nb_paires_opposees` | 11,95 % | 0,73 s | 1 |
| `nb_facons_rendre` | 8,27 % | 0,51 s | 1 appel depuis `main` |
| `longueur` | 6,87 % | 0,42 s | 6 017 |
| `meilleure_periode` | 4,91 % | 0,30 s | 1 |
| `total_par_client` | 1,80 % | 0,11 s | 1 |
| `nb_clients_distincts` | 1,64 % | 0,10 s | 1 |
| `total_par_jour` | 0,82 % | 0,05 s | 1 |

Le tri à bulles est le principal point chaud du profil. `rechercher_par_id` est appelée 30 000 fois et parcourt le tableau à chaque recherche. `ajouter_ligne` appelle `longueur` pour retrouver la fin du rapport ; comme le rapport grandit à chaque ajout, ces recherches répétées reparcourent une quantité croissante de caractères.

Le graphe d'appels permet aussi de voir le coût récursif de `nb_facons_rendre`. Le profil plat ne montre qu'un appel depuis `main`, mais cet appel entraîne de nombreux appels récursifs. Le temps propre observé ne suffit donc pas à lui seul pour expliquer le coût total.

Les fonctions les plus coûteuses n'ont pas nécessairement les complexités les plus élevées. Le tri traite 30 000 transactions, tandis que `meilleure_periode` traite 1 000 jours. Le temps mesuré dépend à la fois de la complexité et de la taille effective des données.

## 3. Complexités algorithmiques et cyclomatiques

On note **n** le nombre de transactions, **C** le nombre de clients, **J** le nombre de jours, **Q** le nombre de requêtes, **S** la somme à rendre, **k** le nombre de pièces et **L** la longueur finale du rapport. Les paramètres sont considérés variables pour l'analyse, même si le programme utilise des constantes.

| Fonction | Calcule | Actuelle | Objectif |
| --- | --- | --- | --- |
| F1 `trier_par_montant` | tri des transactions | O(n²) | O(n log n) |
| F2 `nb_clients_distincts` | clients différents | O(n²) | O(n + C) |
| F3 `total_par_client` | solde par client | O(n * c) | O(n + C) |
| F4 `total_par_jour` | solde par jour | O(n * J) | O(n + J) |
| F5 `meilleure_periode` | période la plus rentable | O(J³) | O(J) |
| F6 `rechercher_par_id` | recherche par identifiant | O(n) | O(1) par requête |
| F7 `nb_paires_opposees` | paires a + b = 0 | O(n²) | O(n log n) |
| F8 `nb_facons_rendre` | rendu de monnaie | O(S^n) | O(S × k) |
| F9 `categorie` | catégorie d'une transaction | M = 14 | M ≤ 10 |
| F10 `ajouter_ligne` | construction du rapport | O(n) | O(L) au total |

### Complexité cyclomatique des fonctions F1 à F10

On calcule **M = nombre de décisions + 1**.

| Fonction | Décisions | Calcul de M |
| --- | --- | ---: |
| F1 `trier_par_montant` | 2 `for` + 1 `if` + 1 `||` + 1 `&&` | 5 + 1 = **6** |
| F2 `nb_clients_distincts` | 2 `for` + 2 `if` | 4 + 1 = **5** |
| F3 `total_par_client` | 2 `for` + 1 `if` | 3 + 1 = **4** |
| F4 `total_par_jour` | 2 `for` + 1 `if` | 3 + 1 = **4** |
| F5 `meilleure_periode` | 3 `for` + 1 `if` | 4 + 1 = **5** |
| F6 `rechercher_par_id` | 1 `for` + 1 `if` | 2 + 1 = **3** |
| F7 `nb_paires_opposees` | 2 `for` + 1 `if` | 3 + 1 = **4** |
| F8 `nb_facons_rendre` | 2 `if` + 1 `||` | 3 + 1 = **4** |
| F9 `categorie` | 11 `if`/`else if` + 1 `||` + 1 `&&` | 13 + 1 = **14** |
| F10 `ajouter_ligne` | 1 `while` | 1 + 1 = **2** |

## 4. Optimiser et vérifier F1

Le tri à bulles de `trier_par_montant` effectue O(n²) comparaisons. Il est remplacé par `qsort`, avec un comparateur qui ordonne d'abord les transactions par montant croissant, puis par identifiant croissant en cas d'égalité. Les comparaisons relationnelles évitent le risque de débordement qu'introduirait une soustraction des montants ou des identifiants. Sur la bibliothèque utilisée, le tri a un coût O(n log n), conformément à l'objectif du TD.

| Mesure | Avant : tri à bulles | Après : `qsort` |
| --- | ---: | ---: |
| Temps réel médian | 2,36 s | 0,97 s |
| Temps utilisateur médian | 2,35 s | 0,97 s |
| Temps système médian | 0,00 s | 0,00 s |
| Empreinte | `ff68d260a7a58441` | `ff68d260a7a58441` |

Sur ces mesures, le temps réel médian baisse d'environ **59 %** (la version optimisée est environ **2,4 fois plus rapide**). Les valeurs affichées par le programme restent identiques et l'empreinte confirme que le rapport n'a pas changé. 

## 4. Optimiser F6 : rechercher une transaction par identifiant

La recherche initiale parcourait le tableau jusqu'à trouver l'identifiant demandé, soit O(n) par requête et O(Qn) pour Q requêtes. Or les identifiants générés forment une permutation de 0 à n−1. Le programme construit donc une fois un tableau d'index où `index[id]` pointe vers la transaction correspondante. Chaque recherche vérifie que l'identifiant est dans les limites, puis renvoie directement `index[id]` en O(1). La construction coûte O(n), les Q recherches coûtent O(Q), soit O(n + Q) au total. L'index est libéré après les requêtes, avant le tri qui déplace les transactions.

| Mesure | Avant : recherche linéaire | Après : index |
| --- | ---: | ---: |
| Temps réel médian | 0,97 s | 0,80 s |
| Temps utilisateur médian | 0,97 s | 0,80 s |
| Temps système médian | 0,00 s | 0,00 s |
| Empreinte | `ff68d260a7a58441` | `ff68d260a7a58441` |

Le temps réel médian baisse d'environ **18 %** (environ **1,2 fois plus rapide**). L'empreinte identique confirme que les recherches renvoient les mêmes transactions et que le rapport conserve son contenu.