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

導入

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

動的配列を理解する

Java では、ArrayList は を提供しながら動的なサイズ変更を提供する配列のようなデータ構造です。 $O(1)$O(1) アクセス。配列がいっぱいになると、配列のサイズが 2 倍になります。 2倍になるごとに時間がかかります $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{.}21$2n 4n 8 n 16n ... 2 1 これは合計が N よりわずかに小さいことになります。したがって、N 個の要素を挿入するには約 $O(n)$の上） 合計で働きます。それぞれの挿入は、 $O(1)$O(1) 一部の挿入に時間がかかる場合でも、平均して $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)$の上） サイズ変更が発生したとき

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

• 複雑： $O(1)$O(1)

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

• 複雑： $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 = this.size) return undefined;
        return this.arr[i];
    }

    // O(1)
    set(i, n) {
        if (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 




  
  
  結論


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