Un algorithme constitue une série d'instructions organisées pour résoudre un problème spécifique. Il existe plusieurs manières d'aborder la solution d'un problème, mais il est essentiel d'analyser l'efficacité de chaque méthode afin de choisir la plus appropriée. Cela nous conduit à explorer la notion de complexité algorithmique. La complexité d'un algorithme évalue les ressources nécessaires à son exécution sur un ensemble de données donné. En comparant la complexité des algorithmes, on peut juger de leur performance pour un problème donné. Cette complexité dépend de la taille des données d'entrée. Il est important de noter que les ressources peuvent inclure le temps ou la mémoire ; ainsi, on distingue généralement la complexité temporelle (concernant le temps d'exécution) et la complexité spatiale (relatif à la mémoire utilisée) ; en règle générale, la discussion se concentre sur la complexité temporelle, qui sera notre principal sujet d'étude. La complexité peut également varier selon la configuration des données d'entrée, ce qui nous amène à considérer les scénarios du meilleur, du moyen et du pire cas. Il convient de mentionner que les complexités ne sont pas toujours exprimées de manière précise : nous nous appuierons sur les ordres de grandeur pour définir certaines catégories de fonctions. Ce cours sera structuré autour des thèmes suivants : un rappel sur les mathématiques des équations récurrentes, les ordres de grandeur et leurs relations, suivi de la présentation de diverses méthodes d'évaluation de la complexité pour les structures conditionnelles et itératives, et enfin, nous appliquerons ces concepts à l'analyse de la complexité de plusieurs algorithmes.