Массив — это упорядоченная структура данных для хранения набора элементов под одним именем. Он позволяет хранить множество значений в виде последовательного списка, к каждому элементу которого можно быстро обратиться по его порядковому номеру (индексу).
Упорядоченная здесь означает, что порядок элементов имеет значение. Это не
то же самое, что отсортированная: значения не обязаны идти по возрастанию или
убыванию.
array = sequence[0..n-1]
Для массива длины n допустимые индексы:
0 <= i < n
Пример:
arr = [7, 3, 9, 1]
index: 0 1 2 3
value: 7 3 9 1
Чтобы восстановить содержимое конкретного массива как последовательность,
достаточно знать:
1. длина
2. значение в каждой позиции
Термины
n -> длина массива
i -> индекс
arr[i] -> значение на индексе i
0 -> первый индекс
n - 1 -> последний индекс
Индекс и значение не совпадают по смыслу.
arr[2] = 9
2 -> индекс
9 -> значение
Виды массивов
Статический массив
Статический массив имеет фиксированную длину.
length = n
После создания количество позиций не меняется. Значения по существующим
индексам можно читать и изменять, если массив мутабельный.
arr[i]
arr[i] = x
Для изменения размера требуется создать новый массив и перенести элементы.
Ключевые свойства:
фиксированная длина
непрерывное хранение элементов
доступ по индексу за O(1)
Динамический массив
Динамический массив хранит элементы в массиве фиксированной ёмкости, но
предоставляет операцию расширения.
append(x)
Если свободная ёмкость есть, добавление в конец стоит O(1).
Если свободной ёмкости нет:
1. создаётся новый внутренний массив большей ёмкости
2. старые элементы копируются в него
3. новый элемент записывается в конец
Стоимость отдельного расширения:
O(n)
Амортизированная стоимость добавления в конец:
amortized O(1)
Примеры динамических массивов:
Python list
Java ArrayList
JavaScript Array
C++ vector
Свойства
Короткая карта свойств массива как структуры:
длина -> количество элементов / позиций: n
индексированность -> у каждой позиции есть индекс
индексная область -> допустимые индексы: 0 ... n - 1
упорядоченность -> порядок элементов имеет значение
позиционность -> каждый элемент находится на конкретной позиции
доступ по индексу -> значение можно получить через arr[i]
границы -> нельзя обращаться за пределы индексной области
повторяемость -> одинаковые значения могут встречаться несколько раз
соседство -> у элемента могут быть левый и правый сосед
диапазоны -> можно выделять часть массива по индексам
Важно отделять свойства массива от характеристик конкретного массива:
свойство: у массива есть длина
характеристика: длина этого массива = 4
свойство: массив допускает повторяющиеся значения
характеристика: в этом массиве повторов нет
Длина
Массив содержит определённое число элементов / позиций.
length(arr) = n
Длина — это массивная форма конечности: через неё задаются индексная область,
последний индекс и выход за границы.
Индексированность
Каждый элемент имеет позицию.
arr[0], arr[1], ..., arr[n - 1]
Индексная область
Для массива длины n допустимые индексы:
0, 1, 2, ..., n - 1
Порядок
Порядок элементов является частью массива.
[7, 3, 9, 1] != [1, 9, 3, 7]
Границы
Обращение допустимо только по индексам из диапазона:
0 <= i < n
Индекс n выходит за границу.
arr[n] -> out of bounds
Повторяемость значений
Массив допускает одинаковые значения.
[5, 5, 5, 2]
Массив хранит значение для каждой позиции, а не множество уникальных значений.
Соседство
Для элемента arr[i] возможны соседи:
left = arr[i - 1], если i > 0
right = arr[i + 1], если i + 1 < n
Соседство используется в задачах на сравнение рядом стоящих элементов.
Диапазон
Подмассив задаётся диапазоном индексов.
arr[l..r]
Для полуоткрытого диапазона:
arr[l..r)
условия корректности:
0 <= l <= r <= n
Базовые операции
Длина
length(arr)
Обычно:
O(1)
Чтение по индексу
arr[i]
Условие:
0 <= i < n
Сложность:
O(1)
Запись по индексу
arr[i] = x
Условие:
0 <= i < n
Сложность:
O(1)
Проход
for i from 0 to n - 1:
use arr[i]
Сложность:
O(n)
Поиск значения
find x in arr
В неотсортированном массиве требуется линейный проход.
O(n)
Проверка наличия
x in arr
В неотсортированном массиве:
O(n)
Подсчёт
count elements where condition is true
Сложность:
O(n)
Минимум и максимум
min(arr)
max(arr)
В неотсортированном массиве:
O(n)
Сумма
sum(arr)
Сложность:
O(n)
Обмен двух элементов
swap(arr[i], arr[j])
Условие:
0 <= i < n
0 <= j < n
Сложность:
O(1)
Вставка
insert(arr, i, x)
При вставке элементы справа от i сдвигаются вправо.
[7, 3, 9, 1]
insert index 2 value 100
[7, 3, 100, 9, 1]
Сложность:
O(n)
Удаление
delete(arr, i)
При удалении элементы справа от i сдвигаются влево.
[7, 3, 9, 1]
delete index 1
[7, 9, 1]
Сложность:
O(n)
Добавление в конец
append(arr, x)
Для динамического массива:
amortized O(1)
Отдельная операция может стоить O(n), если требуется расширение внутреннего
хранилища.
Удаление с конца
pop(arr)
Для динамического массива обычно:
O(1)
Разворот
reverse(arr)
Сложность:
O(n)
Сортировка
sort(arr)
Типичная сложность сравнительной сортировки:
O(n log n)
Конкретная сложность зависит от алгоритма сортировки и реализации.
Таблица сложностей
| Операция | Сложность |
|---|---|
length(arr) |
O(1) |
arr[i] |
O(1) |
arr[i] = x |
O(1) |
| проход по всем элементам | O(n) |
| поиск в неотсортированном массиве | O(n) |
| минимум / максимум | O(n) |
| сумма | O(n) |
swap(arr[i], arr[j]) |
O(1) |
| вставка в середину | O(n) |
| удаление из середины | O(n) |
append в динамический массив |
amortized O(1) |
pop с конца |
O(1) |
| разворот | O(n) |
| сортировка сравнением | O(n log n) |
Формальная схема
Array = {
length: n,
indexes: 0..n-1,
values: arr[0], arr[1], ..., arr[n-1]
}
Операции массива изменяют или используют одну из трёх сущностей:
индекс
значение
порядок
Примеры:
arr[i] -> чтение значения по индексу
arr[i] = x -> изменение значения
swap(i, j) -> изменение порядка
insert(i, x) -> изменение длины и порядка
delete(i) -> изменение длины и порядка
sort(arr) -> изменение порядка
Минимальная формулировка:
массив = конечная индексированная последовательность значений
