Амортизированная константа

Может кто-нибудь объяснить, что означает амортизированная сложность алгоритма, в частности, амортизированная константа? Это когда для массива операция выполняется не каждый вызов, а только один раз?

Ответ

Ну вот смотрите. Берем динамическим массив. Сначала из одного элемента.
Добавляем еще один. Удваиваем массив. Итого - одно выделение, один перенос (первого элемента).
Еще добавление - массив становится равен 4 элементам. Выделений - 2. переносов - 3 (теперь переносим 2 элемента, + 1 ранее). Добавление четвертого элемента не требует ни выделения, ни переноса.
Еще добавление. Массив увеличивается до 8 элементов. Теперь в массиве 8 элементов, 3 выделения памяти, 7 переносов элементов. Элементы с 6 по 8 не требуют ни выделения, ни переноса...
...
Теперь у нас 2n элементов, n выделений памяти, 2n-1 переноса элементов.
Т.е. в среднем каждый элемент пришлось переносить 1-2-n раз, при больших n - 1 раз.
Константа? Да. При том, что первый элемент переносился log2n раз.
А вот в среднем, т.е. амортизированно - константа.
Так более-менее понятно?