Algocourselecturenotes: Поправлены заголовки

2020-03-09T11:25:40Z

Поправлены заголовки

Algocourselecturenotes: Новая страница: «== Вектор == === Операции === Вектор - структура данных, поддерживающая следующие операции:
…»

2020-03-08T10:46:23Z

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

Новая страница

== Вектор ==

=== Операции ===
Вектор - структура данных, поддерживающая следующие операции: 
*Доступ по индексу 
*Добавление в конец структуры 
*Удаление из конца структуры 
Вышеперечисленные операции должны работать за '''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 ======
Остальные случаи рассматриваются аналогично первым двум.

@@ Строка 1: / Строка 1: @@
-== Вектор ==
+== Операции ==
 Вектор - структура данных, поддерживающая следующие операции:<br>
 *Доступ по индексу<br>
@@ Строка 8: / Строка 6: @@
 Вышеперечисленные операции должны работать за '''O(1)'''<br>
-=== Способы реализации вектора ===
+== Способы реализации вектора ==
-==== Способ 1 ====
+=== Способ 1 ===
 Если известно, что размер структуры в любой момент времени не превышает ''K'', то можно хранить массив на ''K'' элементов<br>
 ''Используемая память'' = $ \Theta(K) $ <br>
-==== Способ 2 ====
+=== Способ 2 ===
 Будем хранить массив размера ''buffer'', который в дальнейшем будем реаллоцировать. Пусть ''S'' - размер структуры.<br>
@@ Строка 21: / Строка 19: @@
 )''buffer'' гораздо больше, чем ''S'', тогда вектор занимает сильно больше памяти, чем требуется.
-===== Решение проблемы 1 =====
+==== Решение проблемы 1 ====
 ''S'' = ''buffer'', поступает запрос на добавление элемента. Тогда увеличиваем ''bufffer'' в 2 раза: создаём массив в 2 раза больше, копируем в первую половину нового массива весь старый.<br>
 '''Время операции''': $ \Theta(''buffer'') $ <br>
-===== Решение проблемы 2 =====
+==== Решение проблемы 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'')

Вектор - История изменений

Algocourselecturenotes: Поправлены заголовки

Algocourselecturenotes: Новая страница: «== Вектор == === Операции === Вектор - структура данных, поддерживающая следующие операции:…»

Algocourselecturenotes: Новая страница: «== Вектор == === Операции === Вектор - структура данных, поддерживающая следующие операции:
…»