La complexité d'un algorithme se réfère au nombre d'opérations élémentaires (telles que les affectations, les comparaisons et les calculs arithmétiques) nécessaires à son exécution sur un ensemble de données. Évaluer cette complexité permet d'estimer les ressources requises et de mesurer le temps d'exécution de l'algorithme. Toutefois, cette complexité est influencée par la taille, la nature et l'organisation des données d'entrée. Selon la ressource considérée (temps ou espace), on distingue la complexité temporelle (temps) de la complexité spatiale (espace), mais en général, le terme "complexité" fait référence à la complexité temporelle. On peut analyser cette complexité sous différents angles : au pire des cas (scénario défavorable), au meilleur des cas (scénario favorable) et au cas moyen. Établir précisément la complexité d'un algorithme, même simple, peut s'avérer particulièrement difficile ; c'est pourquoi nous utilisons des outils mathématiques tels que les ordres de grandeur pour y parvenir.
Dans ce cours, nous commencerons par revoir quelques concepts mathématiques relatifs aux récurrences linéaires, suivis par une discussion sur les ordres de grandeur. Nous aborderons ensuite la complexité en détail, les méthodes pour l’évaluer, et enfin, nous fournirons la complexité et le principe de divers algorithmes.