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