Je completerais ta vision "theorique" de la complexite par une autre vision :
La complexite au pire cas n'est pas toujours adapte, on prefere parfois une complexite qui depend de la complexite de la sortie (notamment en geometrie algorithmique). Imagine que tu souhaites calculer les intersections de n segments. La complexite au pire est superieure ou egal a o(n^2) car il peut y avoir o(n^2) intersections, l'algoritme brutal en o(n^2) (tester tous les segments deux a deux) est bon relativement au critere du pire cas. En pratique on lui prefera un algorithme en o(n.log(n) + k) ou k est le nombre d'intersections ou meme en o((n+k).log(n)) car il est plus simple.
parce qu'il faut bien comprendre que même si c'est polynomial, n^4 ça commence à devenir pénible.
En pratique, pour bien des problemes on considere qu'au dessus de o(n^2) c'est limite (et meme souvent au dessous), un jour ou l'autre on tombera sur une instance qui fera que ca va ramer.
Pour les problemes NP-difficiles, 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.
En pratique, les problemes d'optimisation reelles sont souvent NP-difficiles meme si l'on restreint enormement les instances et meme si l'on neglige certaines contraintes importantes. Les criteres d'optimisation sont eux multiples. Par contre, la recherche de l'optimalite n'a que d'importance, il s'agit de trouver une solution acceptable (50% de la solution optiomale, c'est souvent inacceptable en pratique, pour un voyage de commerce pex) et en tout etat de cause meilleure que les solutions existantes (ou concurrentes).
[^] # Re: Complexité asymptotique
Posté par Alberto . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 1.
La complexite au pire cas n'est pas toujours adapte, on prefere parfois une complexite qui depend de la complexite de la sortie (notamment en geometrie algorithmique). Imagine que tu souhaites calculer les intersections de n segments. La complexite au pire est superieure ou egal a o(n^2) car il peut y avoir o(n^2) intersections, l'algoritme brutal en o(n^2) (tester tous les segments deux a deux) est bon relativement au critere du pire cas. En pratique on lui prefera un algorithme en o(n.log(n) + k) ou k est le nombre d'intersections ou meme en o((n+k).log(n)) car il est plus simple.
parce qu'il faut bien comprendre que même si c'est polynomial, n^4 ça commence à devenir pénible.
En pratique, pour bien des problemes on considere qu'au dessus de o(n^2) c'est limite (et meme souvent au dessous), un jour ou l'autre on tombera sur une instance qui fera que ca va ramer.
Pour les problemes NP-difficiles, 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.
En pratique, les problemes d'optimisation reelles sont souvent NP-difficiles meme si l'on restreint enormement les instances et meme si l'on neglige certaines contraintes importantes. Les criteres d'optimisation sont eux multiples. Par contre, la recherche de l'optimalite n'a que d'importance, il s'agit de trouver une solution acceptable (50% de la solution optiomale, c'est souvent inacceptable en pratique, pour un voyage de commerce pex) et en tout etat de cause meilleure que les solutions existantes (ou concurrentes).