Complexité des algorithmes : notation Big-O

Cette séance de cours couvre la complexité des algorithmes, en se concentrant sur la notation big-O, l'induction, la récursion et l'analyse des temps d'exécution des algorithmes. Il traite des classes de complexité communes, telles que constante, logarithmique, linéaire, polynomiale et exponentielle. L'instructeur explique l'impact de la complexité sur le temps de l'ordinateur et introduit des problèmes dociles, des classes NP, des problèmes NP-complets et des problèmes 3-SAT. Des exemples tels que le problème de décision de Knapsack sont utilisés pour illustrer les problèmes NP et les problèmes NP-complets. La session se termine par un résumé des problèmes traitables et leur classification dans la classe P.