Melaksanakan Tatasusunan Dinamik

Menganggap pemahaman tatatanda Big O. Contohnya adalah dalam JavaScript. Rujukan maklumat "Cracking the Coding Interview" oleh Gayle Laakmann McDowell

pengenalan

Dalam sesetengah bahasa seperti JavaScript atau Python, tatasusunan boleh diubah saiz secara automatik, bermakna ia akan berkembang semasa anda menambahkan item. Dalam bahasa lain seperti Java, tatasusunan ialah panjang tetap, bermakna saiz ditentukan apabila anda memulakan tatasusunan. Tatasusunan yang berkembang secara automatik ini dipanggil tatasusunan dinamik.

Memahami Tatasusunan Dinamik

Di Java, ArrayList ialah struktur data seperti tatasusunan yang menawarkan saiz semula dinamik sambil tetap menyediakan $O(1)$O(1) akses. Apabila tatasusunan penuh, tatasusunan berganda saiznya. Setiap penggandaan mengambil $O(n)$O(n) masa, tetapi jarang berlaku sehingga masa sisipan terlunasnya masih $O(1)$O(1) .

Antara bahasa pengaturcaraan yang berbeza, nama struktur data ini serta faktor saiz semulanya (iaitu 2 dalam Java) berbeza-beza. Faktor saiz semula menentukan saiz tatasusunan yang lebih besar.

Mengapa Masa Sisipan Dilunaskan $O(1)$O(1) ?

Apabila mengubah saiz, dengan mengandaikan faktor saiz semula ialah 2, kita boleh melihat bahawa kita meningkat kepada tatasusunan saiz N dengan menggandakan tatasusunan sebelumnya (iaitu separuh daripada N). Tambahan pula, kita juga perlu meniru $N\mathrm{/}2$N/2 elemen kepada tatasusunan baharu ini.

Jika kita menjumlahkan bilangan elemen yang kita salin daripada peningkatan kapasiti terakhir kepada peningkatan kapasiti pertama: $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+\mathrm{.}\mathrm{.}\mathrm{.}+2+1$ 2n​+4n​+8n​+16n​+...+2+1 yang berjumlah hanya kurang daripada N. Oleh itu, memasukkan unsur N mengambil masa kira-kira $O(n)$O(n) bekerja secara total. Setiap sisipan adalah $O(1)$O(1) secara purata, walaupun beberapa sisipan mengambil $O(n)$O(n) masa dalam kes yang paling teruk.

Konsep Teras dan Kerumitan O Besar

Tatasusunan dinamik dalam JavaScript biasanya mempunyai beberapa kaedah teras, setiap satu dengan kerumitan masa yang berbeza:

get(i): Kaedah ini mendapatkan semula elemen pada indeks i.

• Kerumitan: $O(1)$O(1)

set(i, n): Kaedah ini menetapkan elemen pada indeks i kepada n.

• Kerumitan: $O(1)$O(1)

tolak(n): Kaedah ini menambahkan elemen n pada penghujung tatasusunan.

• Kerumitan: $O(1)$O(1) dilunaskan, tetapi $O(n)$O(n) apabila ubah saiz berlaku

popback(): Kaedah ini mengalih keluar elemen terakhir tatasusunan.

• Kerumitan: $O(1)$O(1)

saiz semula(): Kaedah ini menggandakan kapasiti tatasusunan dan menyalin semua elemen ke tatasusunan baharu.

• Kerumitan: $O(n)$O(n)

getSize(): Kaedah ini mengembalikan bilangan elemen dalam tatasusunan.

• Kerumitan: $O(1)$O(1)
• Nota: kami dapat mencapai kerumitan ini dengan menggunakan pembolehubah saiz untuk menjejaki bilangan slot yang diisi dalam tatasusunan.

getCapacity(): Kaedah ini mengembalikan kapasiti semasa tatasusunan.

• Kerumitan: $O(1)$O(1)

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

Kesimpulan

Tatasusunan dinamik ialah struktur data yang berkuasa yang menggabungkan fleksibiliti storan boleh saiz semula dengan kecekapan akses masa tetap. Semoga ini membantu!

Atas ialah kandungan terperinci Melaksanakan Tatasusunan Dinamik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!