Introduction

Dans le domaine de l’informatique, lors de la résolution d’un problème, il est très important et intéressant de savoir le temps qui sera nécessaire à sa résolution ainsi que l’espace mémoire. Afin de résoudre ce calcul, la "théorie de la complexité" a été mise au point.

Celle-ci a en effet pour objectif d’étudier la difficulté d’un problème en estimant la nécessité en temps et en espace mémoire de celui-ci. Elle permet donc, à partir  d’un problème, d’estimer ses ressources spatiales et temporelles pour le résoudre.