Présentation infographique

PRESENTAtIoN

Algorithme

Bruteforce

Analyse de données et complexité d'algorithme

29

Index

3. Comparaison des performances (force brute vs. optimisée)

1. Analyse de l'algorithme de BRUTE FORCE

2. organigramme ET pseudocode

4. Comparaison des résultats

1.

Analyse de l'algorithme de BRUTEFORCE

Traitement

Sortie

Entrée

Meilleurs investissements

Boucle qui passe par toutes les combinaisons possibles

Liste d'actions

name, cost, profit

Calcule le coût total et le profit pour chaque combinaison

Traitement long

Budget

60 459 énumérations

Compléxité exponentielle (O(n6))

1.

Analyse de l'algorithme de BRUTEFORCE optimisé

Traitement

Sortie

Entrée

Meilleurs investissements

Programmation dynamique avec une matrice

Liste d'actions

name, cost, profit

Traitement plus rapide

stocke en sous-problèmes et décide (ou non) de traiter une solution

Budget

10020 énumérations

Compléxité temporelle O(nW)

Solution dynamique

2. Organigramme

Dépend du nombre d'actions et du budget.

Profit = cout * beneficePOUR chaque budget (w): SI cout < budget = on ajoute l'action comme un investissement important dans la matriceSINON : On garde l'ancienne action

Boucle sur chaque action (n)

Matrice (boîte) : dp[n][W]

Stockage de la meilleure action

n = nombre d'actionsw = budget

SI encore du budget on continue d'itérer sur la boucle en cours.

3. programmation dynamique

Bruteforce vs optimisé

Bruteforce

Optimisé

Trés lent

5X plus efficace

• Complexité à croissance linéaire en fonction du nombre d'actions et du budget
• Réduit significativement le temps d'éxécution en excluant les calculs inutiles
• Une matrice utilise moins de mémoire pour stocker les profits

• Doit gérer toutes les combinaisons possibles
• Beaucoup d'itérations et de calculs
• Ne gère pas de très grand ensembles de données

vs

4.Comparaison des résultats

Premier tableau

Sienna :1 actionCoût total: 498.76€ Bénéfice: 196.61€

Moi :22 actionsCoût total: 499.96€Bénéfice: 397.09€

4.Comparaison des résultats

Deuxième tableau

Sienna :18 actionsCoût total: 489.24€ Bénéfice: 193.78€

Moi :22 actionsCoût total: 499.92€Bénéfice: 395.93€

On peut noter que l'algorithme optimisé permet de diversifier les sources d'investissements et de placer le maximum d'argent possible en maximisant les profits.

Merci