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

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

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

Пример: динамический массив (ArrayList) при добавлении элементов.

• Обычно добавление элемента — операция O(1).
• Но когда массив заполняется, происходит перераспределение памяти и копирование элементов — операция O(n).

Амортизированная сложность добавления при этом остаётся O(1), потому что дорогие операции происходят редко и их стоимость распределяется на множество дешёвых операций.

Это помогает оценивать эффективность алгоритмов и структур данных в реальных условиях, а не только в худших случаях.