Séance de cours
Complexité des algorithmes : notation Big-O
Description
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.