Амортизационный анализ на примере динамически расширяющегося массива

04 Jan, 2025

Задача:

Есть структура данных, которая поддерживает следующие операции:

1. push n - вставка элемента со значением n в конец структуры
2. get i - получение значения элемента с индексом i
3. pop - удаление значения с конца структуры

Мы говорим, что в случае, когда заканчивается память, выделенная под массив, нужно увеличить его размер вдвое, и это будет эффективно. Как это доказать? С помощью амортизационного анализа

Метод 1. Метод монеток(банкира)

Пусть операция вставки стоит одну монетку. Мы будем тратить на каждую операцию push 3 монетки:

• 1-я монетка на саму операцию вставки
• 2-я монетка для первой реаллокации
• 3-я монетка на элемент с индексом i-2^k, где i - индекс добавляемого элемента, а k - наибольшее натуральное число, при котором соблюдается неравенство 2^k < i

Тогда на второй и следующей реаллокациях 3-я монетка будет идти в первую половину массива, а 2-я монетка будет идти во вторую половину массива, то есть перед реаллокацией на каждом элементе будет по монетке, так что мы сможем оплатить повторное добавление элементов в увеличенный массив.

Ссылки

Пока я расписал только первый метод, так как он конкретно мне показался неочевидным, остальное есть тут:

1. Википедия
2. Источник из Википедии(Лекция Cornell University)