forked from menault/2026_TD3_DEV51_Qualite_Algo
69 lines
3.3 KiB
Markdown
69 lines
3.3 KiB
Markdown
# Compte rendu — TD3 Complexité algorithmique (R5.A.04)
|
|
|
|
## 1. Complexités algorithmiques
|
|
|
|
| Fonction | Rôle | Avant | Après |
|
|
|---|---|---|---|
|
|
| F1 | `trier_par_montant` — tri par montant puis par id | O(n²) | **O(n log n)** (tri fusion) |
|
|
| F2 | `nb_clients_distincts` | O(n²) | **O(n + c)** (tableau de présence) |
|
|
| F3 | `total_par_client` | O(n·c) | |
|
|
| F4 | `total_par_jour` | O(n·J) | |
|
|
| F5 | `meilleure_periode` | O(J³) | |
|
|
| F6 | `rechercher_par_id` | O(n) | |
|
|
| F7 | `nb_paires_opposees` | O(n²) | |
|
|
| F8 | `nb_facons_rendre` | O(2^S) | |
|
|
| F9 | `categorie` | M = 14 | |
|
|
| F10 | `ajouter_ligne` | O(L) | |
|
|
|
|
## 2. Profil gprof initial
|
|
|
|
Programme d'origine compilé avec `gcc -O0 -g -pg`, temps total mesuré : **6,83 s**.
|
|
|
|
|
|
|
|
`trier_par_montant` représente à elle seule **48 %** du temps (3,28 s) : c'est la première fonction à optimiser.
|
|
|
|
## 3. Optimisations
|
|
|
|
### 3.1 F1 — `trier_par_montant` : tri à bulles → tri fusion
|
|
|
|
**Avant :** tri à bulles, deux boucles imbriquées qui comparent et échangent les éléments voisins → O(n²).
|
|
|
|
**Après :** tri fusion itératif (ascendant). On fusionne des sous-tableaux triés de taille 1, 2, 4, 8… jusqu'à couvrir tout le tableau. La fonction `fusionner` copie les deux moitiés dans des tableaux temporaires puis les recombine dans l'ordre → O(n log n).
|
|
|
|
L'ordre de tri est conservé (montant croissant, puis id croissant en cas d'égalité), donc l'empreinte reste `ff68d260a7a58441`.
|
|
|
|
**Profil gprof après modification :**
|
|
|
|
|
|
|
|
| | Avant | Après |
|
|
|---|---|---|
|
|
| Temps de `trier_par_montant` | 3,28 s | 0,01 s (via `fusionner`) |
|
|
| Temps total du programme | 6,83 s | 3,06 s |
|
|
|
|
Le tri passe de 48 % du temps à un coût négligeable ; le temps total est divisé par plus de 2. Les fonctions les plus coûteuses sont maintenant `nb_facons_rendre` (30 %), `nb_paires_opposees` (24 %) et `rechercher_par_id` (22 %).
|
|
|
|
### 3.2 F2 — `nb_clients_distincts` : double boucle → tableau de présence
|
|
|
|
**Avant :** pour chaque transaction, on reparcourt toutes les transactions précédentes pour savoir si le client a déjà été vu → O(n²).
|
|
|
|
**Après :** l'id du client sert directement d'index dans un tableau de booléens `presence` :
|
|
1. un premier parcours trouve l'id client maximal pour dimensionner le tableau ;
|
|
2. le tableau est alloué avec `calloc` (initialisé à `false`) ;
|
|
3. un second parcours marque chaque client rencontré et incrémente le compteur la première fois qu'il est vu ;
|
|
4. le tableau est libéré avec `free`.
|
|
|
|
Chaque vérification « déjà vu ? » se fait en O(1), d'où une complexité O(n + c) (c = nombre de clients). Le résultat est identique, l'empreinte est inchangée.
|
|
|
|
**Profil gprof après modification :**
|
|
|
|
|
|
|
|
| | Avant | Après |
|
|
|---|---|---|
|
|
| Temps de `nb_clients_distincts` | 0,11 s | 0,00 s |
|
|
| Temps total du programme | 3,06 s | 3,07 s |
|
|
|
|
La fonction devient négligeable dans le profil. Le gain sur le temps total n'est pas visible car il est inférieur aux variations de mesure de gprof (échantillonnage à 0,01 s). Les fonctions les plus coûteuses restent `nb_facons_rendre` (28 %), `nb_paires_opposees` (26 %) et `rechercher_par_id` (25 %).
|