Предполагается, что вы понимаете нотацию Big O. Примеры находятся в JavaScript. Информационные ссылки «Интервью по программированию» Гейл Лаакманн Макдауэлл

Введение

В некоторых языках, таких как JavaScript или Python, размер массивов автоматически изменяется, то есть он будет расти по мере добавления элементов. В других языках, таких как Java, массивы имеют фиксированную длину, то есть размер определяется при инициализации массива. Эти массивы, которые растут автоматически, называются динамическими массивами.

Понимание динамических массивов

В Java ArrayList — это структура данных, подобная массиву, которая обеспечивает динамическое изменение размера, сохраняя при этом $O(1)$O(1) доступ. Когда массив заполнен, его размер увеличивается вдвое. Каждое удвоение занимает $O(n)$На) время, но случается так редко, что его амортизированное время вставки все еще равно $O(1)$O(1) .

В разных языках программирования имя этой структуры данных, а также ее коэффициент изменения размера (который в Java равен 2) различаются. Коэффициент изменения размера определяет, насколько больше будет изменен размер массива.

Почему амортизируется время внедрения $O(1)$O(1) ?

При изменении размера, предполагая, что коэффициент изменения размера равен 2, мы можем наблюдать, что мы увеличиваем размер массива N, удваивая предыдущий массив (что составляет половину N). Кроме того, нам также нужно скопировать $N\mathrm{/}2$Н/2 элементы в этот новый массив.

Если мы суммируем количество элементов, которые мы копируем из окончательного увеличения емкости в первое увеличение емкости: $\frac{n}{2}\frac{n}{4}\frac{n}{8}\frac{n}{16}\mathrm{.}\mathrm{.}\mathrm{.}21$2n​ 4n​ 8 n​ 16n ​ ... 2 1 что в сумме чуть меньше N. Следовательно, вставка N элементов занимает около $O(n)$На) работа в целом. Каждая вставка $O(1)$O(1) в среднем, хотя некоторые вставки занимают $O(n)$На) время в худшем случае.

Основные понятия и сложность Big O

Динамические массивы в JavaScript обычно имеют несколько основных методов, каждый из которых имеет разную временную сложность:

get(i): этот метод извлекает элемент по индексу i.

• Сложность: $O(1)$O(1)

set(i, n): этот метод устанавливает элементу с индексом i значение n.

• Сложность: $O(1)$O(1)

pushback(n): этот метод добавляет элемент n в конец массива.

• Сложность: $O(1)$O(1) амортизировано, но $O(n)$На) когда происходит изменение размера

popback(): этот метод удаляет последний элемент массива.

• Сложность: $O(1)$O(1)

resize(): этот метод удваивает емкость массива и копирует все элементы в новый массив.

• Сложность: $O(n)$На)

getSize(): этот метод возвращает количество элементов в массиве.

• Сложность: $O(1)$O(1)
• Примечание: мы можем достичь этой сложности, используя переменную размера для отслеживания количества заполненных слотов в массиве.

getCapacity(): этот метод возвращает текущую емкость массива.

• Сложность: $O(1)$O(1)

Реализация в 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 




  
  
  Заключение


Динамические массивы — это мощная структура данных, которая сочетает в себе гибкость хранилища с изменяемым размером и эффективность доступа в постоянном времени. Надеюсь это поможет!