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.
Quelles sont les classes de complexité présentées, de constante à exponentielle ?
et .
Comment calculer la complexité au pire cas d’un algorithme ?
On additionne les coûts des lignes, multiplie celui des boucles par leurs répétitions maximales, retient le coût maximal des branches et exprime le résultat en grand O.
Quelle complexité obtient-on pour la factorielle récursive avec C(n)=O(1)+C(n−1) et C(0)=O(1) ?
O(n).
Quelle est la complexité temporelle de la factorielle itérative ?
.
Comment définir la complexité d’un problème et montrer l’optimalité d’un algorithme ?
C’est celle du meilleur algorithme ; une entrée atteignant son pire coût peut prouver son optimalité.
Que doit intégrer le calcul du pire cas pour une récursion arrêtée par une branche conditionnelle ?
Le coût de l’arrêt.
Quelle est la complexité du calcul de l’écart type pour n nombres ?
.
Teste tes connaissances avec un QCM de 9 questions sur Complexité des algorithmes.
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 ?
Révisez le cours complet dans la fiche de révision de Complexité des algorithmes.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards