Fiche de révision : Complexité des algorithmes

Plan du Cours

  1. Mesure des performances algorithmiques
  2. Ordres de grandeur et notation grand O
  3. Calcul de la complexité au pire cas
  4. Analyse des algorithmes récursifs
  5. Exemples de complexité algorithmique
  6. Amélioration de Fibonacci et recherche dichotomique

1. Mesure des performances algorithmiques

Points essentiels

📌 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.

Astuce mémo

Empirique : mesurer l’exécution ; théorique : compter les ressources.

2. Ordres de grandeur et notation grand O

Notions clés & Définitions

  • Notation grand O : La notation grand O signifie que, pour des constantes c et n₀, toute valeur n ≥ n₀ vérifie |f(n)| ≤ c|g(n)| lorsque f est en O(g).

★ À 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 :

    • constante O(1)
    • logarithmique O(log(n))
    • linéaire O(n)
    • quadratique O(n²)
    • polynomiale O(nᵏ)
    • exponentielle O(kⁿ)

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).

3. Calcul de la complexité au pire cas

★ À maîtriser

  • Pour calculer la complexité au pire cas, on additionne les coûts des lignes, multiplie le coût du contenu d’une boucle par son nombre maximal de répétitions, prend le coût maximal des branches d’une condition, compte les tests et simplifie le résultat en grand O.

Compléments

  • Une déclaration simple coûte par défaut O(1), et les appels de fonctions qu’elle contient s’additionnent au coût de l’instruction.

📌 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.

4. Analyse des algorithmes récursifs

★ À 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

  • Dans une branche conditionnelle qui arrête une récursion, le calcul au pire cas doit tenir compte de cet arrêt.

5. Exemples de complexité algorithmique

★ À maîtriser

  • La factorielle itérative initialise une variable, effectue au plus n itérations et utilise une mémoire constante, ce qui donne une complexité temporelle O(n) et une complexité mémoire O(1).

Compléments

  • Le calcul de l’écart type parcourt les n nombres pour calculer la moyenne puis la variance, ce qui donne une complexité O(n).

6. Amélioration de Fibonacci et recherche dichotomique

Points essentiels

  • 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.

Astuce mémo

Fibonacci récursif → Fibonacci en O(n) → Fibonacci en O(log n).

Teste tes connaissances

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 ?

Faire le QCM →

Révisez avec les flashcards

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.

Voir les flashcards →

Cours similaires

Crée tes propres fiches de révision

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

Générateur de fiches