Complexité en espace
En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées. L'espace compte le nombre maximum de cases mémoire utilisées simultanément pendant un calcul. Par exemple le nombre de symboles qu'il faut conserver pour pouvoir continuer le calcul.
Usuellement l'espace que l'on prend en compte lorsque l'on parle de l'espace nécessaire pour des entrées ayant des propriétés données est l'espace nécessaire le plus grand parmi ces entrées ; on parle de complexité en espace dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque les grandeurs des entrées qui influencent la complexité spatiale tendent vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Une autre mesure de la complexité est la complexité en temps.
Classes de complexité associées
modifierLa théorie de la complexité consiste à regrouper des problèmes algorithmiques utilisant des ressources similaires. La classe de complexité DSPACE(f), pour une fonction f croissante, est la classe des problèmes qui peuvent être résolus avec un espace O(f) de façon déterministe. L'espace est ici le nombre de cases du ruban de travail de la machine de Turing visités pendant le calcul[1]. Pour parler de SPACE(f), on doit aussi ajouter la condition que la machine s'arrête sur toutes les entrées[1].
La classe NSPACE(f) correspond à DSPACE mais pour les machines non-déterministes.
Les classes en espace classiques sont L, NL, PSPACE et EXPSPACE. Le théorème de Savitch relie les classes déterministes et non-déterministes.
Notes et références
modifier- Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4 (« Considérations de base sur l’espace »).
