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?"
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wenn wir reden über räumliche Komplexität, die wir nicht in Betracht ziehen, den Platz, der durch den Eingang.
Dies ermöglicht es uns, sprechen über algorithmen, die Konstante Speicherplatz, O(log n) Speicherplatz etc. Wenn wir begann zu zählen die Eingabe, dann werden alle algorithmen werden mindestens linearen Adressraum!
Die standard-multi-Band-Turing-Maschine definition von Raum Komplexität auch zählen nicht die Ausgabe.
Wird die Eingabe nur Lesen, und die Ausgabe ist nur schreiben und zählen nicht in Richtung der Raum-Komplexität.
Der Speicherplatz-Komplexität eines Algorithmus oder Datenstruktur ist die maximale Menge an Speicherplatz verwendet, zu jeder Zeit, ignorieren Sie den Platz, indem Sie die Eingabe für den Algorithmus.
Daher räumliche Komplexität aller drei Beispiele, die in Ihrer Frage ist O(1)