Что такое 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).
Когда место кончилось, массив:
- выделяет новый блок, обычно в 2 раза больше;
- копирует туда все старые элементы - это
O(n); - добавляет новый элемент.
Проследим 8 вызовов push при стартовой capacity = 1:
| push № | capacity до | Нужно расширять? | Скопировано элементов |
|---|---|---|---|
| 1 | 1 | нет | 0 |
| 2 | 1 | да, до 2 | 1 |
| 3 | 2 | да, до 4 | 2 |
| 4 | 4 | нет | 0 |
| 5 | 4 | да, до 8 | 4 |
| 6-8 | 8 | нет | 0 |
За 8 вставок скопировано всего 1 + 2 + 4 = 7 элементов - меньше одного копирования на вставку. В общем случае на n вставок приходится меньше 2n операций, то есть в среднем O(1) на вставку.
Это и называется amortized O(1): отдельный push иногда дорогой, но дорогие случаи настолько редки, что в сумме "размазываются" по всем дешевым.
Типичные сложности
| Операция | Сложность |
|---|---|
| access by index | O(1) |
| update by index | O(1) |
| search by value | O(n) |
| push end | amortized O(1) |
| pop end | O(1) |
| insert/delete middle | O(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 растет автоматически.