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

== Вектор ==

=== Операции ===
Вектор - структура данных, поддерживающая следующие операции:<br>
*Доступ по индексу<br>
*Добавление в конец структуры<br>
*Удаление из конца структуры<br>
Вышеперечисленные операции должны работать за '''O(1)'''<br>

=== Способы реализации вектора ===
==== Способ 1 ====
Если известно, что размер структуры в любой момент времени не превышает ''K'', то можно хранить массив на ''K'' элементов<br>

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

==== Способ 2 ====
Будем хранить массив размера ''buffer'', который в дальнейшем будем реаллоцировать. Пусть ''S'' - размер структуры.<br>

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

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

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

===== Оценка времени =====
Таким образом, $ \frac{1}{4}''buffer'' \leq ''S'' \leq ''buffer'' $, а значит ''buffer'' = O(''S'')<br> 
Амортизированно, требуемые операции выполняются за 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 ======
Остальные случаи рассматриваются аналогично первым двум.