Calcolo complessità spaziale algoritmi

[xneo1]

ciao a tutti, girando in rete non ho trovato nulla che possa aiutarmi.
Vorrei sapere in che modo si calcola la complessità spaziale di un algoritmo iterativo e ricorsivo

Per quanto riguarda la complessità temporale non c'è nessun problema, ma la complessità spaziale è un "buco nero"

Ad esempio per la ricerca binaria, sia che essa sia scritta in maniera iterativa sia in maniera ricorsiva si ha complessità temporale Teta(logn), però non so come calcolare la complessità spaziale.

Potete aiutarmi? Grazie.

[onlyReferee]

Ciao xneo
Innanzitutto si utilizza sempre la notazione di Landau ($O, \Omega, \Theta$) per la notazione. Poi...il tutto dipende dalla struttura dati (o strutture perché possono essere più di una) che si utilizza nell'algoritmo. Inizia l'analisi da lì. Successivamente bisogna vedere quanto e come viene utilizzata tale struttura (quanto viene riempita in maniera particolare).

[xneo1]

si ok, queste cose le so già.
Nel caso della ricerca binaria:

Versione ITERATIVA:

int ricercaBinaria(int[] v, int x):
    int inf=0, sup=v.lenght-1
    while(inf<=sup) :
        int med=(inf+sup)/2
        if(v[med]==x) return med
        if(v[med]>x) :
            sup=med-1
        else :
            inf=med+1
    return -1

a questo punto credo che la complessità spaziale sia O(1) in quanto al più viene allocato spazio al più per 3 variabili.
E' giusto come ragionamento? Il vettore in input mi pare di aver sentito che non viene conteggiato al fine del calcolo della complessità spaziale(Se si, perchè???)

Versione RICORSIVA:

ricercaBinara(int[] v, int x, int inf, int sup):
    if(inf>sup) return -1;
    int med=(inf+sup)/2
    if(v[med]==x) return med
    if(v[med]>x) return ricercaBinara(v,x,inf, med-1)
    return ricercaBinaria(v,x, med+1, sup)

Per quanto riguarda la versione ricorsiva nel caso peggiore credo che la complessità spaziale sia O(logn) in quanto al più possono esserci logn chiamate attive. Siccome ogni chiamata singola costa O(1) perchè si occupa memoria per instanziare al più delle variabili si ha O(1)*logn=O(logn).
Giusto???

[onlyReferee]

Inizio dalla versione iterativa. Bisogna che presti attenzione ad un fatto importante. Per come è scritto il codice di tale algoritmo te stai definendo una variabile $\text{med}$ per ogni iterazione del ciclo e pertanto, se il codice è scritto così non vengono allocate solo $3$ variabili ma una in più ad ogni iterazione ($\text{med}$ è dichiarata localmente al $\text{while}$). Poi... Il vettore di input nel caso della ricerca binaria iterativa non va ad aumentare la complessità spaziale per come è definito lo stesso (tre variabili le usi sia che tu lavori con un vettore di $5$ o $100$ elementi se ci pensi bene). Questo però non è vero in generale per tutti gli algoritmi chiaramente ed attenzione: se consideri il codice così per come lo hai scritto allora sì che la complessità spaziale dipende dalla dimensione dell'input (per le considerazioni fatte prima). Basti pensare ad esempio ad un mergesort oppure semplicemente alla versione ricorsiva della ricerca binaria, per la quale il ragionamento che hai fatto è corretto...
Spero di averti chiarito un po' di idee.

[xneo1]

Grazie per il supporto.

Innanzitutto non ho capito se nella versione iterativa la complessità è O(1)

Se così fosse non mi è chiaro il discorso sull'allocazione di med.
Io "uso" med ad ogni ciclo, quindi nel caso peggiore alloco med logn volte.
A questo punto potrei pensare che anche qui la complessità spaziale sia O(logn)

Però se la complessità fosse O(logn) per colpa di med, potrei comunque non usarla usando inf e sup soltanto.

Per quanto riguarda il vettore in input, in questo caso, ai fini dell'occupazione di memoria, non viene contato in quanto all'interno del metodo viene soltanto letto? O meglio la memoria occupata non dipende dal vettore. Giusto.

Comunque se potresti farmi vedere correttamente come si studia questa complessità, magari se c'è un procedimento "generale", attraverso qualche esempio.
Ad esempio per il bubble sort come mi comporto?

[onlyReferee]

Stando al tuo codice attuale la complessità nella versione iterativa per il caso da te descritto non è $O(1)$ ma $O(\log (n) * 1) = O(\log (n))$ (come dici te) proprio per via di come è dichiarato $\text{med}$. Oltre al fatto di non usare tale variabile per ridurre la complessità spaziale e calcolare così la posizione mediana direttamente come dici te puoi, in maniera molto semplice, dichiarare la variabile $\text{med}$ fuori dal ciclo $\text{while}$ ed utilizzarla comunque al suo interno per determinare la posizione mediana. In tal caso la stessa viene semplicemente sovrascritta ad ogni iterazione e la complessità spaziale si riduce ad $O(1)$ (dicesi anche costo costante).
Poi...che il vettore venga soltanto letto non significa che questi non vada ad influire sulla complessità spaziale finale, attenzione. Non è tanto quello che si fa con il vettore in input (che può influire maggiormente sulla complessità temporale) ma la dimensione dello stesso che va a determinare la complessità spaziale. Pertanto noi possiamo dire che la dimensione del vettore non influisce sulla complessità spaziale nel caso della versione iterativa ma su quella ricorsiva eccome.
Col il bubblesort è molto semplice riguardo alla complessità spaziale se ci pensi poiché hai una procedura iterativa che ordine "in place" (ossia senza bisogno di strutture aggiuntive) ed è soltanto necessario dichiarare una variabile di appoggio per lo scambio. Pertanto la complessità spaziale anche in tal caso sarà...

[xneo1]

...O(1), credo.

Quello che ancora non mi è chiaro è se i dati in input vanno contati ai fini dell'occupazione di memoria.
Cioè nel caso della ricerca binaria ricorsiva il vettore non occupa spazio fisico nell'algoritmo (non conta O(n)), però la complessità spaziale è influenzata dalla sua dimensione in quanto le chiamate attive dipendono da essa?

[onlyReferee]

"xneo":...O(1), credo.
[...]

Corretto .

"xneo":
[...]
Quello che ancora non mi è chiaro è se i dati in input vanno contati ai fini dell'occupazione di memoria.
Cioè nel caso della ricerca binaria ricorsiva il vettore non occupa spazio fisico nell'algoritmo (non conta O(n)), però la complessità spaziale è influenzata dalla sua dimensione in quanto le chiamate attive dipendono da essa?

Esatto, è la dimensione del vettore di input che di fatto conta poiché il numero delle chiamate ricorsive effettuare dipende proprio da essa (ovviamente sempre parlando nel caso peggiore).

[xneo1]

Però per quanto riguarda il metodo ricorsivo ho ancora un dubbio.
Sempre considerando il caso peggiore, quando il metodo viene invocato per la prima volta non c'è nessun problema, tuttavia ad ogni chiamata ricorsiva il vettore non occupa uno spazio Teta(n) all'interno dell'aree dati attive del metodo?

[onlyReferee]

Osservazione corretta in ogni caso. In realtà la risposta è no perché ciò che viene passato alla funzione è una referenza al primo elemento dello stesso (quindi un puntatore in memoria), altrimenti veramente faremo esplodere la stessa già con un vettore di 30-50 elementi (ad esempio). Ciò che avviene è che si hanno varie copie di quel puntatore ad ogni chiamata ricorsiva ed il che, come puoi intuire, è ininfluente sulla complessità spaziale $O(\log (n))$ che abbiamo.

[xneo1]

Perfetto. Infatti avevo pensato di trattare il parametro attuale come un puntatore.
Ti ringrazio molto, sei stato molto chiaro ed esaustivo.

[onlyReferee]

Di niente, mi fa molto piacere tu abbia le idee chiare adesso (talvolta meglio dar vita ad un thread più lungo e far sì che ci si riesca a capire al meglio piuttosto che rimanere coi dubbi).
A presto, chiedi pure ancora se hai bisogno senza farti i problemi (perché questi noi li dobbiamo risolvere e non creare )