Speicherbedarf abschätzen

Neben der Zeit ist der Arbeitsspeicher die zweite knappe Ressource. Wie viel eine Reihung belegt, lässt sich schon an ihrer Deklaration ablesen.

• Einheiten:1 Byte = 8 Bit · 1 kB = 1 000 B · 1 MB = \(10^6\) B · 1 GB = \(10^9\) B.
• Reihung:new int[n] belegt \(4n\) Byte plus einen kleinen festen Kopf (etwa 16 B) — also \(O(n)\).
• Tabelle:new int[z][s]: \(z \cdot s\) Elemente, dazu je Zeile ein Kopf und eine Referenz.
• Referenztypen:eine String[]-Reihung speichert nur Referenzen (4–8 B je Element); die Texte selbst liegen zusätzlich im Speicher.
• * boolean:fachlich reicht 1 Bit; Java legt in Reihungen aber meist 1 Byte je Element an.

Beim Algorithmus zählt nicht die Eingabe selbst, sondern was er zusätzlich anlegt — in Abhängigkeit von \(n\).

• In-place:nur einzelne Hilfsvariablen, unabhängig von \(n\): \(O(1)\) — Selection-, Insertion-, Bubblesort, lineare und binäre Suche.
• Kopie:eine zweite Reihung gleicher Länge, z. B. eine sortierte Kopie neben dem Original: \(O(n)\).
• Markierungsreihung:ein Feld je möglichem Wert: \(O(W)\) für den Wertebereich \(W\) — klein bei Noten 1–6, riesig bei Telefonnummern.
• Rekursion:jeder offene Aufruf belegt Platz auf dem Stapelspeicher — die rekursive binäre Suche braucht \(O(\log n)\).

Ordne die Deklarationen nach ihrem Speicherbedarf — oben der kleinste, unten der größte. Ziehen, oder mit Leertaste aufnehmen, mit ↑/↓ verschieben und mit Leertaste ablegen. „Prüfen“ zeigt die Byte-Werte.

Halte fest: Der Speicherbedarf einer Reihung ist Anzahl der Elemente · Byte je Element. Eine Tabelle mit \(z\) Zeilen und \(s\) Spalten zählt wie eine Reihung mit \(z \cdot s\) Elementen.

• Zeit gegen Speicher:doppelte Werte finden: paarweise vergleichen kostet \(O(n^2)\) Zeit und \(O(1)\) Speicher, eine Markierungsreihung \(O(n)\) Zeit und \(O(W)\) Speicher.

static boolean hatDoppelte(int[] a, int max) {  // alle Werte in 0 … max
    boolean[] gesehen = new boolean[max + 1];   // Zusatzspeicher: max + 1 Byte
    for (int x : a) {
        if (gesehen[x]) {
            return true;                        // x kam schon einmal vor
        }
        gesehen[x] = true;
    }
    return false;
}