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

#java #cpp #алгоритм #динамические_массивы #сложность

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

Ответы

Ответ 1

Ну вот смотрите. Берем динамический массив. Сначала из одного элемента.

Добавляем еще один. Удваиваем массив. Итого - одно выделение, один перенос (первого
элемента). 

Еще добавление - массив становится равен 4 элементам. Выделений - 2. переносов -
3 (теперь переносим 2 элемента, + 1 ранее). Добавление четвертого элемента не требует
ни выделения, ни переноса.

Еще добавление. Массив увеличивается до 8 элементов. Теперь в массиве 8 элементов,
3 выделения памяти, 7 переносов элементов. Элементы с 6 по 8 не требуют ни выделения,
ни переноса...

...

Теперь у нас 2n элементов, n выделений памяти, 2n-1 переноса элементов.

Т.е. в среднем каждый элемент пришлось переносить 1-2-n раз, при больших n - 1 раз. 

Константа? Да. При том, что первый элемент переносился log2n раз.

А вот в среднем, т.е. амортизированно - константа.

Так более-менее понятно?