Les théoriciens (en tous cas, ceux qui travaillent dans le même labo que moi) ont plutôt tendance à envisager la complexité dans le pire des cas, parce que sur la plupart des problèmes combinatoires "difficiles" (ceux qui se situent dans la transition de phase), elle est proche de la complexité en pratique: si ton problème n'est ni trivialement soluble ni trivialement insoluble, il y a de gros risques pour que tu sois obligé d'explorer une bonne partie de l'espace de recherche avant de pouvoir répondre.
Mais pour grossir le trait, on peut séparer les problèmes en deux catégories: ceux qui sont NP-difficiles (par exemple le voyageur de commerce), et dont la résolution prend dans le pire des cas un temps exponentiel dans la taille de la donnée initiale, et ceux qui se contentent d'un traitement polynomial. Pour ces derniers, on peut raffiner un peu, calculer la complexité en moyenne, l'espérance de solution, tout ça... parce qu'il faut bien comprendre que même si c'est polynomial, n^4 ça commence à devenir pénible. Pour les premiers, en revanche, on a trois solutions: soit on trouve des traitements polynomiaux pour réduire l'espace de recherche, soit on réussit à approximer la réponse à un facteur constant près en temps polynomial (c'est à dire qu'on sait donner "rapidement" une solution dont on peut garantir qu'elle n'est, par exemple, pas à plus de 50% de la meilleure solution possible), soit... on rame.
[^] # Complexité asymptotique
Posté par Polaris . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 3.
Mais pour grossir le trait, on peut séparer les problèmes en deux catégories: ceux qui sont NP-difficiles (par exemple le voyageur de commerce), et dont la résolution prend dans le pire des cas un temps exponentiel dans la taille de la donnée initiale, et ceux qui se contentent d'un traitement polynomial. Pour ces derniers, on peut raffiner un peu, calculer la complexité en moyenne, l'espérance de solution, tout ça... parce qu'il faut bien comprendre que même si c'est polynomial, n^4 ça commence à devenir pénible. Pour les premiers, en revanche, on a trois solutions: soit on trouve des traitements polynomiaux pour réduire l'espace de recherche, soit on réussit à approximer la réponse à un facteur constant près en temps polynomial (c'est à dire qu'on sait donner "rapidement" une solution dont on peut garantir qu'elle n'est, par exemple, pas à plus de 50% de la meilleure solution possible), soit... on rame.