forked from menault/2026_TD3_DEV51_Qualite_Algo
rabot
1.2 KiB
1.2 KiB
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.