Wie berechnet man die Raumkomplexität der Funktion? - Algorithmus, Raumkomplexität

Ich habe das grundlegende verstanden, wenn ich eine Funktion wie diese habe:

int sum(int x, int y, int z) {
int r = x + y + z;
return r;
}

es erfordert 3 Einheiten Platz für die Parameter und 1 für die lokale Variable, und dies ändert sich nie, so ist dies O(1).

Was aber, wenn ich eine Funktion wie diese habe:

void add(int a[], int b[], int c[], int n) {
for (int i = 0; i < n; ++i) {
c[i] = a[i] + b[0]
}
}

Was erfordert N Einheiten für a, M Einheiten für b und L Einheiten für c und 1 Einheit für i und n. So wird es brauchen N+M+L+1+1 Menge an Speicherplatz.

Also, was wird das Big-O für Raumkomplexität hier? Derjenige, der höhere Speicher braucht? I.e. wenn N mehr momery als M und L nimmt (von viel höheren Mitteln nehme an, größer als 10**6) - so ist es sicher zu sagen, die Komplexität des Raumes ist O(N) oder nicht wie wir es für Zeitkomplexität tun?

Aber wenn alle drei, a, b, c sind nicht sehr unterschiedlich

Wie diese Funktion

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];
}
}
}

Was wird dann die Raumkomplexität sein? O(N+M+L)? Oder immer noch der Größte?

Antworten:

3 für die Antwort № 1

Die räumliche Komplexität eines Algorithmus oder DatenStruktur ist die maximale Menge an Speicherplatz, die gleichzeitig verwendet wird, wobei der von der Eingabe für den Algorithmus verwendete Speicherplatz ignoriert wird. Daher ist die Raumkomplexität aller drei Beispiele in Ihrer Frage O (1)

---

2 für die Antwort № 2

Wenn wir von Raumkomplexität sprechen, berücksichtigen wir nicht den Raum, den die Eingabe verwendet.

Dies erlaubt uns, über Algorithmen zu sprechen, die ein konstanter Raum, O (log n) -Raum usw. sind. Wenn wir mit dem Zählen der Eingabe beginnen, dann sind alle Algorithmen zumindest ein linearer Raum!

Die Standard-Multitape-Turing-Maschine, die die Raumkomplexität definiert, zählt auch nicht die Ausgabe.

Die Eingabe ist nur lesbar, und die Ausgabe ist nur schreibend und zählt nicht zur Raumkomplexität.

Also, um Ihre Frage zu beantworten: Suchen Sie nach welcher Erinnerung Ihre Methode allokiert, einschließlich Stack-Platz für Rekursion / lokale Variablen usw., und das wird Bestimmen Sie die Komplexität des Platzes.

---