📌 L’analyse empirique mesure notamment les temps de calcul et l’usage moyen de la mémoire, tandis que l’analyse théorique étudie la complexité en instructions et en mémoire.
📌 La complexité au pire cas mesure le maximum de ressources utilisées, la complexité moyenne leur valeur moyenne et la complexité au meilleur cas leur minimum.
Empirique : mesurer l’exécution ; théorique : compter les ressources.
★ À maîtriser
Les complexités asymptotiques expriment l’ordre de grandeur des ressources en fonction de la taille des entrées, souvent avec la notation grand O.
Les classes de complexité présentées sont :
Compléments
📌 Pour simplifier une expression en grand O, on supprime les constantes multiplicatives et on ne conserve que le terme dominant pour chaque variable d’entrée, par exemple O(1+n+n²)=O(n²).
📌 La somme de deux complexités en grand O se simplifie en conservant la plus dominante, soit O(x)+O(y)=max(O(x),O(y)), tandis que leur produit devient O(x·y).
★ À maîtriser
Compléments
📌 La complexité d’un problème est celle du meilleur algorithme pour ce problème, et l’optimalité peut être montrée en donnant une entrée qui atteint le pire coût.
★ À maîtriser
La factorielle récursive vérifie C(n)=O(1)+C(n−1) avec C(0)=O(1), ce qui donne n coûts constants successifs et une complexité O(n).
La version récursive de Fibonacci vérifie C(n)=C(n−1)+C(n−2)+O(1), avec C(0)=O(1) et C(1)=O(1).
Compléments
★ À maîtriser
Compléments
Le cours indique une complexité O(n) pour un calcul de Fibonacci abrégé, puis mentionne qu’une version peut être améliorée jusqu’à O(log n).
La recherche dichotomique compare l’élément recherché à l’élément médian d’un tableau trié, puis poursuit la recherche dans une moitié du tableau.
Fibonacci récursif → Fibonacci en O(n) → Fibonacci en O(log n).
Teste tes connaissances sur Complexité des algorithmes avec 9 questions à choix multiples et corrections détaillées.
1. Une équipe chronomètre un programme sur des données réelles et relève sa consommation moyenne de mémoire, puis étudie théoriquement son nombre d’instructions et ses besoins en mémoire. Quelle distinction décrit ces deux démarches ?
2. Pour un algorithme donné, une équipe compare les ressources consommées sur différentes entrées. Quel cas correspond à la valeur moyenne des ressources utilisées ?
Mémorisez les concepts clés de Complexité des algorithmes avec 10 flashcards interactives.
Que mesure notamment l’analyse empirique des performances algorithmiques ?
Les temps de calcul et l’usage moyen de la mémoire.
Que mesure la complexité au pire cas d’un algorithme ?
Le maximum de ressources utilisées.
Que mesure la complexité asymptotique en fonction de la taille des entrées ?
L’ordre de grandeur des ressources utilisées.
Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.
Générateur de fiches