compresi la base che se ho una funzione come questa:Come calcolare la complessità dello spazio della funzione?
int sum(int x, int y, int z) {
int r = x + y + z;
return r;
}
richiede 3 unità di spazio per i parametri e 1 per la variabile locale, e questo non cambia mai, quindi questo è O(1).
Ma se ho una funzione come questa:
void add(int a[], int b[], int c[], int n) {
for (int i = 0; i < n; ++i) {
c[i] = a[i] + b[0]
}
}
che richiede N unità per a, unità M per b e L unità per c e 1 unità per i e n. Quindi sarà necessario lo spazio di archiviazione N+M+L+1+1.
Quindi quale sarà il grande-O per la complessità spaziale qui? Quello che prende più memoria? I.e. se N richiede un valore più alto di M e L (da molto più alto supponiamo che sia più grande di 10**6) - quindi è sicuro dire che la complessità dello spazio è O(N) o non come facciamo per la complessità del tempo?
Ma se tutti e tre vale a dire a, b, c non sono molto diversi
Ti piace questa funzione
void multiply(int a[], int b[], int c[][], int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
c[i] = a[i] + b[j];
}
}
}
Allora quale sarà la complessità spaziale? O(N+M+L)? O ancora il più grande?
Quando parliamo di complessità spaziale, tipicamente intendiamo lo spazio ausiliario _ necessario, non lo spazio per gli input stessi. –
La complessità dello spazio include sia lo spazio ausiliario che lo spazio utilizzato dall'input. Destra ? –
@AnkurAnand Tecnicamente, sì. Ma molti usano il termine per indicare semplicemente la complessità dello spazio ausiliario. In particolare ti piacerebbe sapere cose come: "Se passo questo grande set di dati attraverso 100 funzioni, quanta più memoria ho preso, e garbage ho creato?" – btilly