Algorithmique: Apprendre à écrire les algorithmes

Auteur: Mohamed CHINY Durée necessaire pour le cours de Algorithmique: Apprendre à écrire les algorithmes Niveau recommandé pour le cours de Algorithmique: Apprendre à écrire les algorithmes Supports vidéo disponibles pour ce cours Exercices de renforcement disponibles pour ce cours Quiz non disponibles pour ce cours

Page 14: Calcul de la complexité des algorithmes

Toutes les pages

La complexité des algorithmes

Calcul de la complexité asymptotique

L'efficacité d'un algorithme est jugée par l'évaluation de son temps d'exécution et par les ressources matérielles mises à sa disposition au moment de l'exécution. Cependant, pour évaluer l'efficacité d'un algorithme on s'intéresse surtout à calculer son temps d'exécution. Mais vu que ce temps peut changer d'une machine à une autre (une machine plus performante exécutera l'algorithme plus rapidement), alors on s'intéresse surtout à évaluer l'ordre de grandeur du nombre d'opérations exécutées dans un algorithme. On parle alors de complexité asymptotique.

La complexité asymptotique est représentée par le symbole Grand O. On peut donc avoir une complexité constante qui vaut O(1), une complexité linéaire qui vaut O(n), une complexité quadratique qui vaut O(n²), une complexité logarithmique qui vaut O(log(n)) etc...

La complexité des algorithmes en vidéo

Dans cette vidéo j'ai essayé d'expliqur brièvement comment calculer la complexité asymptotique d'un algorithme.
https://www.youtube.com/watch?v=vzUK6YxkhB0




  • Playlist du cours d'algorithmique complet
  • Playlist d'exercices corrigés d'algorithmique