Динамический массив

Динамический массив – это последовательная структура данных, обеспечивающая индексированный доступ к элементам и автоматическое изменение объёма памяти во время выполнения программы. В отличие от статического массива с фиксированной длиной, динамический массив поддерживает операции увеличения/уменьшения логического размера без предшествующего знания итогового числа элементов. Понимание модели, инвариантов и затрат операций в динамическом массиве формирует у абитуриента навыки алгоритмического мышления, оценки временной и пространственной сложностей, что напрямую помогает в заданиях ЕГЭ по информатике (массивы, обработка последовательностей, табличные преобразования, оценка сложности).

Формальная модель и инварианты

1. Модель
   

   Динамический массив задаётся кортежем

   A=⟨buf, size, capacity⟩, 

   где:

   • buf – указатель/ссылка на непрерывный блок памяти, хранящий элементы;

   • size – текущее число логически хранимых элементов;

   • capacity – объём выделенной памяти в элементах (capacity ≥ size).

2. Инварианты корректности
   

   1. Непрерывность хранения: элементы A[0],A[1],…,A[size−1] расположены в памяти подряд.

   2. Границы: доступ к A[i] корректен тогда и только тогда, когда 0≤i<size.

   3. Ёмкость: вставка элемента при size<capacity не вызывает выделения новой памяти; при size=capacity выполняется реаллокация и расширение.

   4. Стабильность порядка: операции вставки/удаления сохраняют относительный порядок прочих элементов (если явно не оговорено обратное).

Политики роста и амортизированный анализ

1. Политика роста
   

   При нехватке места выделяется новый блок памяти большего размера, все элементы копируются/перемещаются в него, старый блок освобождается. Типичные коэффициенты роста: ×2, ×1,5 и т.п.

2.  Амортизированная стоимость push_back
   

   Пусть массив начинает с capacity=1 и при переполнении удваивает ёмкость. При последовательном добавлении nnn элементов произойдёт ⌊log2n⌋ реаллокаций. Суммарное число копирований элементов при всех расширениях не превосходит 2n.

   Следствие: средняя стоимость одной операции добавления – O(1) амортизированно, несмотря на редкие «дорогие» расширения O(n).

3.  Влияние коэффициента роста
   

   • Больший коэффициент ⇒ меньше реаллокаций, но больше «пустой» памяти.

   • Меньший коэффициент ⇒ экономия памяти, но чаще копирования.
     Практическое правило: выбирайте коэффициент роста исходя из профиля нагрузки; для потоков ввода неизвестной длины целесообразен рост ×2 или ×1,5.

Операции и их сложности

Правила:

1. Частые вставки/удаления в середине/начале экономически нецелесообразны для динамического массива – используйте другие структуры (списки, дека, буфер с головным индексом) или меняйте алгоритм.

2. Для предсказуемых объёмов ввода заранее вызывайте reserve (принцип опережающего выделения).

3. Помните, что реаллокация инвалидирует старые адреса/итераторы/ссылки на элементы – после расширения ими пользоваться нельзя.

Память, кэш и производительность

• Локальность данных. Непрерывное хранение повышает кэш-эффективность при линейных проходах и операциях над всем массивом (скан, редукция, сортировка).

• Выравнивание и размер элемента. Крупные элементы повышают накладные расходы копирования при реаллокации; в задачах с крупными объектами применяйте перемещение/ссылки/идентификаторы.

• Фрагментация. Частые расширения и сжатия могут приводить к фрагментации кучи; смягчайте reserve, группируйте операции.

Псевдокод ключевых процедур

1. Добавление в конец
   

   procedure push_back(A, x):

       if A.size == A.capacity:

           new_capacity ← growth(A.capacity)   // например, max(1, 2*capacity)

           new_buf ← allocate(new_capacity)

           copy(new_buf[0..A.size-1], A.buf[0..A.size-1])

           deallocate(A.buf)

           A.buf ← new_buf

           A.capacity ← new_capacity

       A.buf[A.size] ← x

       A.size ← A.size + 1

2. Вставка в позицию
   

   procedure insert(A, pos, x):

       assert 0 ≤ pos ≤ A.size

       if A.size == A.capacity: reallocate_growth(A)

       // сдвиг хвоста вправо

       for i from A.size-1 downto pos:

           A.buf[i+1] ← A.buf[i]

       A.buf[pos] ← x

       A.size ← A.size + 1

3. Удаление из позиции 
   

   procedure erase(A, pos):

       assert 0 ≤ pos < A.size

       for i from pos to A.size-2:

           A.buf[i] ← A.buf[i+1]

       A.size ← A.size - 1

Сопоставление с другими структурами

Вывод: при преобладании линейных проходов, сортировок, агрегаций и добавлений в конец динамический массив – оптимальный выбор (что характерно для многих задач ЕГЭ).

Связь с подготовкой к ЕГЭ по информатике

1. Обработка последовательностей переменной длины. В задачах с неизвестным числом входных данных (до маркера/EOF) динамический массив естественен.

2. Сложность алгоритмов. Освоение амортизированного O(1) добавления и O(n) вставки в середину помогает выбирать правильные алгоритмы (например, собирать данные, затем сортировать, а не «вставлять на место»).

3. Табличные преобразования. Построение частотных массивов, префикс-сумм, фильтраций «по условию» удобно реализовывать на динамических массивах.

4. Память и корректность. Границы индексов, работа с ёмкостью/размером – частые источники ошибок, отработка которых повышает аккуратность решения экзаменационных задач.

Типичные ошибки и правила профилактики

• Выход за границы: доступ к A[size] недопустим; всегда проверяйте диапазоны.

• Забытый учёт capacity: дорогостоящие реаллокации из-за мелких ростов → применяйте reserve.

• Инвалидация ссылок после расширения: не храните долговременные указатели на элементы – переизвлекайте после операций, которые могли расширить буфер.

• Нерациональные вставки в начало/середину: для таких профилей используйте другие структуры или алгоритмы «собрать → отсортировать».

• Избыточные shrink_to_fit: частое сжатие может ухудшать производительность; сжимайте только при подтверждённой необходимости.

Пять упражнений (академический формат «теория + практика»)

Упражнение 1. Амортизированный анализ

Динамический массив стартует с capacity = 1 и удваивает ёмкость при переполнении.
Задания:
a) Докажите, что суммарное число копирований при добавлении nnn элементов не превосходит 2n.
b) Оцените среднюю стоимость одной операции push_back (в асимптотике и в «копированиях на элемент»).
c) Сравните с политикой роста ×1,5: оцените количество реаллокаций и память-овербайт при больших nnn.

Упражнение 2. Симуляция операций

Дан пустой массив. Последовательно выполните:
push_back(7), push_back(4), push_back(9), insert(1, 5), erase(2), push_back(1), insert(0, 8).
Задания:
a) Запишите содержимое массива после каждой операции.
b) Укажите моменты, когда происходит реаллокация, если начальная capacity = 1, рост ×2.

c) Подсчитайте суммарное число копирований элементов, вызванных реаллокациями и сдвигами отдельно.

Упражнение 3. Предварительное резервирование

Планируется считать N=10⁶ целых значений и затем выполнить сортировку и линейный проход для подсчёта количества уникальных элементов.
Задания:
a) Предложите порядок действий с использованием reserve, оцените выигрыш по числу реаллокаций.
b) Оцените асимптотическую сложность всего процесса.
c) Обоснуйте, почему динамический массив предпочтительнее связного списка для данного профиля.

Упражнение 4. Удаление по предикату (стабильное)

Требуется удалить все элементы, удовлетворяющие условию P(x), сохранив порядок остальных.
Задания:
a) Опишите алгоритм «стабильного сжатия» на месте (двойной указатель: write/read).
b) Докажите корректность и оцените сложность по времени/памяти.
c) Предложите вариант с накоплением индексов удаляемых элементов и обсуждением кэш-локальности.

Упражнение 5. Баланс «память ↔ скорость»

Дан поток из n элементов. Сравниваются три стратегии:

1. Без reserve (рост ×2);

2. reserve(n) заранее;

3. Поштучные «малые» расширения на +1 к capacity при каждом переполнении.
   

   Задания:
   a) Сравните стратегии по числу реаллокаций, пиковому использованию памяти и времени.
   b) Объясните, почему стратегия 3) часто худшая по времени.
   c) Сформулируйте практическое правило выбора между 1) и 2) при частично известном nnn.

Заключение

Динамический массив – фундаментальная структура данных с сочетанием индексного доступа O(1), высокой кэш-локальности и амортизированного O(1) добавления в конец. Теоретическое понимание модели (инварианты, политика роста, амортизированный анализ) и практические правила (границы, reserve, корректная работа с ссылками, выбор алгоритмов) позволяют решать широкий спектр учебных и прикладных задач. Для ЕГЭ это означает уверенное владение массивами и последовательностями, грамотный расчёт сложностей и аккуратное выполнение процедур – компетенции, напрямую конвертирующиеся в высокие баллы.