Flashcards : Complexité des algorithmes (10 cartes)

Toutes les cartes

1Question

Que mesure notamment l’analyse empirique des performances algorithmiques ?

Réponse

Les temps de calcul et l’usage moyen de la mémoire.

2Question

Que mesure la complexité au pire cas d’un algorithme ?

Réponse

Le maximum de ressources utilisées.

3Question

Que mesure la complexité asymptotique en fonction de la taille des entrées ?

Réponse

L’ordre de grandeur des ressources utilisées.

4Question

Quelles sont les classes de complexité présentées, de constante à exponentielle ?

Réponse

O(1),O(log⁡(n)),O(n),O(n2),O(nk)O(1), O(\log(n)), O(n), O(n^2), O(n^k) et O(kn)O(k^n).

5Question

Comment calculer la complexité au pire cas d’un algorithme ?

Réponse

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.

6Question

Quelle complexité obtient-on pour la factorielle récursive avec C(n)=O(1)+C(n−1) et C(0)=O(1) ?

Réponse

O(n).

7Question

Quelle est la complexité temporelle de la factorielle itérative ?

Réponse

O(n)O(n).

8Question

Comment définir la complexité d’un problème et montrer l’optimalité d’un algorithme ?

Réponse

C’est celle du meilleur algorithme ; une entrée atteignant son pire coût peut prouver son optimalité.

9Question

Que doit intégrer le calcul du pire cas pour une récursion arrêtée par une branche conditionnelle ?

Réponse

Le coût de l’arrêt.

10Question

Quelle est la complexité du calcul de l’écart type pour n nombres ?

Réponse

O(n)O(n).

Teste-toi avec le QCM

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 ?

Faire le QCM →

Consultez la fiche

Révisez le cours complet dans la fiche de révision de Complexité des algorithmes.

Voir la fiche →

Cours similaires

Crée tes propres flashcards

Importe ton cours et l'IA génère des flashcards en 30 secondes.

Générateur de flashcards