Базовые структуры, амортизационный анализ

Вектор

Операции

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

• Доступ по индексу
  
• Добавление в конец структуры
  
• Удаление из конца структуры
  

Вышеперечисленные операции должны работать за O(1)

Способы реализации вектора

Способ 1

Если известно, что размер структуры в любой момент времени не превышает K, то можно хранить массив на K элементов

Используемая память = $ \Theta(K) $

Способ 2

Будем хранить массив размера buffer, который в дальнейшем будем реаллоцировать. Пусть S - размер структуры.

Возникает 2 проблемы:
1)S = buffer: в этом случае нам некуда добавлять новые элементы
2)buffer гораздо больше, чем S, тогда вектор занимает сильно больше памяти, чем требуется.

Решение проблемы 1

S = buffer, поступает запрос на добавление элемента. Тогда увеличиваем bufffer в 2 раза: создаём массив в 2 раза больше, копируем в первую половину нового массива весь старый.
Время операции: $ \Theta(buffer) $

Решение проблемы 2

Если S меньше buffer более чем в 4 раза, то уменьшаем buffer в 2 раза
Время операции: $ \Theta(buffer) $

Оценка времени

Таким образом, $ \frac{1}{4}buffer \leq S \leq buffer $, а значит buffer = O(S)
Амортизированно, требуемые операции выполняются за O(1), то есть если изначально структура пустая, то любые m операций выполняются за O(m)

Доказательство амортизированности: cлучай 1

Между двумя командами push_back, требующими реаллокацию, будет хотя бы buffer операций push_back. Все эти операции потребуют O(buffer) времени, поделим на buffer, и поймём, что в среднем одна операция выполняется за O(1).

Доказательство амортизированности: cлучай 2

Между командами push_back и pop_back, требующими реаллокацию, будет хотя бы $ \frac{buffer}{2} $ операций pop_back. Все эти операции потребуют O(buffer) времени, поделим на buffer, и поймём, что в среднем одна операция выполняется за O(1).

Доказательство амортизированности: cлучай 3, 4

Остальные случаи рассматриваются аналогично первым двум.