Wie berechnet sich die räumliche Komplexität der Funktion?

Verstand ich die basic, wenn ich eine Funktion wie diese:

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

es benötigt 3 Einheiten von Speicherplatz für die Parameter und 1 für die lokale variable, und diese ändert sich nie, das ist also O(1).

Aber was ist, wenn ich eine Funktion wie diese:

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

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

Also, was die big-O für Raum-Komplexität hier? Die eine, die dauert in höheren Speicher?
I. e. wenn N braucht mehr höher momery als M und L (ab sehr viel höheren Mittel angenommen, die größer als 10**6) - so ist es sicher zu sagen, dass der Raum Komplexität ist O(N) oder nicht, wie wir es tun für die Zeitkomplexität ?

Aber wenn alle drei ich.e a, b, c sind nicht sehr viel anders

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 sein, die Raum-Komplexität? O(N+M+L)? Oder immer noch der größte?

  • Wenn wir reden über räumliche Komplexität, in der Regel meinen wir, aux-Raum nötig – kein Platz für die Eingänge selbst.
  • Speicherplatz-Komplexität umfasst sowohl Hilfs-Raum und Platz, der von input. Richtig ?
  • Technisch, ja. Aber viele benutzen den Begriff, um nur bedeuten, Hilfs-Speicherplatz-Komplexität. Insbesondere möchten Sie wissen, Dinge wie, "Wenn ich vorbeigehe, diese große Datenmenge über 100 Funktionen, um wie viel mehr Speicher ich nehmen, und den Müll hab ich erstellen?"
InformationsquelleAutor Ankur Anand | 2015-05-13
Schreibe einen Kommentar