Se supone que comprende la notación O grande. Los ejemplos están en JavaScript. Referencias informativas "Cracking the Coding Interview" de Gayle Laakmann McDowell

Introducción

En algunos lenguajes como JavaScript o Python, las matrices se pueden cambiar de tamaño automáticamente, lo que significa que crecerán a medida que agregue elementos. En otros lenguajes como Java, las matrices tienen longitudes fijas, lo que significa que el tamaño se define cuando inicializa la matriz. Estas matrices que crecen automáticamente se denominan matrices dinámicas.

Comprender las matrices dinámicas

En Java, una ArrayList es una estructura de datos similar a una matriz que ofrece un cambio de tamaño dinámico sin dejar de proporcionar $O(1)$O(1) acceso. Cuando la matriz está llena, duplica su tamaño. Cada duplicación toma $O(n)$En) tiempo, pero ocurre tan raramente que su tiempo de inserción amortizado aún es $O(1)$O(1) .

Entre diferentes lenguajes de programación, el nombre de esta estructura de datos, así como su factor de cambio de tamaño (que es 2 en Java) varía. El factor de cambio de tamaño determina cuánto más grande se cambiará el tamaño de una matriz.

¿Por qué se amortiza el tiempo de inserción? $O(1)$O(1) ?

Al cambiar el tamaño, asumiendo que el factor de cambio de tamaño es 2, podemos observar que aumentamos a una matriz de tamaño N duplicando la matriz anterior (que es la mitad de N). Además, también necesitamos copiar $N\mathrm{/}2$N/2 elementos a esta nueva matriz.

Si sumamos el número de elementos que copiamos del aumento de capacidad final al primer aumento de capacidad: $\frac{n}{2}\frac{n}{4}\frac{n}{8}\frac{n}{16}\mathrm{.}\mathrm{.}\mathrm{.}21$2n​ 4n​ 8 n​ 16n ​ ... 2 1 que suma poco menos que N. Por lo tanto, insertar N elementos lleva aproximadamente $O(n)$En) trabajo en total. Cada inserción es $O(1)$O(1) en promedio, aunque algunas inserciones toman $O(n)$En) tiempo en el peor de los casos.

Conceptos básicos y complejidad de la gran O

Las matrices dinámicas en JavaScript suelen tener varios métodos principales, cada uno con diferentes complejidades temporales:

get(i): este método recupera el elemento en el índice i.

• Complejidad: $O(1)$O(1)

set(i, n): este método establece el elemento en el índice i a n.

• Complejidad: $O(1)$O(1)

pushback(n): este método agrega el elemento n al final de la matriz.

• Complejidad: $O(1)$O(1) amortizado, pero $O(n)$En) cuando ocurre el cambio de tamaño

popback(): este método elimina el último elemento de la matriz.

• Complejidad: $O(1)$O(1)

resize(): este método duplica la capacidad de la matriz y copia todos los elementos a la nueva matriz.

• Complejidad: $O(n)$En)

getSize(): Este método devuelve el número de elementos de la matriz.

• Complejidad: $O(1)$O(1)
• Nota: podemos lograr esta complejidad usando una variable de tamaño para rastrear el número de espacios ocupados en la matriz.

getCapacity(): Este método devuelve la capacidad actual de la matriz.

• Complejidad: $O(1)$O(1)

Implementación 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 = 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 




  
  
  Conclusión


Los arreglos dinámicos son una poderosa estructura de datos que combina la flexibilidad del almacenamiento redimensionable con la eficiencia del acceso en tiempo constante. ¡Espero que esto ayude!