DAA - Complexités spatiales

Dans ce chapitre, nous discuterons de la complexité des problèmes de calcul par rapport à la quantité d'espace requise par un algorithme.

La complexité spatiale partage de nombreuses caractéristiques de la complexité temporelle et sert de moyen supplémentaire de classer les problèmes en fonction de leurs difficultés de calcul.

Qu'est-ce que la complexité spatiale?

La complexité spatiale est une fonction décrivant la quantité de mémoire (espace) qu'un algorithme prend en termes de quantité d'entrée à l'algorithme.

On parle souvent de extra memorynécessaire, sans compter la mémoire nécessaire pour stocker l'entrée elle-même. Encore une fois, nous utilisons des unités naturelles (mais de longueur fixe) pour mesurer cela.

Nous pouvons utiliser des octets, mais il est plus facile d'utiliser, par exemple, le nombre d'entiers utilisés, le nombre de structures de taille fixe, etc.

En fin de compte, la fonction que nous proposons sera indépendante du nombre réel d'octets nécessaires pour représenter l'unité.

La complexité de l'espace est parfois ignorée parce que l'espace utilisé est minimal et / ou évident, mais parfois cela devient un problème aussi important que la complexité du temps

Définition

Laisser M être un déterministe Turing machine (TM)qui s'arrête sur toutes les entrées. La complexité spatiale deM est la fonction $ f \ colon N \ rightarrow N $, où f(n) est le nombre maximum de cellules de bande et M scanne toute entrée de longueur M. Si la complexité spatiale deM est f(n), on peut dire ça M court dans l'espace f(n).

Nous estimons la complexité spatiale de la machine de Turing en utilisant la notation asymptotique.

Soit $ f \ colon N \ rightarrow R ^ + $ une fonction. Les classes de complexité spatiale peuvent être définies comme suit -

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE est la classe des langages décidables dans l'espace polynomial sur une machine de Turing déterministe.

En d'autres termes, PSPACE = U_k SPACE (n^k)

Théorème de Savitch

L'un des premiers théorèmes liés à la complexité spatiale est le théorème de Savitch. Selon ce théorème, une machine déterministe peut simuler des machines non déterministes en utilisant une petite quantité d'espace.

Pour la complexité temporelle, une telle simulation semble exiger une augmentation exponentielle du temps. Pour la complexité spatiale, ce théorème montre que toute machine de Turing non déterministe qui utilisef(n) l'espace peut être converti en une TM déterministe qui utilise f²(n) espace.

Par conséquent, le théorème de Savitch déclare que, pour toute fonction, $ f \ colon N \ rightarrow R ^ + $, où $ f (n) \ geqslant n $

NSPACE(f(n)) ⊆ SPACE(f(n))