forked from menault/2026_TD3_DEV51_Qualite_Algo
SOLAR D
78 lines
2.9 KiB
Markdown
78 lines
2.9 KiB
Markdown
# Dimitri SOLAR / Valentin LOISON / Kais BENS
|
|
|
|
Empreinte : ff68d260a7a58441
|
|
|
|
real 2.11s
|
|
user 2.11s
|
|
sys 0.00s
|
|
|
|
|
|
|
|
2. # Profiller
|
|
la fonction la plus couteuse est : trier_par_montant pourtant elle n'a pas la complexité la plys élévé .
|
|
|
|
3.
|
|
F1 = O(n^2)
|
|
F2 = O(n^2)
|
|
F3 = O(n*c)
|
|
F4 = O(n*j)
|
|
F5 = O(j^2)
|
|
F6 = O(n^2)
|
|
F7 = O(n^2)
|
|
F8 O(2^k)
|
|
F9 M=14
|
|
F10 = O(n+L)
|
|
|
|
|
|
|
|
```console
|
|
└─$ ./evaluer.sh banque.c solar
|
|
Empreinte correcte
|
|
Temps (médiane de 5) : 13 ms
|
|
Complexité cyclomatique : vérifiée par l'enseignant
|
|
Ligne ajoutée à resultats.csv : solar;-;13
|
|
|
|
```
|
|
|
|
|
|
4. # Justification
|
|
|
|
F1 (trier_par_montant)
|
|
Remplacement du tri à bulles en O(n^2) par le tri rapide standard qsort en O(n log n).
|
|
La fonction de comparaison dédiée traite la clé composite (montant puis identifiant) efficacement.
|
|
|
|
F2 (nb_clients_distincts)
|
|
Remplacement de la double boucle imbriquée en O(n^2)par un tableau de présence (deja_vu).
|
|
Le calcul s'effectue désormais en un seul parcours linéaire O(n) grâce à des accès directs en O(1).
|
|
|
|
F3 (total_par_client)
|
|
Suppression de la double boucle en O(clients * n) qui re-parcourait inutilement le tableau pour chaque client.
|
|
Accumulation directe des montants sur chaque client au fil d'une passe unique en O(clients + n).
|
|
|
|
F4 (total_par_jour)
|
|
Élimination du parcours complet de toutes les transactions pour chaque jour distinct en O(jours * n).
|
|
Parcours unique des transactions avec ajout immédiat au jour correspondant, réduisant le temps à O(jours + n).
|
|
|
|
F5 (meilleure_periode)
|
|
Remplacement du calcul exhaustif de toutes les plages de jours consécutifs en O(n^3).
|
|
Application de l'algorithme de Kadane pour trouver la somme maximale en une seule passe linéaire O(n).
|
|
|
|
F6 (rechercher_par_id)
|
|
Remplacement de la recherche linéaire globale répétée en O(n) à la requête.
|
|
Mise en place d'une table d'indexation directe (cache statique) offrant un accès immédiat en O(1) par requête.
|
|
|
|
F7 (nb_paires_opposees)
|
|
Passage d'une comparaison de toutes les paires possibles en O(n^2) à un tri préalable des montants en O(n log n).
|
|
Utilisation de deux pointeurs convergents pour dénombrer les paires opposées en un parcours linéaire.
|
|
|
|
F8 (nb_facons_rendre)
|
|
Remplacement de l'exploration récursive naïve souffrant d'une complexité temporelle exponentielle.
|
|
Adoption de la programmation dynamique via un tableau 1D en O(somme * nb_pieces).
|
|
|
|
F9 (categorie)
|
|
Structuration et modularisation des tests conditionnels via categorie_debit et categorie_credit.
|
|
Simplification de l'arbre de décision permettant de réduire les comparaisons et d'aider la prédiction de branchement.
|
|
|
|
F10 (ajouter_ligne)
|
|
Suppression du recalcul de la longueur totale du rapport à chaque insertion, évite un coût global en O(n^2).
|
|
Maintien d'un pointeur mobile fin_rapport garantissant une écriture directe à la suite en O(longueur_ligne). |