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 (...)