Complexité en espace

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. 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 les entrées de taille n, est l'espace le plus grand pour les entrées de cette taille ; 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 la taille des entrées tend 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[modifier | modifier le code]

La 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 | modifier le code]

  1. a et b Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4 (« Considérations de base sur l’espace »).