re:re:actable
Урок 013 минуты чтения

Что такое array и dynamic array?

На этой странице
Кратко

Array - индексируемая последовательность элементов. Dynamic array может менять размер: при добавлении элементов он иногда выделяет больше памяти и копирует данные, поэтому push обычно считается amortized O(1).

Вопрос

Что такое array и dynamic array и почему push в среднем работает за O(1)?

Array как структура данных

Array дает быстрый доступ по индексу:

const nums = [10, 20, 30]
 
console.log(nums[1]) // 20

Доступ:

O(1)

Почему dynamic?

В JavaScript массивы изменяемые:

const nums: number[] = []
 
nums.push(1)
nums.push(2)
nums.push(3)

Внутри движок сам управляет памятью. Модель dynamic array полезна для понимания:

  • быстрый доступ по индексу;
  • быстрый push в конец;
  • дорогие вставки в начало/середину;
  • сдвиги элементов при shift, unshift, splice.

Почему push в среднем O(1)?

Под капотом dynamic array хранит элементы в непрерывном блоке памяти фиксированного размера - capacity. Пока место есть, push просто кладет элемент в следующую ячейку: O(1).

Когда место кончилось, массив:

  1. выделяет новый блок, обычно в 2 раза больше;
  2. копирует туда все старые элементы - это O(n);
  3. добавляет новый элемент.

Проследим 8 вызовов push при стартовой capacity = 1:

push №capacity доНужно расширять?Скопировано элементов
11нет0
21да, до 21
32да, до 42
44нет0
54да, до 84
6-88нет0

За 8 вставок скопировано всего 1 + 2 + 4 = 7 элементов - меньше одного копирования на вставку. В общем случае на n вставок приходится меньше 2n операций, то есть в среднем O(1) на вставку.

Это и называется amortized O(1): отдельный push иногда дорогой, но дорогие случаи настолько редки, что в сумме "размазываются" по всем дешевым.

Типичные сложности

ОперацияСложность
access by indexO(1)
update by indexO(1)
search by valueO(n)
push endamortized O(1)
pop endO(1)
insert/delete middleO(n)

Что отвечать на собеседовании?

Массив - линейная структура с доступом по индексу. Dynamic array умеет расти, поэтому добавление в конец обычно amortized O(1), но вставка или удаление в начале/середине требует сдвига элементов и стоит O(n).

Что важно помнить: частые ошибки

  • Считать любые операции массива O(1).
  • Использовать массив как очередь через shift на больших данных.
  • Не учитывать копии через slice.
  • Забывать, что поиск по значению линейный.
  • Мутировать input без согласования.

Мини-шпаргалка

  • Индекс - O(1).
  • Поиск - O(n).
  • push/pop - быстро.
  • shift/unshift - дорого.
  • Вставка в середину - O(n).
  • Dynamic array растет автоматически.

Документация

Wikipedia: Dynamic array.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам