Dynamische Arrays implementieren

Setzt Verständnis der Big-O-Notation voraus. Beispiele sind in JavaScript. Informationsreferenzen „Cracking the Coding Interview“ von Gayle Laakmann McDowell

Einführung

In einigen Sprachen wie JavaScript oder Python kann die Größe von Arrays automatisch geändert werden, was bedeutet, dass sie wachsen, wenn Sie Elemente anhängen. In anderen Sprachen wie Java haben Arrays feste Längen, was bedeutet, dass die Größe definiert wird, wenn Sie das Array initialisieren. Diese automatisch wachsenden Arrays werden dynamische Arrays genannt.

Dynamische Arrays verstehen

In Java ist eine ArrayList eine Array-ähnliche Datenstruktur, die eine dynamische Größenänderung ermöglicht und gleichzeitig bereitstellt $O(1)$O(1) Zugang. Wenn das Array voll ist, verdoppelt sich seine Größe. Jede Verdoppelung dauert $O(n)$O(n) Zeit, kommt aber so selten vor, dass die amortisierte Einfügezeit immer noch beträgt $O(1)$O(1) .

Unter verschiedenen Programmiersprachen variieren der Name dieser Datenstruktur sowie ihr Größenänderungsfaktor (der in Java 2 beträgt). Der Größenänderungsfaktor bestimmt, um wie viel größer die Größe eines Arrays geändert wird.

Warum handelt es sich um amortisierte Einfügezeit? $O(1)$O(1) ?

Wenn wir die Größe ändern und davon ausgehen, dass der Größenänderungsfaktor 2 beträgt, können wir beobachten, dass wir durch Verdoppelung des vorherigen Arrays (das der Hälfte von N entspricht) auf ein Array der Größe N anwachsen. Darüber hinaus müssen wir auch kopieren $N\mathrm{/}2$N/2 Elemente zu diesem neuen Array hinzufügen.

Wenn wir die Anzahl der Elemente, die wir von der letzten Kapazitätserhöhung zur ersten Kapazitätserhöhung kopieren, summieren: $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+\mathrm{.}\mathrm{.}\mathrm{.}+2+1$ 2n​+4n​+8n​+16n​+...+2+1 was knapp weniger als N ergibt. Daher dauert das Einfügen von N Elementen etwa $O(n)$O(n) insgesamt arbeiten. Jede Einfügung ist $O(1)$O(1) im Durchschnitt, auch wenn einige Einfügungen dauern $O(n)$O(n) Zeit im schlimmsten Fall.

Kernkonzepte und Big-O-Komplexität

Dynamische Arrays in JavaScript verfügen normalerweise über mehrere Kernmethoden mit jeweils unterschiedlicher zeitlicher Komplexität:

get(i): Diese Methode ruft das Element am Index i ab.

• Komplexität: $O(1)$O(1)

set(i, n): Diese Methode setzt das Element am Index i auf n.

• Komplexität: $O(1)$O(1)

pushback(n): Diese Methode fügt das Element n am Ende des Arrays hinzu.

• Komplexität: $O(1)$O(1) amortisiert, aber $O(n)$O(n) wenn eine Größenänderung erfolgt

popback(): Diese Methode entfernt das letzte Element des Arrays.

• Komplexität: $O(1)$O(1)

resize(): Diese Methode verdoppelt die Kapazität des Arrays und kopiert alle Elemente in das neue Array.

• Komplexität: $O(n)$O(n)

getSize(): Diese Methode gibt die Anzahl der Elemente im Array zurück.

• Komplexität: $O(1)$O(1)
• Hinweis: Wir können diese Komplexität erreichen, indem wir eine Größenvariable verwenden, um die Anzahl der gefüllten Slots im Array zu verfolgen.

getCapacity(): Diese Methode gibt die aktuelle Kapazität des Arrays zurück.

• Komplexität: $O(1)$O(1)

Implementierung in JavaScript

class DynamicArray {
    // size is # of filled slots while capacity is total slots in array
    constructor(capacity) {
        this.capacity = capacity;
        this.arr = new Array(this.capacity);
        this.size = 0;
    }

    // O(1)
    get(i) {
        if (i < 0 || i >= this.size) return undefined;
        return this.arr[i];
    }

    // O(1)
    set(i, n) {
        if (i < 0 || i >= this.size) return undefined;
        this.arr[i] = n;
    }

    // O(1) amortized 
    pushback(n) {
        if (this.size === this.capacity) {
            this.resize();
        }
        this.arr[this.size] = n;
        this.size++;
    }

    // O(1) 
    popback() {
        if (this.size === 0) return undefined;
        this.size--;
        let temp = this.arr[this.size];
        this.arr[this.size] = undefined;
        return temp;

    }

    // O(n)
    resize() {
        this.capacity *= 2;
        let newArr = new Array(this.capacity);
        for (let i = 0; i < this.size; i++) {
            newArr[i] = this.arr[i];
        }
        this.arr = newArr;
    }

    // O(1)
    getSize() {
        return this.size;
    }

    // O(1) 
    getCapacity() {
        return this.capacity;
    }
}

Abschluss

Dynamische Arrays sind eine leistungsstarke Datenstruktur, die die Flexibilität eines skalierbaren Speichers mit der Effizienz eines zeitkonstanten Zugriffs kombiniert. Hoffe das hilft!

Das obige ist der detaillierte Inhalt vonDynamische Arrays implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!