實現動態數組

假設理解 Big O 表示法。 JavaScript 中有範例。資料參考 Gayle Laakmann McDowell 的《Cracking the Coding Interview》

介紹

在 JavaScript 或 Python 等某些語言中，陣列會自動調整大小，這表示陣列會隨著您追加專案而成長。在 Java 等其他語言中，陣列是固定長度的，這表示陣列的大小是在初始化陣列時定義的。這些自動增長的陣列稱為動態數組。

了解動態數組

在 Java 中，ArrayList 是一種類似陣列的資料結構，它提供動態調整大小的同時仍提供 $O(1))$O(1) O(1)$O()$n)O(n🎜> $時間，但發生的情況很少，因此其攤銷插入時間仍然是\mathrm{}($1)1

)

O(1)

$.\mathrm{在不同的程式語言中，此資料結構的名稱及其調整大小因子（Java\; 中為\; 2）各不相同。調整大小因子決定陣列大小會調整多大。}為什麼是攤銷插入時間$O(1

)

1$)O(1)\mathrm{}\mathrm{O(1)}？$ 調整大小時，假設調整大小因子為 2，我們可以觀察到透過將前一個陣列加倍（即 N 的一半），我們增加到大小為 N 的陣列。此外，我們還需要複製

N/2N/22N/2N/2N/2 >N/2 元素添加到這個新數組。

如果我們將從最終容量增加到第一次容量增加複製的元素數量相加： $\frac{n}{2}+2\frac{}{\mathrm{(🎜>}}4\frac{+}{\mathrm{}}8\frac{}{\mathrm{}}+8\mathrm{}+\mathrm{8}\mathrm{}+8\mathrm{}+8\mathrm{}+$+> 🎜>n16+...+2+1壓裂{n}{2} + 壓裂{n}{4} + 壓裂{n}{8 } + 壓裂{n}{16} + ...+2 + 1 2nn+ 4n 🎜>+ 🎜>n$$16$161616n$$>\; 🎜>+2+$1 其總和略小於 N。因此，插入 N 個元素大約需要

O

(n)n)O(n🎜> O(n) 總共工作。每次插入都是 O(1)1)O(1) O(1) 平均而言，即使某些插入需要 O(n)n)O(n🎜> O(n) 最壞情況下的時間。 核心概念與大O複雜性 JavaScript 中的動態陣列通常有幾個核心方法，每個方法都有不同的時間複雜度： get(i)：此方法會擷取索引 i 處的元素。

• 複雜性： $O(1))$O(1) O(1)

• set(i, n)：此方法將索引 i 處的元素設為 n。 $\mathrm{O}()$1)O(1)

O(1)

• $pushback(n)：此方法將元素\; n\; 加到陣列末尾。複雜性：\mathrm{}($1)1)$O(1)O(1)攤銷，但是$O(n
)

n

)
• O(n🎜> $\mathrm{O(n)}\mathrm{調整大小時}popback()：此方法刪除陣列的最後一個元素。複雜性：$O
(

1

)
• 1$)O(1)\mathrm{O(1)}$resize()：此方法將陣列的容量加倍，並將所有元素複製到新數組。 複雜性：

O

(
• n$)n)O(n🎜>\mathrm{}$ getSize()：此方法傳回數組中元素的數量。
複雜性：

O

(
• 1$)1)O(1)\mathrm{}$ 注意：我們可以透過使用大小變數來追蹤數組中已填充槽的數量來實現這種複雜性。

getCapacity()：此方法傳回數組的目前容量。

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

複雜性：

O(1)1)O(1) O(1) JavaScript 中的實作 結論 動態數組是一種強大的資料結構，它結合了可調整儲存大小的靈活性和恆定時間存取的效率。希望有幫助！

以上是實現動態數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！