Динамические массивы — это структуры данных, которые автоматически изменяют размер при достижении мощности. Понимание их амортизированной стоимости помогает оценить их эффективность по нескольким операциям.

Что такое амортизированная стоимость?

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

Динамические операции Array

Общие операции на динамических массивах включают вставку, удаление и изменение размера.Вставка в конце обычно является наиболее частой операцией, которая может вызвать изменение размера при превышении емкости.

Расчет амортизированной стоимости

При вставке элементов массив удваивается в размере при заполнении. Стоимость изменения размера предполагает копирование всех существующих элементов в новый массив. Хотя изменение размера является дорогостоящим, оно происходит нечасто.

Например, если массив начинается с емкости 1, последовательность затрат на изменение размера по нескольким вставкам может быть суммирована следующим образом:

  • Включить 1 элемент: стоимость 1
  • Включить 2-й элемент: размер (стоимость 1), общая стоимость 2
  • Включить 3-й элемент: размер (стоимость 2), общая стоимость 3
  • Включить 4-й элемент: размер (стоимость 4), общая стоимость 4

Общая стоимость вставок свыше n пропорциональна 2n, что делает амортизированную стоимость вставки приблизительно O(1).