Pressupõe compreensão da notação Big O. Os exemplos estão em JavaScript. Referências informativas "Cracking the Coding Interview" por Gayle Laakmann McDowell

Introdução

Em algumas linguagens como JavaScript ou Python, os arrays são automaticamente redimensionáveis, o que significa que eles crescerão conforme você acrescenta itens. Em outras linguagens como Java, os arrays têm comprimentos fixos, o que significa que o tamanho é definido quando você inicializa o array. Esses arrays que crescem automaticamente são chamados de arrays dinâmicos.

Compreendendo matrizes dinâmicas

Em Java, um ArrayList é uma estrutura de dados semelhante a um array que oferece redimensionamento dinâmico enquanto ainda fornece $O(1)$O(1) acesso. Quando a matriz está cheia, ela dobra de tamanho. Cada duplicação leva $O(n)$Sobre) tempo, mas acontece tão raramente que seu tempo de inserção amortizado ainda é $O(1)$O(1) .

Entre diferentes linguagens de programação, o nome desta estrutura de dados, bem como seu fator de redimensionamento (que é 2 em Java) varia. O fator de redimensionamento determina quanto maior um array será redimensionado.

Por que o tempo de inserção é amortizado $O(1)$O(1) ?

Ao redimensionar, assumindo que o fator de redimensionamento é 2, podemos observar que aumentamos para um array de tamanho N dobrando o array anterior (que é metade de N). Além disso, também precisamos copiar $N\mathrm{/}2$N/2 elementos para esta nova matriz.

Se somarmos o número de elementos que copiamos do aumento de capacidade final para o primeiro aumento de capacidade: $\frac{n}{2}\frac{n}{4}\frac{n}{8}\frac{n}{16}\mathrm{.}\mathrm{.}\mathrm{.}21$2n​ 4n​ 8 n​ 16n ​ ... 2 1 que soma pouco menos que N. Portanto, inserir N elementos leva cerca de $O(n)$Sobre) trabalho no total. Cada inserção é $O(1)$O(1) em média, embora algumas inserções demorem $O(n)$Sobre) tempo na pior das hipóteses.

Conceitos Básicos e Complexidade Big O

Matrizes dinâmicas em JavaScript normalmente têm vários métodos principais, cada um com diferentes complexidades de tempo:

get(i): Este método recupera o elemento no índice i.

• Complexidade: $O(1)$O(1)

set(i, n): Este método define o elemento no índice i como n.

• Complexidade: $O(1)$O(1)

pushback(n): Este método adiciona o elemento n ao final do array.

• Complexidade: $O(1)$O(1) amortizado, mas $O(n)$Sobre) quando ocorre o redimensionamento

popback(): Este método remove o último elemento do array.

• Complexidade: $O(1)$O(1)

resize(): Este método dobra a capacidade do array e copia todos os elementos para o novo array.

• Complexidade: $O(n)$Sobre)

getSize(): Este método retorna o número de elementos do array.

• Complexidade: $O(1)$O(1)
• Nota: podemos atingir essa complexidade usando uma variável de tamanho para rastrear o número de slots preenchidos na matriz.

getCapacity(): Este método retorna a capacidade atual do array.

• Complexidade: $O(1)$O(1)

Implementação em 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 




  
  
  Conclusão


Matrizes dinâmicas são uma estrutura de dados poderosa que combina a flexibilidade do armazenamento redimensionável com a eficiência do acesso em tempo constante. Espero que isto ajude!