動的配列の実装

Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参照先「Cracking thecoding Interview」ゲイル・ラークマン・マクダウェル著

導入

JavaScript や Python などの一部の言語では、配列は自動的にサイズ変更可能です。つまり、項目を追加すると配列が大きくなります。 Java などの他の言語では、配列は固定長です。つまり、サイズは配列を初期化するときに定義されます。自動的に拡張されるこれらの配列は、動的配列と呼ばれます。

動的配列を理解する

Java では、ArrayList は を提供しながら動的なサイズ変更を提供する配列のようなデータ構造です。 $O(1)$O(1) アクセス。配列がいっぱいになると、配列のサイズが 2 倍になります。 2倍になるごとに時間がかかります $O(n)$O(n) しかし、滅多に起こらないため、その償却挿入時間は依然として $O(1)$O(1) .

プログラミング言語が異なると、このデータ構造の名前とそのサイズ変更係数 (Java では 2) が異なります。サイズ変更係数によって、配列のサイズがどのくらい大きくなるかが決まります。

なぜ挿入時間が償却されるのか $O(1)$O(1) ?

サイズ変更の際、サイズ変更係数が 2 であると仮定すると、前の配列 (N の半分) を 2 倍にすることでサイズ N の配列に増加することがわかります。さらに、コピーする必要もあります $N\mathrm{/}2$N/2 要素をこの新しい配列に追加します。

最後の容量増加から最初の容量増加までにコピーする要素の数を合計すると、次のようになります。 $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+\mathrm{.}\mathrm{.}\mathrm{.}+2+1$ 2n+4n+8n+16n+...+2+1 これは合計が N よりわずかに小さいことになります。したがって、N 個の要素を挿入するには約 $O(n)$O(n) 合計で働きます。それぞれの挿入は、 $O(1)$O(1) 一部の挿入に時間がかかる場合でも、平均して $O(n)$O(n) 最悪の場合は時間がかかります。

中心となる概念と Big O の複雑さ

JavaScript の動的配列には通常、時間計算量が異なるいくつかのコア メソッドがあります。

get(i): このメソッドはインデックス i の要素を取得します。

• 複雑さ: $O(1)$O(1)

set(i, n): このメソッドは、インデックス i の要素を n に設定します。

• 複雑さ: $O(1)$O(1)

pushback(n): このメソッドは要素 n を配列の末尾に追加します。

• 複雑さ: $O(1)$O(1) 償却されますが、 $O(n)$O(n) サイズ変更が発生したとき

popback(): このメソッドは配列の最後の要素を削除します。

• 複雑さ: $O(1)$O(1)

resize(): このメソッドは配列の容量を 2 倍にし、すべての要素を新しい配列にコピーします。

• 複雑さ: $O(n)$O(n)

getSize(): このメソッドは配列内の要素の数を返します。

• 複雑さ: $O(1)$O(1)
• 注: この複雑さは、サイズ変数を使用して配列内の埋まっているスロットの数を追跡することで実現できます。

getCapacity(): このメソッドは、配列の現在の容量を返します。

• 複雑さ: $O(1)$O(1)

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

結論

動的配列は、サイズ変更可能なストレージの柔軟性と定時アクセスの効率性を組み合わせた強力なデータ構造です。これがお役に立てば幸いです!

以上が動的配列の実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。