Calcolo complessità spaziale

[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

[Kaamos]

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).

[John360]

ah scusami! Il fatto è che siccome sto studiando java mi viene automatico postare una domanda del genere qui però alcune complessità possono lo stesso variare dato che in java non è permessa la tail recursion! In ogni caso se l'algoritmo occupa delle variabili, perchè la complessità è Θ(1) e non Θ(n) dove n è il numero delle variabili istanziate? E soprattutto perchè hai usato Θ e non O(scusa l'ignoranza )

[Kaamos]

Originariamente inviato da John360
ah scusami! Il fatto è che siccome sto studiando java mi viene automatico postare una domanda del genere qui però alcune complessità possono lo stesso variare dato che in java non è permessa la tail recursion! In ogni caso se l'algoritmo occupa delle variabili, perchè la complessità è Θ(1) e non Θ(n) dove n è il numero delle variabili istanziate? E soprattutto perchè hai usato Θ e non O(scusa l'ignoranza )

Infatti ho scritto "generalmente". Comunque non è che Java non supporti la ricorsione in coda, è la piattaforma che non ottimizza questo tipo di ricorsione, o almeno non in generale, forse alcune implementazioni lo fanno. "ricorsione in coda" significa solo che la chiamata ricorsiva è l'ultima operazione fatta dalla procedura, eventualmente ritornandone il valore.

Come fai a dichiarare N variabili dove N è un parametro in input?
Al massimo puoi allocare una quantità di spazio proporzionale a N, per esempio un array di N elementi (ed in questo caso infatti l'array occuperebbe una quantità di spazio in Θ(N)), ovviamente per "variabili" intendevo semplici variabili con un'occupazione costante, non strutture dati.

Θ e O grande sono due notazioni diverse, O grande indica un limite massimo che non viene superato, mentre Θ indica esattamente l'ordine di grandezza. Per esempio, un algoritmo che opera in tempo lineare su N elementi è in O(N), ma è anche in O(N²), in O(N³²)... ma con l'altra notazione puoi solo dire che è in Θ(N). Quest'ultima è sia un limite inferiore sotto il quale non si scende, sia un limite superiore non oltrepassato, specificando quindi l'esatto ordine di grandezza.
Per la cronaca, ci sono anche altre notazioni, trovi le informazioni su Wikipedia. Quando possibile è meglio utilizzare la notazione più informativa.

[John360]

Dimmi se ho capito bene: theta serve solo per dire su quale grandezza ci si deve basare? Cioè se costante o dipendente da qualcosa?
Riguardo la ricorsione in coda, si, io mi riferivo alla jvm ufficiale.

[Kaamos]

Originariamente inviato da John360
Dimmi se ho capito bene: theta serve solo per dire su quale grandezza ci si deve basare? Cioè se costante o dipendente da qualcosa?
Riguardo la ricorsione in coda, si, io mi riferivo alla jvm ufficiale.

Non capisco, che significa "su quale grandezza ci si deve basare"?

Queste notazioni servono per classificare funzioni matematiche come appartenenti ad un ordine di grandezza piuttosto che ad un altro. Se una funzione f appartiene a Θ(N²) potrà essere qualcosa come N², 2N², 5N²+7N... ma non potrà essere 5N, 2N³, o una funzione costante. Ma ad esempio, tutte queste funzioni che ho elencato sono in O(N³), e come vedi in questo caso non è molto informativo dato che fra una funzione costante e una cubica c'è una bella differenza.

"costante" è una funzione che restituisce sempre lo stesso risultato, indipendentemente dall'input, insomma una funzione in Θ(1). Per esempio una procedura che alloca sempre e solo 3 variabili intere, indipendentemente dai valori in input, ha un'occupazione spaziale costante, e ce l'avrebbe anche se ne allocasse sempre un miliardo.

[John360]

Ah ok! Non avevo capito prima... mi ero perso XD ora ho capito a cosa ti riferivi