forked from menault/2026_TD3_DEV51_Qualite_Algo
rabot
21 lines
1.2 KiB
Markdown
21 lines
1.2 KiB
Markdown
# Complexités avant et après l'étape 4
|
||
|
||
| ID | Fonction | Avant | Après (objectif atteint) | M avant → après |
|
||
|:---:|---|---|---|:---:|
|
||
| F1 | `trier_par_montant` | `O(n²)` | `O(n log n)` au pire cas | 6 → 3 |
|
||
| F2 | `nb_clients_distincts` | `O(n²)` | `O(n + C)` | 5 → 3 |
|
||
| F3 | `total_par_client` | `O(n × C)` | `O(n + C)` | 4 → 3 |
|
||
| F4 | `total_par_jour` | `O(n × J)` | `O(n + J)` | 4 → 3 |
|
||
| F5 | `meilleure_periode` | `O(J³)` | `O(J)` | 5 → 4 |
|
||
| F6 | `rechercher_par_id` | `O(n)` par requête | `O(1)` par requête, après indexation `O(n)` | 3 → 3 |
|
||
| F7 | `nb_paires_opposees` | `O(n²)` | `O(n log n)` | 4 → 3 |
|
||
| F8 | `nb_facons_rendre` | `O(2^(S + k))`, borne générale | `O(S × k)` pour `k ≥ 1` | 4 → 5 |
|
||
| F9 | `categorie` | `O(1)`, M = 14 | `O(1)`, M = 3 (auxiliaires : 5 et 7) | 14 → 3 |
|
||
| F10 | `ajouter_ligne` | `O(L²)` au total, lignes de taille bornée | `O(L)` au total | 2 → 2 |
|
||
|
||
`n` transactions · `C` clients · `J` jours · `S` somme · `k` pièces · `L` longueur du rapport.
|
||
|
||
Justifications, mémoire auxiliaire, M des fonctions auxiliaires et validations
|
||
dans `COMPTE_RENDU.md`, section 4. Les constantes et le format du rapport
|
||
sont inchangés ; l'empreinte reste `ff68d260a7a58441` à chaque optimisation.
|