Array (Массив)
Массив — коллекция элементов, хранящихся в непрерывном блоке памяти, с доступом по индексу за O(1). Индексация даёт мгновенный доступ, но вставка/удаление в середине требует сдвига элементов.
Сложности операций
| Операция | Сложность | Комментарий |
|---|---|---|
| Доступ по индексу | O(1) | адрес = база + индекс × размер |
| Поиск по значению | O(n) | линейный проход (O(log n), если отсортирован — бинарный поиск) |
| Вставка/удаление в конец | O(1)* | амортизированно для динамического массива |
| Вставка/удаление в начало/середину | O(n) | нужен сдвиг элементов |
Динамический массив (JS Array)
В JS массив — динамический: при переполнении внутренней ёмкости выделяется новый буфер (обычно ×2) и элементы копируются. Поэтому push — амортизированно O(1), но отдельные вставки иногда O(n) на копирование.
const arr = [1, 2, 3];
arr.push(4); // O(1) амортизированно
arr.pop(); // O(1)
arr.unshift(0); // O(n) — сдвиг всех элементов
arr.shift(); // O(n) — сдвиг всех элементов
arr[1]; // O(1) — доступ по индексу
arr.includes(2); // O(n) — линейный поиск⚠️
shift/unshift(операции с началом) — O(n). Для частых операций с обоих концов используйте дек.
См. также
- linked-list — вставка/удаление за O(1), но доступ за O(n)
- prefix-sums — сумма на отрезке массива за O(1)
- LeetCode: задачи