Pour résoudre un problème, une solution "simple" a priori est la méthode exhaustive: on passe en revue tous les cas en ne retenant que ceux qui satisfont les contraintes.
Cela peut nous amener à envisager toutes les permutations possibles.
Comme il y a $n!$ permutations de $n$ objets, expliquez pourquoi cette stratégie ne peut être utilisée que pour des entiers $n$ "petits".
- Une réponse possible
Considérons un processeur à 5Gh, et disons (pour simplifier) que notre processeur effectue 5 milliards d'opérations par seconde ( une adresse pour clarifier un peu cela). Admettons maintenant que nous devions envisager toutes les permutations sur 20 objets: $\frac{ 20!}{ 5\cdot 10^9 \times \left(60\times 60 \times 24 \times 365\right)} \approx 15$
Il nous faut donc déjà 15 années de calcul pour un nombre aussi petit que 20...
Par contre $\frac{15!}{5\cdot 10^9} \approx 261$ (en seconde). Pour 15 objets, on peut encore espérer être dans un temps de calcul raisonnable.
Une citation (Donald Knuth in "The Art of Computer Programming", volume 1) :
It is helpful to keep the value of $10! = 3\ 628\ 800$ in mind; one should remember that $10!$ is about $3\frac{1}{2}$ million. In a sense, this number represents an approximate dividing line between things that are practical to compute and things that are not. If an algorithm requires the testing of more than 10! cases, it may consume too much computer time to be practical. On the other hand, if we decide to test 10! cases and each requires, say, one millisecond of computer time, then the entire run will take about an hour.