Implémentation de tableaux dynamiques

Suppose une compréhension de la notation Big O. Les exemples sont en JavaScript. Références d'informations "Cracking the Coding Interview" par Gayle Laakmann McDowell

Introduction

Dans certains langages comme JavaScript ou Python, les tableaux sont automatiquement redimensionnables, ce qui signifie qu'ils grandissent à mesure que vous ajoutez des éléments. Dans d'autres langages comme Java, les tableaux ont des longueurs fixes, ce qui signifie que la taille est définie lorsque vous initialisez le tableau. Ces tableaux qui grandissent automatiquement sont appelés tableaux dynamiques.

Comprendre les tableaux dynamiques

En Java, une ArrayList est une structure de données de type tableau qui offre un redimensionnement dynamique tout en fournissant $O(1)$O(1) accéder. Lorsque le tableau est plein, sa taille double. Chaque doublement prend $O(n)$O(n) temps, mais cela arrive si rarement que son temps d'insertion amorti est toujours $O(1)$O(1) .

Parmi les différents langages de programmation, le nom de cette structure de données ainsi que son facteur de redimensionnement (qui est de 2 en Java) varient. Le facteur de redimensionnement détermine la taille d'un tableau qui sera redimensionné.

Pourquoi le temps d'insertion est-il amorti $O(1)$O(1) ?

Lors du redimensionnement, en supposant que le facteur de redimensionnement est de 2, nous pouvons observer que nous passons à un tableau de taille N en doublant le tableau précédent (qui est la moitié de N). De plus, nous devons également copier $N\mathrm{/}2$N/2 éléments à ce nouveau tableau.

Si l'on additionne le nombre d'éléments que l'on copie de l'augmentation de capacité finale à la première augmentation de capacité : $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+\mathrm{.}\mathrm{.}\mathrm{.}+2+1$ 2n​+4n​+8n​+16n​+...+2+1 ce qui équivaut à un peu moins de N. Par conséquent, l’insertion de N éléments prend environ $O(n)$O(n) travail au total. Chaque insertion est $O(1)$O(1) en moyenne, même si certaines insertions prennent $O(n)$O(n) temps dans le pire des cas.

Concepts de base et complexité Big O

Les tableaux dynamiques en JavaScript ont généralement plusieurs méthodes de base, chacune avec des complexités temporelles différentes :

get(i) : Cette méthode récupère l'élément à l'index i.

• Complexité : $O(1)$O(1)

set(i, n) : Cette méthode définit l'élément à l'index i sur n.

• Complexité : $O(1)$O(1)

pushback(n) : Cette méthode ajoute l'élément n à la fin du tableau.

• Complexité : $O(1)$O(1) amorti, mais $O(n)$O(n) lors du redimensionnement

popback() : Cette méthode supprime le dernier élément du tableau.

• Complexité : $O(1)$O(1)

resize() : Cette méthode double la capacité du tableau et copie tous les éléments dans le nouveau tableau.

• Complexité : $O(n)$O(n)

getSize() : Cette méthode renvoie le nombre d'éléments dans le tableau.

• Complexité : $O(1)$O(1)
• Remarque : nous pouvons atteindre cette complexité en utilisant une variable de taille pour suivre le nombre d'emplacements remplis dans le tableau.

getCapacity() : Cette méthode renvoie la capacité actuelle du tableau.

• Complexité : $O(1)$O(1)

Implémentation en 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;
    }
}

Conclusion

Les baies dynamiques sont une structure de données puissante qui combine la flexibilité du stockage redimensionnable avec l'efficacité de l'accès en temps constant. J'espère que cela vous aidera !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!