Poster un nouveau message
En réponse à :
La machine de Turing (2 / 2)
par
Patrice Debrabant
le mercredi 4 mai 2022
le mercredi 4 mai 2022
Voir au préalable La machine de Turing (1/2)
La complexité algorithmique a pour objectif de mesurer la quantité de ressources (en temps ou en espace mémoire) pour réaliser quelque chose avec un dispositif particulier (par exemple une machine de Turing). Là où la calculabilité détermine si on peut le faire en théorie, la complexité précise ce que l’on va consommer (en temps ou en espace mémoire), au minimum, pour le faire. Autrement dit si on peut le faire en pratique. On pourrait penser a priori que (...)