Originariamente inviato da John360
Non ho ben capito su cosa si basi la complessità spaziale(e come si calcoli) e se dipenda da un linguaggio specifico. Per quella temporale non ci sono problemi ma ma non riesco a capire cosa si debba fare per calcolare quella spaziale!
Ad esempio, si ha un albero e si deve cercare un certo elemento, il tempo peggiore di un algoritmo di ricerca è O(n) nel caso l'elemento non sia presente, il migliore è O(1), cioè si trova nella radice. In quella spaziale, di cosa devo tener conto? Le aree dati dell'algoritmo(ricorsivo) o cosa?
Grazie in anticipo
L'analisi si fa sugli algoritmi ed è quindi in genere indipendente dal linguaggio, queste domande andrebbero in "Programmazione".

La complessità spaziale è la quantità di memoria che l'algoritmo richiede per essere eseguito, sempre in termini asintotici ed in funzione della dimensione della dimensione dell'input, come nel caso della complessità temporale, e allo stesso modo ci sono i tre casi: migliore, medio e peggiore.

Se per esempio un algoritmo prende in input un vettore di N elementi, e nello svolgimento deve allocare un array di N elementi, la sua occupazione spaziale sarà Θ(N), se invece necessita solo di qualche variabile, l'occupazione sarà Θ(1).

Nel caso di algoritmi ricorsivi, si può tenere conto anche della memoria che l'algoritmo occupa sullo stack: nel tuo esempio, un algoritmo ricorsivo che visiti l'albero potrebbe non creare esplicitamente alcuna struttura dati, ma facendo una chiamata ricorsiva per ogni nodo di fatto l'occupazione diventerebbe Θ(N). Un algoritmo con lo stesso scopo ma iterativo non avrebbe questo problema, la sua occupazione sarebbe costante, Θ(1).