Complexité computationnelle

Concepts en informatique

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Classes de complexité

Classes de complexité

Une animation qui montre l'ensemble des complexités de problèmes

Une image qui montre l'espace des problèmes P

Classe de complexité -->	P (temps polynomial)
Ce que ça veut dire	Se résout rapidement et efficacement
Exemple	Trier une liste
Analogie	« Classement de documents par ordre alphabétique »
Point clé	« Faciles » du point de vue computationnel

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Une image qui montre l'espace des problèmes P et NP

Classe de complexité -->	NP (temps polynomial non déterministe)
Ce que ça veut dire	Solution vérifiable, difficile de trouver une nouvelle solution
Exemple	Vérifier qu'un Sudoku est correct
Analogie	« Trouver un document précis avec des infos manquantes »
Point clé	Vérifier est « facile », trouver une solution est difficile

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Une image qui montre l'espace des problèmes P, NP et NP-complet

Classe de complexité -->	NP-complet
Ce que ça veut dire	Les plus difficiles de NP. Spéciaux car résoudre l'un résout tout NP
Exemple	Problème du voyageur de commerce
Analogie	« Casse-tête complexe : facile à vérifier, difficile à résoudre »
Point clé	Aucune solution efficace connue. Si on en trouve une, tout NP serait résolu

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Une image qui montre l'espace des problèmes P, NP, NP-complet et NP-difficile

Classe de complexité -->	NP-difficile
Ce que ça veut dire	Aussi difficile que NP-complet ou plus
Exemple	Planification optimale avec fortes dépendances et non vérifiable
Analogie	« Fixer une heure de réunion optimale avec de nombreuses contraintes, non vérifiable vite »
Point clé	Peut être irréaliste à résoudre en pratique

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Un diagramme qui pose la sempiternelle question de recherche : P=NP ?

Concepts en informatique