Prolongements sur la complexité
I. La fonction d'Ackermann
La fonction d'Ackermann est un exemple classique de fonction récursive qui "explose" très vite. Vous pouvez la tester grâce au fichier complexiteAckermann.py. Pour plus d'informations, voir la page qui y est consacrée sur Wikipedia. La définition de la fonction Ackermann est la suivante :
A(0, n) = n + 1 A(m, 0) = A(m-1, 1) si m > 0 A(m, n) = A(m-1, A(m, n-1)) si m > 0 et n > 0
II. Efficacité des langages de programmation
Pour résoudre un problème efficacement, l'efficacité d'un langage de programmation passe bien sûr après le problème de la complexité, Surtout s'il s'agit de résoudre ponctuellement un gros problème. Mais s'il s'agit de résoudre fréquemment des problèmes de tailles petites à moyennes, la question est tout autre. À titre d'exemple, voici un extrait d'une comparaison publiée sur la page https://thenewstack.io/which-programming-languages-use-the-least-electricity/ :
| Langage | Efficacité en temps |
Efficacité en espace |
|---|---|---|
| C | 1 | 1,17 |
| Java | 1,89 | 6,01 |
| C# | 3,14 | 2,85 |
| swift | 4,20 | 2,71 |
| javascript | 6,52 | 4,59 |
| PHP |
27,64 | 2,57 |
| Python | 71,90 | 2,80 |
III. Pour aller encore plus loin
L'étude de la complexité est un problème de recherche qui date des "débuts" de l'informatique et qui est encore d'actualité. En 1965, Juris Hartmanis et Richard E. Stearns définissent les premières classes de complexité. Voici une présentation rapide de quelques classes de complexité :
- P : problèmes décidables en temps polynomial par une machine déterministe : il y a un algorithme polynomial permettant de résoudre le problème ;
- NP : problèmes décidables en temps polynomial par une machine indéterministe : il y a un algorithme polynomial pour dire si une solution candidate est effectivement une solution du problème ;
- EXPTIME : problèmes décidables en temps exponentiel par une machine déterministe : il y a un algorithme exponentiel permettant de résoudre le problème ;
- NEXPTIME : problèmes décidables en temps exponentiel par une machine indéterministe : il y a un algorithme exponentiel pour dire si une solution candidate est effectivement une solution du problème.
Il a été prouvé (démonstration triviale) que P ⊂ NP. Par contre, la question P = NP reste un problème ouvert.